유클리드 호제법과 최대 공약수(GCD), 최소 공배수(LCM)

최대 공약수 (Greatest Common Divisor, GCD)

최대 공약수(GCD)는 두 개 이상의 정수의 공통 약수 중 가장 큰 수를 말합니다.

예를 들어, 12와 18의 최대 공약수는 6입니다.

최소 공배수 (Least Common Multiple, LCM)

최소 공배수(LCM)는 두 개 이상의 정수의 공통 배수 중 가장 작은 수를 말합니다.

예를 들어, 12와 18의 최소 공배수는 36입니다.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 정수의 최대 공약수(GCD)를 찾는 데 사용하는 알고리즘입니다.

유클리드 호제법

두 양의 정수 $a, b(a>b)$에 대하여 $a=bq+r(0\le r \lt b)$라 하면, $a, b$의 최대 공약수는 $b, r$의 최대 공약수와 같다.

\[GCD(a,b)=GCD(b,r)\]

$r=0$이라면, $a, b$의 최대 공약수는 $b$가 된다.

유클리드 호제법의 기본 원리

유클리드 호제법에서는 $a$를 $b$로 나누고 나머지를 $r$이라 할 때, $a$와 $b$의 최대 공약수는 $b$와 $r$의 최대 공약수와 같다는 것을 이용합니다.

나머지 정리

우선, 두 수의 나눗셈에서 몫과 나머지에 대한 나머지 정리를 알아야 합니다.

어떤 수 $a$를 $b$로 나누고 나온 나머지 $r$에 대해 공식으로 정리하면 다음과 같습니다.

\[a=b\cdot q+r\]

즉, 어떤 수 $b$에 몫 $q$를 곱하고 나머지 $r$을 더하면 $a$가 나온다는 것입니다.

공약수 관계 설명

$a$와 $b$의 어떤 공약수를 $d$라고 합시다.

여기에서, $a$를 $d$로 나누면 $k$가 되고, $b$를 $d$로 나누면 $l$이 된다고 가정합니다.

\[a=kd, b=ld\]

이때, $d$는 공약수이기 때문에, 나머지가 존재하지 않게 됩니다.

이제, 나머지 $r$에 대해서 정리해 보겠습니다.

\[\begin{align} a&=b\cdot q+r \tag{나머지 정리} \\ r&=a-b \cdot q \\ &=kd-ld \cdot q \\ &=d(k-l \cdot q) \end{align}\]

결과적으로 $r$은 $d$로 나누어 떨어집니다.

즉, $d$는 $r$의 공약수이기도 합니다.

정리

• 공약수 $d$는 $a$와 $b$를 나눌 수 있습니다.
• $a$와 $b$로 나눈 나머지 $r$도 $d$로 나눌 수 있습니다.
• 따라서, $a$와 $b$의 최대 공약수는 $b$와 $r$의 최대 공약수와 동일합니다.

즉, 두 양의 정수 $a, b(a>b)$에 대해서, $a, b$의 최대 공약수는 $b, r$의 최대 공약수와 같고,

나머지가 없는 상태($r=0$)라면, $b$는 $a$의 최대 공약수가 됩니다.

유클리드 호제법 코드

즉, 위와 같은 원리로 인해, $a$를 $b$로 나누었을 때, $r=0$이라면 $b$가 최대 공약수가 되기 때문에 아래와 같은 코드를 작성할 수 있습니다.

(코드에서는 b==0이 되는 순간, a가 $b$이기 때문에 return a가 됩니다.)

int GCD(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}

	return a;
}

유클리드 호제법으로 최소 공배수 찾기

$a$와 $b$를 $GCD(a,b)$로 나누면, 서로소 관계(공약수가 1인 관계)가 되는 두 수 $a’$와 $b’$를 얻을 수 있습니다.

\[\begin{align} a&=GCD(a,b) \cdot a' \\ b&=GCD(a,b) \cdot b' \end{align}\]

또한, 최소 공배수(LCM)은 두 수의 최대 공약수에 두 수에 대한 서로소의 곱으로 구합니다.

\[LCM(a,b)=GCD(a,b) \cdot a' \cdot b'\]

이때, 두 수($a, b$)를 곱한다고 가정하면 다음과 같은 결론을 얻을 수 있습니다.

\[\begin{align} a \cdot b &= GCD(a, b) \cdot a' \cdot GCD(a, b) \cdot b' \\ &= GCD(a,b) \cdot LCM(a,b) \end{align}\]

따라서, 최소 공배수(LCM)를 다음과 같이 쓸 수 있습니다.

\[LCM(a,b) = \frac{(a \cdot b)}{GCD(a,b)}\]

그러므로, 코드로 만들면 유클리드 호제법을 사용해 다음과 같이 만들 수 있습니다.

int LCM(int a, int b)
{
	return (a * b) / GCD(a, b);
}