유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.

유클리드 호제법의 사용

유클리드 호제법(유클리드 알고리즘)은 아래의 성질을 이용한다.

두 정수 a, b (a > b) 에 대해 a를 b로 나눈 나머지를 r 이라 하면(r = a % b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

위의 성질을 이용해 24와 18의 최대공약수를 구해보자.
24 > 18 이므로 a = 24, b = 18 이라고 하면 r = 24 % 18 = 6 이다.
성질에 의해 24(a)와 18(b)의 최대공약수는 18(b)과 6(r)의 최대공약수와 같다.
그렇다면 24와 18의 최대공약수를 구하는 문제는 18과 6의 최대공약수를 구하는 문제가 된다.
그렇다면 18과 6의 최대공약수를 구해보자.
18 % 6 = 0 이므로 최대공약수는 6이다.

유클리드 호제법은 이와 같이 성질을 반복적으로 이용해 최대공약수를 구하는 대상이 되는 두 개의 숫자를 나눗셈을 통해 줄여나가며 최종적으로 a % b = 0 이 될 때 최대공약수를 구한다.

반복적으로 나누고, 그 나머지를 이용하므로 표기를 다르게 하면 아래와 같이 쓸 수도 있다.
1886과 423의 최대공약수를 구해보자.
1886 > 423 이므로 a = 1886, b = 423 이다.
1886 = 423 * 4 + 194 이므로 r = 194 이다.
이제 문제는 423과 194 의 최대공약수를 구하는 문제가 된다.
423 = 194 * 2 + 35
194 = 35 * 5 + 19
35 = 19 * 1 + 16
19 = 16 * 1 + 3
16 = 3 * 5 + 1
3 = 1 * 3 + 0
즉 3은 1로 나누어떨어지므로 최대공약수는 3이다.

유클리드 호제법 증명

간단하게 증명해보자면
어떤 정수 a, b 가 있고, a >= b 라고 할 때,
a = bq + r 을 만족하는 q, r 쌍은 유일하다.
(14 = 3*4 + 2 같은 식을 생각해보면, q의 위치인 4가 다른 값으로 바뀌면 r의 위치인 2도 다른 값으로 바뀌어야 한다는 것이 명백하다. 그 반대도 마찬가지.)
이 때, a와 b의 최대공약수를 d라고 하면 a = dα, b = dβ 로 나타낼 수 있으므로
a = bq + r 은 아래와 같이 쓸 수 있다.
dα = dβq + r
이 때 d, α, β, q 는 모두 정수이다.
최대공약수는 0이 될 수 없으므로 위 식을 d로 나누면,
α = βq + r/d 가 되고, α와 βq 모두 정수이므로 r/d 도 정수여야 한다.
즉, r 은 d의 배수이다.

자세한 증명은 위키백과에 잘 나와 있습니다

유클리드 호제법 구현

유클리드 호제법은 결국 a, b, r 을 가지고 반복적으로 같은 식을 수행하기 때문에 재귀로 구현할 수 있다.
재귀를 멈추는 순간은 r 이 0이 되는 순간이다.

int gcd(a, b) {
  int r = a % b;
  if(r == 0) return b;
  return gcd(b, r);
}
// 혹은
int gcd(a, b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

재귀를 사용하지 않고 아래와 같이 구현할 수도 있다.

int gcd(a, b) {
  int r;
  while(b = 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

참고링크

유클리드 호제법 - 위키백과