최대공약수 알고리즘

최대공약수

최대공약수는 두 정수의 공통된 약수 중 가장 큰 수를 의미한다.
최대공약수를 구하는 방법 중에서 유클리드 호제법을 이용하면 빠르게 구할 수 있다.

유클리드 호제법

유클리드 호제법이란, 2개의 자연수 a, b (a > b)에 대하여 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수와 b와 r의 최대공약수가 같다는 성질을 이용하여 두 자연수의 최대공약수를 구하는 알고리즘이다.

성질 증명

우선 위의 성질을 간단하게 증명해보면 아래와 같다.
$a, b \in \mathbb{Z}$이고,
$\, a \le {b}$라고 하자.
그러면, $\, a = bq + r$을 만족하는 유일한 정수 $\, q, r$이 존재한다.
이 때 $\, 0 \le r < b$이다.
이 때 $\,a$와 $\,b$의 최대공약수를 $\,d$라고 하면,
$\, a = d \alpha, \, b = d \beta$이고 $\, \alpha$와 $\,\beta$는 서로소이다.
따라서,
$a = bq + r$
$\Rightarrow d \alpha = d \beta q + r$
따라서 $\,r$은 $\,d$의 배수가 되어야 한다.
이제 $\,r = d \rho$라고 하자.
만약 $\, \beta$와 $\, \rho$가 1이 아닌 최대공약수가 존재한다면,
이를 $\,d'$라고 하면 $\, \beta = d' \beta' ,\, \rho = d' \rho'$ 라고 할 수 있다.
따라서,
$ d \alpha = d \beta q + d \rho$
$\Rightarrow d \alpha = d d' \beta' q + d d' \rho'$
$\Rightarrow d \alpha = d d' (\beta' q + \rho')$
$\Rightarrow \alpha = d' (\beta' q + \rho')$
즉, $\,\alpha$와 $\,\beta$는 모두 $\, d'$의 배수이므로 둘은 서로소가 아니게 되고, 이는 $\,a, b$의 최대공약수가 $\,d$라는 가정에 모순이다.
이로 인해 $\, \beta$와 $\, \rho$는 서로소임을 알 수 있다.
즉, $\, b$와 $\, r$의 최대공약수는 $\, d$로, $\, a$와 $\, b$의 최대공약수인 $\, d$와 같다.

알고리즘

위의 성질을 이용하여 두 자연수의 최대공약수를 둘 중 작은 수와 큰 수를 작은 수로 나눈 나머지의 최대공약수를 구하는 과정으로 치환하는 과정을 반복하면, 나머지는 결국 0으로 수렴할 것이므로 간단하게 최대공약수를 구할 수 있다.
이를 코드로 구현하면 아래와 같이 나타낼 수 있다.

int gcd(int a, int b) {
    int big = (a > b) ? a : b;
    int small = (a + b) - big;

    if (small == 0) {
        return big;
    }
    else {
        int r = big % small;
        return gcd(small, r);
    }
}

Reference

• https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95