纯数学方法证明辗转相除法（欧几里得算法）：gcd(a,b)=gcd(b,a%b)
1、首先 设gcd(a,b)=gcd(b,a%b)=d
2、 构造k与c 得到a=kb+c
其中c=a%b k=
⌊
a
b
⌋
\lfloor\frac{a}{b}\rfloor
⌊ba⌋
证明gcd(a,b)=gcd(b,a%b)=d 的问题转化为证明 gcd(a,b)=gcd(b,c)=d
则有 a=
⌊
a
b
⌋
\lfloor\frac{a}{b}\rfloor
⌊ba⌋*b+c
3、等式两边同除d 得
a
d
=
b
d
∗
⌊
a
b
⌋
+
c
d
\frac{a}{d}=\frac{b}{d}*\lfloor\frac{a}{b}\rfloor+\frac{c}{d}
da=db∗⌊ba⌋+dc
移位得
a
d
−
b
d
∗
⌊
a
b
⌋
=
c
d
\frac{a}{d}-\frac{b}{d}*\lfloor\frac{a}{b}\rfloor=\frac{c}{d}
da−db∗⌊ba⌋=dc
4、因为d为a b最大公因子，且k=
⌊
a
b
⌋
\lfloor\frac{a}{b}\rfloor
⌊ba⌋ 为整数，则有等式左边为 整数-整数，显然等式右侧一定为整数
则
c
d
\frac{c}{d}
dc为整数。那么d为c的因子。
现在我们证明了d为c b的公因子，接下来证明他为最大公因子
5、我们使用反证法：假设存在D>d,D为c b更大的公因子，那么D可以被c整除 也可以被b整除 D|c D|b
又因为a=kb+c 所以D|(kb+c) D能被a整除，那么D为a b的公因子，并且大于d,则D将成为a b的最大公因子，与题目假设相违背
6、因此我们证得d为c d的最大公因子，gcd(a,b)=gcd(b,a%b)=d
结束 wink~
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
