유클리드 호제법, 이해하기

1. 정의

A = Bq + R일 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

위의 정의를 활용하면 연쇄적인 나눗셈으로 A,B의 최대공약수를 소인수 분해 없이 구할 수 있다.

2. 구현

개발 언어로 이를 구현하기 위해서는 %(mod) 연산자를 알고 있어야 한다. A%B의 결과값은 A를 B로 나누었을 때, 나머지를 반환한다.
큰 수를 A, 작은 수를 B라고 해보자.

1️⃣ 큰 수를 작은 수로 나누고 나머지를 얻는다. 이때 나머지를 R이라 하자.

A % B = R

2️⃣ 작은 수를 나머지로 나눈다. 이때 나온 나머지 값을 R'라고 하자.

B % R = R'

3️⃣ 2번을 작은수가 나머지로 나누어 떨어질 때까지 반복한다.

R % R' = 0

4️⃣ 작은 수를 나누어 떨어지게 만든 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를 최대공약수로 공유한다.