专栏文章

学习笔记：证辗转相除法

cchenxi797
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5hz95
此快照首次捕获于
2025/12/02 13:41
3 个月前
此快照最后确认于
2025/12/02 13:41
3 个月前
查看原文

辗转相除法是什么？

简单来说，是可以通过不断互相取余的算法求 gcd⁡(a,b)\gcd(a,b) 的算法。即
gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b,a \bmod b)
具体来说：

证明

要证明辗转相除法，只需要证明 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b,a \bmod b) 即可。
设 gcd⁡(a,b)=t\gcd(a,b) = t，则有：
a=t×m,b=t×na = t \times m,b = t \times n
(m,nm,n 为正整数)。
可以证明 m⊥nm \bot n。

如何证明 m⊥nm \bot n？

显然。
假设 gcd⁡(m,n)=d\gcd(m,n) = d，dd 为正整数且 d≠1d \ne 1。
则有：
m=d×x,n=d×ym = d \times x,n = d \times y
则：
a=t×d×x,b=t×d×ya = t \times d \times x,b = t \times d \times y
注意到此时 gcd⁡(a,b)=t×d\gcd(a,b) = t \times d，与已设矛盾。
所以 m⊥nm \bot n。

回到正题。
那么 a mod ba \bmod b 到底是什么呢？
实际上就是
a mod b=a−b×⌊a÷b⌋a \bmod b = a - b \times \lfloor a \div b \rfloor
设 q=a/bq = a / b，继续推导：
a mod b=a−b×q=t×m−t×n×q=t×(m−n×q)\begin{aligned} a \bmod b &= a - b \times q \\ &= t \times m - t \times n \times q \\ &= t \times (m - n \times q)\end{aligned}
注意到：
a mod b=t×(m−n×q)b=t×na \bmod b = t \times (m - n \times q) \\ b = t \times n
易证 n⊥(m−n×q)n \bot (m - n \times q)。
什么，你问我怎么证出来的？？

为什么 n⊥(m−n×q)n \bot (m - n \times q)？

跟上面的证明差不多。
假设 gcd⁡(n,m−n×q)=d\gcd(n,m - n \times q) = d，dd 为正整数且 d≠1d \ne 1。
则有：
n=d×x,m−n×q=d×yn = d \times x,m - n \times q = d \times y
代入，得：
m−d×x×q=d×y⇒m=d×(y+q×x)m - d \times x \times q = d \times y \Rightarrow m = d \times (y + q \times x)
又因为 n=d×xn = d \times x，则 gcd⁡(m,n)=d\gcd(m,n) = d，与前面 m⊥nm \bot n 的已证不符。
所以 n⊥(m−n×q)n \bot (m - n \times q)。

回到正题。
a mod b=t×(m−n×q)b=t×na \bmod b = t \times (m - n \times q) \\ b = t \times n
如果 n⊥(m−n×q)n \bot (m - n \times q)，那么 gcd⁡(b,a mod b)=t\gcd(b,a \bmod b) = t。
最开始设的 gcd⁡(a,b)=t\gcd(a,b) = t，那么得：
gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b,a \bmod b)
证毕。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...