学习笔记：证辗转相除法
chenxi797
·
·
算法·理论
辗转相除法是什么？
简单来说，是可以通过不断互相取余的算法求 \gcd(a,b) 的算法。即
\gcd(a,b) = \gcd(b,a \bmod b)
具体来说：
证明
要证明辗转相除法，只需要证明 \gcd(a,b) = \gcd(b,a \bmod b) 即可。
设 \gcd(a,b) = t，则有：
a = t \times m,b = t \times n
(m,n 为正整数)。
可以证明 m \bot n。
如何证明 m \bot n？
显然。
假设 \gcd(m,n) = d，d 为正整数且 d \ne 1。
则有：
m = d \times x,n = d \times y
则：
a = t \times d \times x,b = t \times d \times y
注意到此时 \gcd(a,b) = t \times d，与已设矛盾。
所以 m \bot n。
回到正题。
那么 a \bmod b 到底是什么呢？
实际上就是
a \bmod b = a - b \times \lfloor a \div b \rfloor
设 q = a / b，继续推导：
\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 \bmod b = t \times (m - n \times q) \\ b = t \times n
易证 n \bot (m - n \times q)。
什么，你问我怎么证出来的？？
为什么 n \bot (m - n \times q)？
跟上面的证明差不多。
假设 \gcd(n,m - n \times q) = d，d 为正整数且 d \ne 1。
则有：
n = d \times x,m - n \times q = d \times y
代入，得：
m - d \times x \times q = d \times y \Rightarrow m = d \times (y + q \times x)
又因为 n = d \times x，则 \gcd(m,n) = d，与前面 m \bot n 的已证不符。
所以 n \bot (m - n \times q)。
回到正题。
a \bmod b = t \times (m - n \times q) \\ b = t \times n
如果 n \bot (m - n \times q)，那么 \gcd(b,a \bmod b) = t。
最开始设的 \gcd(a,b) = t，那么得：
\gcd(a,b) = \gcd(b,a \bmod b)
证毕。