04. 유클리드 호제법(Euclidean algorithm)

● 정의
- A = BQ + R 일 때, A와B의 최대공약수, B와 R의 최대공약수는 같다.

● 증명
① gcd(A, B)를 G라고 가정한다. ( A = aG, B=bG )
② A = BQ + R에 각각의 변수를 대응 시킨다. ( aG = bGQ + R )
③ (a - bQ)G = R 로 변환이 가능하며 A, B, R 은 모두 G의 배수라고 말할 수 있다. B=bg, R=(a - bQ)G 이므로 b와 (a - bQ)가 서로소이고 B와 R의 최대공약수가 G가 된다.
※ 증명
ⓐ b와 (a - bQ)가 서로소가 아니라고 가정한다. b = dn, (a - bQ ) = dm 그리고 이 식이 거짓임을 증명함으로써 b와 (a - bQ)가 서로소임을 증명한다.
ⓑ (a - (dn)Q) = dm => (a - dnQ) = dm => a = dm + dnQ => a = d( m + nQ )
ⓒ a = d( m + nQ ), b = dn 이므로 a와 b가 d 라는 공약수를 가지게 된다. 이것은 a와 b가 서로소라는 앞의 가정에 모순이 되기 때문에 b와 (a - bQ)는 서로소라는 것이 증명된다.

● 예제
Q. GCD(206, 40)을 구하라.

A. 2

GCD(206, 40) = GCD(40, 6)
= GCD(6, 4)

= GCD(4, 2)
= GCD(2, 0)
= 2