유클리드 알고리즘(Euclidean Algorithm) - 최대공약수(GCD) 구하기

유클리드 알고리즘은 최대공약수(GCD)를 구하는 가장 효율적인 알고리즘입니다.

다음과 같은 성질을 이용하여 두 정수 $a, b$의 최대공약수를 구할 수 있습니다.

• $a=0$ 이면 $gcd(0,b)=b$ 이므로 $gcd(a,b)=b$ 입니다.
• $b=0$ 이면 $gcd(a,0)=a$ 이므로 $gcd(a,b)=a$ 입니다.
• $a=bq+r \; (0 \le r < b)$ 이면 $gcd(a,b)=gcd(b,r)$ 입니다.

---

증명

[명제 1]

• $a=0$ 이면 $gcd(0,b)=b$ 이므로 $gcd(a,b)=b$ 입니다.
• $b=0$ 이면 $gcd(a,0)=a$ 이므로 $gcd(a,b)=a$ 입니다.

증명

$gcd(a,0)=a$ 는 다음과 같이 증명할 수 있습니다.

• $a$ 를 나누어떨어지게 하는 가장 큰 양의 정수는 $a$ 입니다.
• 0의 약수는 0이 아닌 모든 정수입니다.

따라서 $a$ 와 0을 동시에 나누는 가장 큰 정수는 $a$이며, $gcd(a,0)=a$ 가 성립합니다.

*$gcd(0,b)=b$ 역시 같은 방식으로 증명할 수 있으므로 생략합니다.

[명제 2]

• $a=bq+r$ $(0 \le r < b)$ 이면 $gcd(a,b)=gcd(b,r)$ 입니다.

해당 명제는 일차결합 성질을 이용하여 증명할 수 있습니다.

증명

$a \mid b$, $a \mid c$ 라고 가정하면, 어떤 정수 $m,n$ 에 대해 $am=b, an=c$ 입니다.

$bx+cy=(am)x+(an)y=a(mx+ny)$

$bx+cy$ 는 $a$ 로 나누어떨어지므로 $a \mid (bx+cy)$ 입니다.

다시 명제 2로 돌아가서,

증명

$d=gcd(a,b)$ 라고 두면 정의상 $d \mid a$, $d \mid b$ 이고 $a=bq+r$ 에 따르면 $r=a-bq$ 입니다.

일차결합 성질에서 $x=1$, $y=-q$ 를 택하면 $d \mid (ax+by)=(a-bq)=r$ 이므로 $gcd(a,b) \mid r$ 입니다.

$gcd(a,b) \mid b, \; gcd(a,b) \mid r$ 이므로 $gcd(a,b)$ 는 $b,r$ 의 공약수입니다.

마찬가지로 $gcd(b,r)$ 에 대해서도 같은 논리를 적용하면 $gcd(b,r) \mid (bq+r)=a$ 로 $gcd(b,r) \mid a, \; gcd(b,r) \mid b$ 가 성립합니다.

즉, $b,r$ 의 모든 공약수는 $a,b$ 의 공약수이기도 합니다.

공약수 집합이 서로 같으므로 최대공약수도 같아 $gcd(a,b)=gcd(b,r)$ 가 성립합니다.

---

예제

간단한 예제로 유클리드 알고리즘 동작 과정을 살펴보겠습니다.

앞에서 증명한 성질을 이용하면 다음 절차로 두 정수의 최대공약수를 구할 수 있습니다.

1. 두 정수 $a,b$ 에 대해 나눗셈 알고리즘 $a=bq+r$ 을 적용합니다.
2. $a$ 또는 $b$ 중 하나가 0이면 [명제 1]에 의해 $gcd(a,b)=b$ 또는 $gcd(a,b)=a$ 이므로 종료합니다.
3. 두 정수 모두 0이 아니라면 $gcd(a,b)=gcd(b,r)$ 성질을 이용하여 $b$ 와 $r$ 에 대해 다시 나눗셈을 수행합니다.

-> 위 과정을 나머지가 0이 될 때까지 반복합니다.

기본 예제

유클리드 알고리즘을 사용하여 $gcd(174,132)$ 구하기

$a=174, b=132$

$174=132*1+42$ => $gcd(174,132)=gcd(132,42)$

$132=42*3+6$ => $gcd(132,42)=gcd(42,6)$

$42=6*7+0$ => $gcd(42,6)=gcd(6,0)=6$

$\therefore gcd(174,132)=6$

JavaScript 예제

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;
    a = b;
    b = r;
  }
  return a;
}

반복적인 나머지 연산을 통해 최대공약수를 구합니다.

• 각 단계에서 $(a,b) \leftarrow (b,r)$ 로 값을 갱신합니다. $gcd(a,b)=gcd(b,r)$
• $b=0$ 이 되는 순간 $gcd(a,0)=a$ 이므로 $a$ 가 최대공약수가 됩니다.

재귀적으로도 구현할 수 있습니다.

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

두 개 이상 정수의 최대공약수

최대공약수는 결합법칙이 성립합니다.

$gcd(a,b,c)=gcd(gcd(a,b),c)$

이 성질을 이용하면 n개의 정수에 대해서도 순차적으로 최대공약수를 계산할 수 있습니다.

function gcdMultiple(numbers) {
  return numbers.reduce((acc, num) => gcd(acc, num));
}

console.log(gcdMultiple([48, 18, 30])); // 6
console.log(gcdMultiple([56, 98, 42])); // 14

앞 두 수의 최대공약수를 구한 뒤, 그 결과를 다음 수와 다시 최대공약수를 구하는 방식으로 전체 정수들의 최대공약수를 계산합니다.

---

References

Khan Academy