1. 정의
A = Bq + R일 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
위의 정의를 활용하면 연쇄적인 나눗셈으로 A,B의 최대공약수를 소인수 분해 없이 구할 수 있다.
2. 구현
개발 언어로 이를 구현하기 위해서는 %(mod) 연산자를 알고 있어야 한다. A%B의 결과값은 A를 B로 나누었을 때, 나머지를 반환한다.
큰 수를 A, 작은 수를 B라고 해보자.
1️⃣ 큰 수를 작은 수로 나누고 나머지를 얻는다. 이때 나머지를 R이라 하자.
A % B = R2️⃣ 작은 수를 나머지로 나눈다. 이때 나온 나머지 값을 R'라고 하자.
B % R = R'3️⃣ 2번을 작은수가 나머지로 나누어 떨어질 때까지 반복한다.
R % R' = 04️⃣ 작은 수를 나누어 떨어지게 만든 R'는 유클리드 호제법을 따라 거슬러 올라가면 우리가 처음에 알고자 했던 A와 B의 최대 공약수이다.
GCD(A,B) = R'3. 증명
(1) A와 B와 R이 같은 G를 공유하는가?
A = Ga, B = Gb (G가 최대공약수임으로, a와b는 서로소)
A = Bq + R 임으로,
R = G(a+bq)이다. 따라서 같은 G를 공유한다.(2) B와 R의 최대공약수도 G가 맞는가?
B와 R의 최대공약수도 G려면, 위의 식에서 b와 (a+bq)도 서로소여야 한다.
G가 최대공약수이면, B와 R을 동시에 나눌 수 있는 수는 모두 G에 합해져 있으므로 나머지인 b와 a+bq는 절대로 서로 나누는 수가 공유되어서는 안되기 때문이다.
귀류법을 사용하겠다.
귀류법은 결론을 부정했을 시 생기는 모순으로 원명제가 참임을 증명하는 방식이다.
G가 공약수가 아니라서 b와 a+bq 사이야 공약수가 m이 있다고 가정해보겠다.
b = mk
a+bq = mk'그러면 다음과 같은 모순이 생긴다.
a+bq = a+mkq = mk'
a = mk'-mkq
a = m(k'-kq)맨 위에서 a와 b는 서로소라고 했다.
만약 m >=2 이면 해당 전제와 모순된다. m = 1 이면, b와 a+bq는 모순된다.
따라서 b와 a+bq는 서로소이고, B와 R은 G를 최대공약수로 공유한다.
