文章目錄
- 前言
- 補充：
- 輾轉法證明
- 總結：
前言
- 博主實力有限，博文有什么錯誤，望各位大佬，不吝賜教，非常感謝！
- 本文證明 求2數的最大公約數的輾轉相除法，
補充：
2數互質：公因數只有1的2個非0自然數，稱為互質，
如果 2個數a,b存在最大公約數 c即c=gcd(a,b)，(gcd是最大公約數的意思)
設 a = mc;b =nc;那么 m與n必
互質證明 如果 m，n不互質，那么m = pd;n=qd;可以知道 a= pdc; b= qdc; 因此 cd將會是 a,b的最大公約數，這與c是a，b的最大公約數相矛盾，因此 m，n互質，
輾轉法證明
a/b=x…y
a=xb+y;
輾轉法就是證明：gcd（a,b）=gcd(b,y);
設 a ，b的最大公約數是 c
a= m c;
y= c(m-nx);
y= c(m-nx);
我們分析 ： n與 m-nx 發現其互質，
證明：
n = qd；m-nx = pd；
因此 a= cd(qx+p);b =cdq;即 cd是 a,b的最大公約數，這與c是a,b的最大共約數矛盾，
因此 n,m-nx互質，這也說明 c也是 b,y的最大公約數，
因此 gcd(a,b)=gcd(b,y)成立，另外如果 b/y = q…r;
那么 gcd(a,b)= gcd(b,y)=gcd(y,r)…
這也就是 為什么 輾轉法要連續執行，直到 商為0.
總結：
| 補充部分的 m,n互質很關鍵， |
|---|
| 另外，2個數的最大共約數與最小公倍數 之積與2數的之積相同即 ab=pq； |
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/300513.html
標籤：其他
上一篇：微服務002服務呼叫
下一篇：計算機中整數的存盤與大小端