최대공약수 정리

Theorem. 주어진 $a,b\in \mathbb{Z}$에 대하여 a,b가 둘 다 0이 되지 않을 때,

$$\exists x,y \in \mathbb{Z} \quad \mathrm{such \ that} \quad \gcd (a,b) = ax+ by$$

$$S = \{ au +bv | au+bv > 0 , \; u,v\in \mathbb{Z} \}$$

존재성을 보이기 위해 WOP를 적용해야 할 것을 생각하면서 위 집합을 잡아줄 수 있다. 이 집합이 공집합이 아니라는 것은 다음과 같이 간단한 것을 생각해주면 알 수 있다.

$$\mathrm{take} \; u = b , \quad v= -a + sgn (1)$$

공집합이 아닌 자연수로 이루어진 집합이므로 Well Ordering Principle을 적용해서

$$\mathrm{Let} \quad d = \min S, \quad \mathrm{claim} \quad d = gcd(a,b)$$

claim이 참인 것을 보이기 위해서는 d가 a와 b의 공약수이고, 그 중에서도 가장 크다는 것을 보이면 된다.

d가 a의 약수인 것을 먼저 보이자. 직접 증명은 힘들기 때문에 Division Algorithm에 의해 a를 다른 값으로 나타내면

$$\exists ! q,r \in \mathbb{Z}, \; 0 \le r < d, \quad a = dq + r$$

d = ax+by 로 놓았을 때

$$r = a - dq = a - (ax+by)q = (1-qx)a - bqy, \quad 0 \le r < d$$

만약 r>0이라면 $r \in S$인데 $r < d$이므로 d의 정의에 모순이다.

따라서 r=0이고 $d|a$이다. 같은 방법으로 $d|b$이므로 d는 a와 b의 공약수이다.

a와 b의 공약수 c를 생각했을 때 $c|ax+by = d$이므로 d는 c보다 언제나 크거나 같다. 따라서 d는 gcd(a,b)로, 증명이 끝난다.