[수학알고리즘] 유클리드 호제법

이 글에서는 유클리드 호제법의 증명과 원리를 다룹니다.

유클리드 호제법은 최대공약수/최소공배수를 구하는 데 쓰이는 알고리즘 입니다.
그러면, 유클리드 호제법을 알아보기 전에 최대공약수에 대해 알아봅시다.

일단 여기서 다루는 모든 수는 자연수라고 가정해봅시다.
자연수는 약수를 갖고 있습니다. n을 i로 나누었을 때 나누어 떨어진다면, “i는 n의 약수다” 라고 합니다.
이것은 간단하게 n%i == 0 로 나타낼 수 있습니다.
다음으로, 숫자가 1개가 아니라 2개가 있고, 그 두 수를 a, b라 합시다.
그러면 a의 약수 그룹(집합)과 b의 약수 그룹이 생깁니다. 그 중 겹치는 요소들(교집합)을 공통의 약수라 해서 공약수라고 합니다. 숫자가 3개가 있다면 그 3개의 수의 공통된 약수가 공약수가 되겠죠.

최대 공약수는 공약수들 중 최대값을 말합니다. 24와 16의 최대 공약수를 구해봅시다.
일단 24의 약수들은 {1, 2, 3, 4, 6, 8, 12, 24}이고, 16의 약수들은 {1, 2, 4, 8, 16)입니다.
공약수는 {1, 2, 4, 8}이 됩니다. 공약수들 중 최대값, 즉 최대 공약수는 8이 됩니다.

다음 단계로 넘어가서 최대 공약수의 성질을 살펴봅시다.
숫자 A, B의 최대 공약수를 G라고 합시다.
그러면 A, B는 G와 임의의 자연수 a, b를 이용해 다음과 같이 나타낼 수 있습니다.
A = Ga
B = Gb
그리고, G는 최대 공약수이기 때문에 a와 b의 최대 공약수는 1이고, 이 관계를 서로소 라고 합니다.

A ± B = G(a ± b)이기 때문에 G는 여전히 A와 B를 더하거나 뺀 값의 약수입니다.
A ≥ B라고 가정하고 A를 B로 나누어봅시다.
이 때, 몫을 Q, 나머지를 R이라고 합시다.
A = BQ + R
Ga = GbQ + R
Ga - GbQ = R
R = G(a - bQ)
즉, G는 A를 B로 나눈 나머지의 약수이며, 이 특징이 유클리드 호제법의 핵심입니다.

이제 유클리드 호제법에 대해 알아봅시다.

유클리드 호제법은 기원전 300년경에 쓰인 유클리드의 <원론> 제 7권, 명제 1~3번에 해당합니다.

실행 순서는 다음과 같습니다.

두 수 (a, b)를 입력받습니다. (단, a > b)
b가 0이라면 a를 출력하고 알고리즘을 종료합니다.
그렇지 않다면, (a, b)에 (b, a%b)를 대입한 뒤, 2번으로 돌아갑니다. 유클리드 호제법은 손으로 직접 최대 공약수를 구할 때 수를 점점 줄이면서 계산을 쉽게 하도록 도와주며, 이 점으로 인해 재귀함수로 구현 시 종료 조건 지정도 편해집니다.
a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대 공약수가 일치하기 때문에 이 알고리즘이 정당합니다.

이제 코드로 구현해봅시다.

//c언어
int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a%b);
}

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

//js
function gcd(a, b){
    if(!b) return a;
    return gcd(b, a%b);
}

#python
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)