알고리즘을 풀다보면 최대공약수를 구할 수 있는지 요구하는 문제가 많다. 딱히 알고리즘이 아니더라도, 코딩을 하다보면 최대공약수가 필요한 경우가 많다.
이럴때 쓰이는 알고리즘이 유클리드 호제법이다.
\(a, b ∈ Z\)이고 \(a≥b\)라면 \(a = bq + r\)를 만족하는 유일한 정수 \(q, r\)이 존재한다.\((0≤r<b)\)
\(GCD(a, b) = d\)일 때, \(a\)와 \(b\)는 \(a = αd, b = βd\)로 표현이 가능하며 이 때 \(α\)와 \(β\)는 서로소이다.
위의 식 \(a = bq + r\)은 \(αd = βdq + r\)로 표현할 수 있으며, \(r = (α – βq)d\)가 된다.
\(b = βd, r = (α – βq)d\)에 의해 \(d\)는 \(r\)과 \(b\)의 공약수 중 하나라는 것을 알 수 있다. 이 때 \(b\)와 \(r\)의 최대공약수를 \(c\)라고 하면 \(c≥d\)임을 알 수 있다.
\(b = mc, r = nc\) (\(m, n\)은 서로소)라 하면 위의 식 \(a = bq + r\)은 \(a = mcq + nc = (mq + n)c\)이다.
위에서 구한 두 식 \(b = mc\)와 \(a = (mq + n)c\)에 의해 \(c\)는 \(a, b\)의 공약수 중 하나라는 것을 알 수 있다.
따라서 \(c\)는 \(a, b\)의 최대공약수 \(d\)보다 같거나 작아야 한다. \((d≥c)\)
위에서 구한 두 식 \(c≥d, d≥c\)에 의해 \(c=b\)가 성립하고, 따라서 \(GCD(a, b) = GCD(b, r)\)이 성립한다.
예시로 1071과 1029의 최대공약수를 구해보자.
위의 증명에 따라 GCD(1071, 1029) = GCD(1029, 42) = GCD(42, 21) = GCD(21, 0)이 성립하고 GCD(X, 0) = X라는 성질에 의해 GCD(21, 0) = 21이다.
따라서 1071과 1029의 최대공약수는 21이다.
이 식을 코드로 표현하면 아래와 같다. gcd함수의 매개변수 x, y의 대소관계는 중요치 않은데, x < y라면 첫번째 루프를 돌면서 swap이 되므로, x > y가 되기 때문이다.
#include <stdio.h>
int gcd(int a, int b) {
int temp;
while (b) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
int main() {
int a = 1071, b = 1029;
printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
return 0;
}
gcd(1071, 1029) = 21
유클리드 호제법의 나머지 연산은 최악의 경우라도 b의 자릿수의 5배를 넘지 않는다는 것이 라메의 정리에 의해 증명되었다.
따라서 재귀적으로 프로그래밍을 해도 크게 문제가 되지 않는다.
int gcd(int a, int b){
return b ? gcd(b, a%b) : a;
}