유클리드 호제법

오늘은 최대 공약수를 구할 수 있는 파워풀한 알고리즘인

유클리드 호제법 에 대해 포스팅을 하도록 하겠다.

유클리드 호제법의 정의는 다음과 같다.

두 양의 정수 a, b (b > a) 에 대해 b = aq + r (0 <= r < q) 라 하면
gcd(a, b) = gcd(a, r)이 성립한다.

a, b의 최대 공약수는 a, r의 최대 공약수와 같다는 말이다. (왜?)

자 그럼 왜 그런지 증명을 해보자.

gcd(a, b) = G 라고 하고, 서로소 A, B에 대해 다음과 같은 식이 성립된다.
a = GA, b = GB

유클리드 호제법 정의의 b = aq + r 에 위의 수식을 대입하면
GB = GAq + r 이고 이를 이항 후 G로 묶으면
r = G(B - Aq) 가 성립한다.
유클리드 호제법의 정의에 따르면 gcd(a, b) = gcd(a, r) = G 가 된다.
a = GA이고, r = G(B - Aq) 이므로 
A와 B - Aq가 서로소이면 증명이 끝난다.

gcd(A, B - Aq) = m 이라고 가정하고 이를 만족하는 적당한 서로소를 k, l 이라고 해보자.
그럼 A = mk, B - Aq = ml 이 성립한다.
B = Aq + ml 이고, A = mk 이므로 B = mkq + ml = m(kq + l) 이 성립한다.
즉, B = m(kq + l) 이므로 m은 A와 B의 공약수이다.

하지만 맨 위에서 A와 B는 서로소라고 했으니 m = 1 이되므로
A와 B - Aq 역시 서로소가 된다.

따라서 gcd(a, b) = gcd(a, r) 이 성립된다.

증명 끝!

굉장했다.

증명은 나무위키 에서 보고 참고했다.

실제 알고리즘은 위에 증명에 비하면 너무너무너무 간단하다.

b = aq + r (0 <= r < q) 만 이용하면 된다.

48, 60 을 가지고 구해보자.

b = aq + r 을 이용하여

60 = 48 * 1 + 12

48 = 12 * 4 + 0

음?! 너무 간단하게 나왔다.

12가 최대 공약수임을 알았다.

다시, 좀 더 복잡한 95, 250 을 가지고 해보자.

250 = 95 * 2 + 60

95 = 60 * 1 + 35

60 = 35 * 1 + 25

35 = 25 * 1 + 10

25 = 10 * 2 + 5

10 = 5 * 2 + 0

최대 공약수는 5가 되겠다.

이제 위 과정을 일반화를 통해 알고리즘을 구현해 보자.

gcd(95, 250)에서 a = 95, b = 250 이다.

250 % 95 -> 60 이므로 r = 60 이 된다.

즉, gcd(95, 250) = gcd(95, 60) 과 같다.

근데, (60, 95) 에 대한 최대 공약수나, (95, 60) 에 대한 최대 공약수나 똑같다. 

gcd(95, 60) 이나 gcd(60, 95)나 똑같다는 의미이다.

그럼, 다음 식을 보자.

gcd(60, 95) 에서 a = 60, b = 95 이다.

95 % 60 -> 35 이므로 r = 35 이다.

즉, gcd(60, 95) = gcd(60, 35) = gcd(35, 60) 이다.

다음 식은

60 % 35 -> 25 이므로

gcd(35, 60) = gcd(35, 25) =  gcd(25, 35) 이고,

35 % 25 -> 10 이므로

gcd(25, 35) = gcd(25, 10) = gcd(10, 25) 이고...

25 % 10 -> 5 이므로

gcd(10, 25) = gcd(10, 5) = gcd(5, 10) 이고

10 % 5 -> 0 이므로

최대 공약수는 5 가 된다.

요약하면 gcd(95, 250) = gcd(5, 10) 과 같은 것이다.

그럼, 위 과정을 일반화 해서 보면

gcd(a, b) 는 다음 단계에서 gcd(b %a, a) 가 된다는 걸 알 수 있다.

하지만 b % a 가 0일 경우, 우리는 최대 공약수를 찾았으므로 a 를 반환하면 된다.

구현해보자!

JavaScript

var eu = function(a, b) {
  return b % a ? eu(b % a, a) : a;
}

Java

...
public int eu(int a, int b) {
    return b % a != 0 ? eu(b % a, a) : a;
}

참고로 최소 공배수는 유클리드 호제법을 안다면 굉장히 간단하게 구할 수 있다.

lcd(a, b) = a * b / gcd(a, b) 이다.

직접 구현해보기 바란다.