|
|
【定理】若\(\gcd(u,v)=d>0,\) 则有整数\(s,t\)使\(su+tv=d\).
【证明】考虑集合\(S=\{m=au+bv\mid a, b\in\mathbb{Z},m>0\}.\) 易
\(\qquad\)见\(|u|=(\frac{|u|}{u})u{\small+0}v{\scriptsize\in S,\,S\ne\varnothing,}\,\exists s,t\in\mathbb{Z}\,(su+tv=\min S)\)
\(\qquad\)取整数\(m,r\)使\(u=m\min S+r\,(0\le r<\min 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\)但显然\(\gcd(u,v)\small\mid\min S.\) 故\(\exists s,t{\small\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\)
|
|