集合I={ax-by|x,y∈Z}を考える。
I≠φ,{0}なのでIには絶対値が最小の0でない元d=ax'-by'が存在する。
d∈Iならば-d∈Iであるから始めからd>0と仮定してよい。
ここでm=ax''-by''∈Iをとるとm=dq+rを満たす整数qとd(0≦r<d)が存在する。
r=m-dq=ax''-by''-(ax'-by')q=a(x''-qx')-b(y''-qy')はIの元なので
dの定義よりr=0でなければならない。よってI={kd|k∈Z}
ここで明らかにa,b∈Iなのでdはa,bの公約数である
よってd=1よりax'-by'=1