유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나입니다. 호제법互除法이라는 한자어에서 볼 수 있듯, 몫과 나머지를 서로(互) 나누어(除) 최대공약수를 구하는 알고리즘 입니다.
정리
이고, 를 로 나눈 나머지가 이라고 하자. (여기서 이고, 은 인 정수.)
※ 피제수a와 제수b는 정수Z이고 피제수a는 제수b보다 크거나 같고, 나머지r는 0보다 크거나 같고 제수b보다 작다.
와 의 최대공약수를 라고 하면, 다음이 성립한다.
※ 피제수a 제수b의 최대공약수는 제수b와 나머지r의 최대공약수와 같다.
증명
이고, 라고 하자.
그러면, 을 만족하는 유일한 정수 이 존재한다. 이때, 이다.
라고 하자. 즉, 와 는 서로소이다.
(즉, 은 의 배수)
이제, .라고 하자. 여기서 와 가 서로소라면, 와 의 최대 공약수도 가 된다.
만약 (서로소가 아닌 수, 즉 다른 공약수를 가지는 수)라면, 으로 두었을 때,
이 되므로, 이다. (즉, 는 의 배수)
즉, 가 되어 와 는 서로소라는 것에 모순이다. 이는 라는 가정에서 나타나는 모순이므로 (즉, β와 p는 서로소)이다.
따라서 곧 라는 것이다.
※ a와 b의 최대공약수 d가 있다고 할때 dα = dβ + r이고, (α,β)=1 서로소이다. 따라서 r도 d의 배수여야 한다. r=dρ
이때 (β,ρ)>1 즉 다른 나누어지는 수 d'가 있다면 α,β가 서로소라는 가정에 모순이기에 (β,ρ)=1 서로소이다. 따라서 (dβ,dρ)=(b,r)=d=(a,b)이다.
구현
그렇다면 프로그래밍 언어로 어떻게 구현할 수 있을까요? 먼저 큰 숫자의 최대공약수를 구하는 예제를 봅시다.
a = b × q + r
78696 = 19332×4 + 1368
19332 = 1368×14 + 180
1368 = 180×7 + 108
180 = 108×1 + 72
108 = 72×1 + 36
72 = 36×2 + 0
규칙을 찾으셨나요?
a와 b의 최대공약수는 상대적으로 작은 b와 r의 최대공약수와 같기 때문에 b와 r의 최대공약수를 찾을 때까지(나머지r이 0이 될때까지) 반복합니다.
나머지가 0으로 떨어질때까지 gcd
를 재귀적으로 호출하는 방법으로 구현해봅시다!
// c/c++
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
유클리드 호제법을 bitwise shift를 사용해 더 빨리 계산하는 binary GCD 알고리즘도 있습니다!