\(\huge^\star\text{ Bézout's Identity}\)

elim

【定理】若\(\gcd(u,v)=d>0,\) 则有整数\(s,t\)使\(su+tv=d\).
【证明】考虑集合 \(\small S=\{m=au+bv\mid a, b\in\mathbb{Z},m>0\}.\) 易见
\(\qquad\,|u|=(\frac{|u|}{u})u\small+0v\in S,\,S\ne\varnothing,\,\exists s,t\in\mathbb{Z}\,(su+tv=\min S)\)
\(\qquad\)取整数\(m,r\)使 \(u=m\min{\small S}+r\,(0\le r<\min{\small S})\). 于是
\(\qquad\,0\le r=(1-ms)u+(-mt)v<\min S.\) 由\(S\)的定义知
\(\qquad\,r=0,\min S\mid u\). 同理\(\min S\mid v.\) 进而\(\min S\mid\gcd(u,v)\).
\(\qquad\)但显然 \(\small\gcd(u,v)\mid\min S.\) 故 \(\small\exists s,t \in\mathbb{Z}:\, \gcd(u,v)=su+tv.\)
【推论】若\(\gcd(p,a)=1,\,p\mid ab,\) 则 \(p\mid b\).
【证明】取 \(s,t\) 使 \(sp+ta=1\) 则 \(p\mid (sb)p+t(ab)=b.\quad_\blacksquare\)
【注记】若\(\gcd(p,q)=1, q\mid p^n\). 反复应用上述推论得\(q\mid p\),
\(\qquad\)若\(q\)是正整数, 那么它就是\(p,q\)的最大公因数\(\gcd(p,q)=1.\)