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)로, 증명이 끝난다.