유클리드 호제법 정리 / 증명

알고있던 유클리드의 호제법이 생각이 나지 않아서 다시 한번 정리 해둔다.(열강 도전 프로그래밍 ONE을 보다가)

유클리드 호제법이란.
A >= B인 어떤 두 정수 A와 B가 있을 때(A = Bq + r로 나타낼 수 있다.)
A와 B의 최대공약수 gcd(A, B) = d는 gcd(B, r)과 같다.
즉, 쉽게 말하면 두 수의 최대공약수는 "큰 수를 작은 수로 나눈 나머지"와 "작은 수"의 최대공약수와 같다는 것이다.

증명.
gcd(A, B) = d에 의해서 A = ad, B = bd (따라서 a와 b는 서로소이다.)
A = Bq + r 이므로 r = A - Bq = ad - bdq = (a-bq)*d 이다.

여기서 B = bd 와 r = (a-bq)d이므로 d는 B와 r의 공약수 중 하나라는 것을 알 수 있다.
B와 r의 최대공약수를 c라 하면 c >= d 라 할 수 있다.

B = cs, r = ct라 하면 (s, t도 서로소)
A = Bq + r = csq + ct = (sq+t)c 이다.
c는 A와 B의 공약 수 중 하나라는 것을 알 수 있다.
따라서 c는 A와 B의 최대 공약수인 d의 약수이고 d >= c 임을 알 수 있다.

따라서 c >= d 이고 d >= c 이므로 d = c 라는 결론을 얻게 된다.
즉 gcd(A, B) = gcd(B, r)이다.

알고리즘
#include <stdio.h>

void gcd(int, int);

void main()
{
    int num1, num2;
    scanf("%d %d", &num1, &num2);
    num1 > num2 ? gcd(num2, num1) : gcd(num1, num2);
    return;
}

void gcd(int n1, int n2)
{
    if(n2 % n1 == 0)                //A가 B로 나누어지면 B가 최대공약수
    {
        printf("%d", n1);          
        return;
    }
    else
        gcd(n2%n1, n1);         //나누어 떨어지지 않을 경우 b와 r의 최대공약수를
}