\[ 設(shè)c=gcd(a,b)，那么a可以表示為mc，b可以表示為nc的形式。然后令a=kb+r，那么我們就\\ 只需要證明gcd(b,r)=c即可。{\because}r=a-kb=mc-knc，{\therefore}gcd(b,r)=gcd(nc,mc-knc)\\ =gcd(nc,(m-kn)c)，所以我們只需要證gcd(n,m-kn)=1即可。\\ 設(shè)n=xd,m-kn=yd，那么m=kn+yd=kxd+yd，進(jìn)而a=(kx+y)cd,b=xcd\\ ，于是gcd(a,b)就可以表示為gcd((kx+y)cd,xcd)=cd，如果要讓它等于c，那么d=1，即\\ gcd(n,m-kn)=1。 \]

放上模板代碼：

int gcd(int a,int b){if(!b) return a;return gcd(b,a%b); } //壓行之后: int gcd(int a,int b){ return b?gcd(b,a%b):a; }

轉(zhuǎn)載于:https://www.cnblogs.com/akura/p/11088720.html

總結(jié)

以上是生活随笔為你收集整理的与数论的厮守05:gcd(a,b)=gcd(b,a mod b)的证明的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。