[Algorithm] 유클리드 호제법 : 최대 공약수 찾기

유클리드 호제법

a, b의 최대공약수와 b, a%b의 최대공약수가 같다는 것을 사용하여 최대 공약수를 찾는다.

public static int gcd(int a, int b){
	if(a%b==0) return b;
    return gcd(b, a%b);
}

a%b가 0이 되는 경우, a가 b로 나누어떨어지는 것이므로, b가 최대공약수가 된다.

 

관련 문제로 백준의 <최대공약수와 최소공배수>가 있다.

2609번: 최대공약수와 최소공배수

 

 

증명

유클리드 호제법은 귀류법으로 증명할 수 있다.

f(a, b)는 최대공약수를 찾는 함수이다.

 

1.

a>=b일 때, a = bx + r 가 성립한다.

 

2.

f(a, b) = d 라고 하자.

a, b 둘 다 d의 배수 이므로

a = dp
b = dq
(이 때 d가 최대공약수이므로 p, q는 서로소)

 

따라서

a = bx + r  => dp = dqx + r

 

이고,

r = d(p-qx)

이므로 r은 d의 배수임을 알 수 있다.

 

3.

그럼 b와 r 모두 약수 d를 갖는다.

b = dq
r = dk

 

만일 d가 b, r의 최대 공약수가 아니라면, q와 k 사이에 1이 아닌 공약수가 있을 것이다.

그 최대 공약수를 d'라고 가정하자.

f(q, k) = d'

 

이에 따라

q = d'q'
k = d'k'

 

또한 성립한다.

 

4.

다시 a = bx + r 식으로 돌아가보자. 이 식을 지금까지 나온 변수들로 풀어 쓰면

a = bx + r
dp = dqx + dk
dp = dd'q'x + dd'k' = dd'(q'x+k')
p = d'(q'x +k')

가 성립한다. p는 d'의 배수이다. 아까 q도 d'의 배수라고 했다.

즉, p와 q가 서로소라는 명제에 모순이 생긴다!

 

이를 통해 아까의 'd가 b, r의 최대 공약수가 아니다' 라는 가정이 틀렸다는 것을 알 수 있다.

 

결론

- f(a, b) = d이고, a = bx + r일 때, r 또한 d의 배수이다. 즉 a, b, r은 같은 약수 d를 공유한다.

- b, r의 최대공약수 역시 d이다.

- f(a, b) = f(b, a%b) = d