유클리드 호제법

GCD (최대 공약수) 구하기
a, b 자연수의 최대 공약수 d를 구하라.

 

1234, 56789의 최대 공약수를 구한다고 했을 때, 숫자가 커짐에 따라 소인수분해가 쉽지 않아진다.

 

쉽게 하는 방법 : 유클리드 호제법 알고리즘
(명시적으로 기술된 가장 오래된 알고리즘, 쉽다.)

a, b의 최대 공약수를 (a, b)라고 하면 (a, b) = (b, r). (r은 a를 b로 나눈 나머지)

 

r은 a를 b로 나눈 나머지 임으로 a = bx + r이라고 했을 때,

a, b의 최대 공약수 d를 이용하여 풀어 쓰면 d(a1) = d(b1)x + r 가 된다.

이는, d(b1)x 와 나머지 r을 더했을 때 결국 d(a1), d와 무언가(a1)가 곱해진 수가 된다는 말이 된다.

따라서 d(a1) = d(b1)x + d(r1)과 같이 쓸 수 있다.

 

d를 소거하면 a1 = (b1)x + r1.

유클리드 호제법은 위 식의 양 항을 d1(a2) = d1(b2)x + d1(r2)와 같이 더 분해될 수 없음을 증명한다.

 

세부 증명 요약 : 최대 공약수 d로 분해함에 따라 a1, b1이 서로소가 되는데 이를 d1으로 더 분해하기는 불가능하다.

세부 증명은 생략하고 d(a1) = d(b1)x + d(r1) 식에서 d보다 더 큰 값으로 분해되지 않는다는 사실에만 주목하자.

더 큰 값으로 분해 될 수 없다 === 최대 공약수

따라서 d(b1)x와 d(r1)의 최대 공약수는 d가 된다.

(앞에서 d는 a, b의 최대 공약수로 설정한 것이다. d(b1)x와 d(r1)의 최대 공약수 또한 d가 됨을 증명한 부분)

이는 최초의 식 a = bx + r에 대입하여 이야기 하면

bx와 r의 최대 공약수는 d가 된다는 말이 된다.

 

그런데 bx와 r의 최대 공약수를 구하는 것은 a, b 의 최대 공약수 구하는 것보다 더 어렵다.

x와 r, 즉 x와 d(r1)이 서로소 임에 주목하자. x의 약수는 이미 최대 공약수 d를 결정지을 때 d에 포함되며 x의 약수가 r1의 약수에 존재한다면 최대 공약수는 d * x의 약수가 되어야 하기 때문이다.

 

앞에서 bx와 r의 최대 공약수는 d가 되지만 복잡했었는데 x와 r이 서로소라면 bx와 r의 최대 공약수 d를 결정하는데에는 상관이 없는 요소가 된다. 따라서 b와 r의 최대 공약수 만으로 bx와 r의 최대 공약수 d, a와 b의 최대 공약수 d를 구할 수 있다.

 

a, b의 최대 공약수를 (a, b)라고 하면 (a, b) = (b, r). (r은 a를 b로 나눈 나머지)