最大公因数 Great Common Divisor

对于 a,b∈Za,b\in \mathbb Z 不为0，那么ab的最大公因数为 gcd(a,b)\text{gcd(a,b)} 或者简写为 (a,b)(a,b) 且常用字符 dd 表示，即 d ∣ ad\ |\ a, d ∣ bd\ |\ b (我们可以用 d ∣ m∧d ∣ r⇒d ∣ gcd(m,r)d\ |\ m \land d\ |\ r \Rightarrow d\ |\ gcd(m,r))
如果有常数 c ∣ a∧c ∣ bc\ |\ a\land c\ |\ b 那么有 c ∣ dc\ |\ d

常见原理证明

原理1

对于 m,n∈N\{0}m,n\in \mathbb N\backslash\{0\} 如果 m ∣ nm\ |\ n 那么 gcd(n,m)=mgcd(n,m) = m

原理2

对于 m,n∈N\{0}m,n\in\mathbb N\backslash\{0\} 如果 n=qm+rn = qm + r 且 q≥0,0≤r<mq\ge 0,0\le r<m 那么 gcd(n,m)=gcd(m,r)gcd(n,m) = gcd(m,r)

欧几里得算法（辗转相除法）

对于正整数 nn 和 mm，我们可以通过欧几里得整除法求得 gcd(n,m)gcd(n,m)

n=mq1+r1,0<r1<mn = mq_1 + r_1, 0 < r_1 < m

m=r1q2+r2,0<r2<r1m = r_1q_2 + r_2, 0 < r_2 < r_1

r1=r2q3+r3,0<r3<r2r_1 = r_2q_3 + r_3, 0 < r_3 < r_2

⋮\vdots

rk−2=rk−1qk+rk,0<rk<rk−1r_{k-2} = r_{k-1}q_k + r_k, 0 < r_k < r_{k-1}

rk−1=rkqk+1r_{k-1} = r_kq_{k+1}

那么 gcd(n,m)=rk\text{gcd}(n,m) = r_k

证明方法

我们可以递归使用上述的原理1，2

丢番图方程 Diophantine Equation

对于 a,b,c∈Za,b,c\in \mathbb Z 我们有 ax+by=cax + by = c 的解 x,yx,y 可以通过欧几里得算法求得，但是我们需要满足 c ∣ gcd(a,b)c\ |\ gcd(a,b)

例子

对于丢番图方程 42823x+6409y=1742823x + 6409y = 17, 其中 17=gcd(42823,6409)17 = gcd(42823,6409)
那么，首先由 42823=6409×6+436942823 = 6409 \times 6 + 4369, 6409=4369×1+20406409 = 4369\times 1 + 2040, 4369=2040×2+2894369 = 2040\times 2 + 289, 2040=289×7+172040 = 289\times 7 + 17, 289=17×17+0289 = 17\times 17 + 0
那么我们再反着来就能返回到 6409 和 42823
17=2040−289×7=2040−(4369−2040×2)×7=2040×15−4369×717 = 2040 - 289 \times 7 = 2040 - (4369 - 2040\times 2)\times 7 = 2040\times 15 - 4369\times 7 17=(6409−4369)×15−4369×717 = (6409 - 4369)\times 15 - 4369 \times 7
最后化简得到 6409×147−42823×226409\times 147 - 42823 \times 22

丢番图方程的停止条件是达到最大公约数的情况，即 r=gcdr = gcd