유클리드 호제법

유클리드 호제법이란?

두 양의 정수 A, B (A>B)에 대하여 A=Bq+r, (0<=r<B)라 하면, A, B의 최대공약수는 B, r의 최대공약수와 같다.

즉, GCD(A,B) = GCD(B,R).

<증명>

G가 최대공약수라고 하면

A = aG, B = bG (a, b는 서로소)

A = q*B + r

aG = g*bG + r

r = (a-gb)G

r = (a-gb)G, B = bG 이 둘의 최대공약수가 G임을 확인하면 된다.

즉, (a-gb)와 b가 서로소임을 보이면 된다.

- 귀류법 이용 (결론을 부정하면 모순이 나온다는 사실로 원명제가 참임을 증명하는 방법)

if) b와 a-bq가 서로소가 아니다 (a, b는 서로소)

a-qb = mp    b = np    // 서로소임을 부정했기 때문에 공통 약수 p를 가지고 있을 것

a-q*np = mp

a = (nq+m)p

a = (nq+m)p

b = np

위에 따라 a와 b는 공약수 p를 갖게 되어 모순이 발생했으므로

a와 a-bq가 서로소임이 증명된다.