（觉得自己快没了，赶紧完成想做的事）
最大公约数是数论中很常见的一个知识。本文将从数学和信息学两个方面简单谈一下它。
从这里开始
带余数除法
定理1.1（带余数除法） 设$a, b$是两个给定整数，且$a
eq 0$，那么一定存在唯一的一对整数$q$和$r$，满足：
$b = qa + r, left0leqslant r < left | a ight |ight)$
此外，$amid b$的充分必要条件是$r = 0$。
证明 存在性 当$a mid b$的时候，取$q = b / a, r = 0$即可。考虑$a
mid b$的时候。
设$T = left { b – ka :kin mathbb{Z} ight }$。因为$a
eq 0$，所以不等式$b – ka > 0$总是有整数解的。根据最小自然数原理可知，必然存在最小的正整数$t_{0} = b – k_{0}a in T$
若$t_{0} < left | a ight |$，则取$q = k_{0}, r = t_{0}$。否则有$t_{0} > left | a ight |$，考虑$t_{0} – left | a ight |$，由$T$的定义知$t_{0} – left | a ight |in T$，再由$t_{0} > left | a ight |$可知$t_{0} – left | a ight | > 0$,因此$t_{0} – left | a ight |$是正整数，又因为$a
eq 0$，所以$t_{0} – left | a ight | < t_{0}$与$t_{0}$的最小性矛盾。因此必有$t_{0} < left | a ight |$。
唯一性 假设还存在一对整数$q’$和$r’$满足$b = q’a + r’, left0leqslant r’ < left | a ight |ight)$。若$q = q’$，则可以推出$r = r’$，因此$q
eq q’$。联立等式有$qa + r = q’a + r’$。移项得$q – q’)a = r – r’$，假设$r > r’$，则有$r – r’ geqslant a$，显然这是不可能的。所以唯一性得证。
然后来证明一下最后那一句话。充分性由整除定义可证。考虑必要性，因为$amid b$，所以$amid b – qa = r$，再由$0leqslant r < left | a ight |$，可知$r = 0$。
（虽然它很显然，但是很有必要证明一下）
带余数除法的一个重要的推广莫过于就是辗转相除法，也称Euclid算法。它不仅在理论中有很大的价值，而且在应用中也有举足轻重的地位。
辗转相除法 设$u_{0}, u_{1}$是两个给定整数，且$u_{1}
eq 0$。重复使用带余数除法可以得到下面若干等式：
$egin{matrix}u_{0} = q_{0}u_{1} + u_{2} &0 < u_{2} < left | u_{1} ight | \ u_{1} = q_{1}u_{2} + u_{3} &0 < u_{3} < u_{2}\ u_{2} = q_{2}u_{3} + u_{4} &0 < u_{4} < u_{3} \ cdots & cdots\ u_{k – 1} = q_{k – 1}u_{k} + u_{k + 1} & 0 < u_{k + 1} < u_{k} \u_{k} = q_{k}u_{k + 1} end{matrix}$
用程序写，就是：
1 int gcdint a, int b) { 2 return b) ? a) : gcdb, a % b)); 3 }
那么它能做什么？
引理1.2 1)$a, b) = a, b – a)$2)设$b = qa + r, 0leqslant r < left| a ight|$，a, b) = b, r)。
证明 1)设$d mid a$且$d mid b$，则$d mid b – a$。
设$d mid b – a$且$d mid a$，则$d mid b$。
因此$a,b$的公约数集合与$a, b – a$的公约数集合相同。
由定义可知$a, b) = a, b – a)$。
2)由1)易证。
定理1.3 在辗转相除法中，$u_{k + 1} = u_{0}, u_{1})$。
证明 由引理1.2易证。
于是它可以用来求两个数的最大公约数，如果把它推广到求多个数的最大公约数还需要一些数学定理。
最大公约数理论
定理2.1 $a_{i}mid c$的充分必要条件是$[a_{1}, a_{2}, cdots, a_{k}]mid c$。
定理2.2 设$D$为正整数，那么$D = a_{1}, a_{2}, cdots, a_{k})$的充分必要条件是$Dmid a_{i}$且对于任意满足$dmid a_{i}$的$d$，则有$dmid D$。
定理2.3 $a_{1}, a_{2}, cdots, a_{k}) = a_{1}, a_{2}), a_{3}, cdots, a_{k})$。
定理2.4 设$a_{1}, a_{2}, cdots, a_{k}$是不全为0的整数。则$a_{1}, a_{2}, cdots, a_{k}) = minleft {s = a_{1}x_{1} + a_{2}x_{2} + cdots + a_{k}x_{k}:x_{i}in mathbb{Z}wedge s > 0ight }$。
定理2.5 若$a, b) = 1, amid mb$，则$amid m$。
定理2.6 若正整数$mmid a_{i}, i = 1, 2, cdots, k$, $a_{1}/m, a_{2}/m, cdots, a_{k}/m) = a_{1}, a_{2}), a_{3}, cdots, a_{k})/m$。
（注：《初等数论》上，此章有8个定理，这里只选取与本文有关的6个定理）
定理2.1的证明 充分性显然。考虑证明必要性。
设$L = [a_{1}, a_{2}, cdots, a_{k}]$。由带余数除法可知，存在唯一的整数$q, r$满足：
$c = qL + r, 0leqslant r < L$
因为$a_{i}mid c, a_{i} | qL$，所以$a_{i} | c – qL = r$，因此$r$是$a_{1}, a_{2}, cdots, a_{k}$的公倍数。由定义可知$r = 0$。因此$Lmid c$。
这一条定理揭示了最小公倍数的本质属性：公倍数一定是最小公倍数的倍数。
定理2.2的证明 充分性 由$Dmid a_{i}$可知$D$是$a_{1}, cdots, a_{k}$的公约数，再由$D$是正整数，任意满足$dmid a_{i}$的$d$，则有$dmid D$可知，$dleqslant D$。由定义可知$D = a_{1}, a_{2}, cdots, a_{k})$。
必要性 设$d_{1}, d_{2}, cdots, d_{s}$为$a_{1}, a_{2}, cdots, a_{k}$的全体公约数。设$L = [d_{1}, d_{2}, cdots, d_{s}]$，所以$d_{i}leqslant L$。由定理2.1可知，$Lmid d_{i}$，由充分性可知$L = a_{1}, a_{2}, cdots, a_{k})$，取$D = L$。
这条定理揭示了一条结论：公约数一定是最大公约数的约数。
定理2.3的证明 若$dmid a_{i}$，则由定理2.2可知$dmid a_{1}, a_{2})$，若$dmid a_{1}, a_{2}), dmid a_{i}, i = 3, 4,cdots, k$，则由整除的传递性可得$dmid a_{1}, dmid a_{2}$。因此它们的公约数集合相同，由定义可知等式成立。
可以利用定理2.3来求多个数的最大公约数。
定理2.4的证明 设$S = left {s = a_{1}x_{1} + a_{2}x_{2} + cdots + a_{k}x_{k}:x_{i}in mathbb{Z}wedge s > 0ight }$，因为$0 < a_{1}^{2} + a_{2}^{2} + cdots + a_{k}^{2}in S$，所以集合$S$中存在正整数。由最小自然数原理可知，$S$中存在最小正整数$s_{0}$。
任意公约数$dmid s_{0}$，则有$dmid s_{0}$，所有$dleqslant s_{0}$。
另一方面，由带余数除法可得$left|a_{j}ight| = q_{j}s_{0} + r_{j}, 0leqslant r_{j} < s_{0}$。因为当$a_{j}
eq 0$的时候，$q_{j}s_{0}in S, left|a_{j}ight|in S$,当$r_{j}
eq 0$时，可以证得$r_{j} = left|a_{j}ight| – q_{j}s_{0}in S$，这与$s_{0}$的最小性矛盾，故$r_{j} = 0$。因此$s_{0} mid a_{i}$。
由定理2.2可得$s_{0} = a_{1}, a_{2}, cdots, a_{k})$。
根据定理2.4，我们可以知道一组不完全为零的整数$a_{1}, a_{2}, cdots, a_{k}$，存在一组整数$x_{1}, cdots, x_{k}$使得$a_{1}x_{1} + a_{2}x_{2} + cdots + a_{k}x_{k} = lefta_{1}, a_{2}, cdots, a_{n} ight )$。现在我们考虑如何来求解它。
首先考虑2个数$u_{0}, u_{1}$的情况，先使用辗转相除法。假设已经知道$u_{k + 1} = xcdot u_{n} + ycdot u_{n + 1}$。利用代入消元法消掉$u_{n + 1}$：$u_{k + 1} = xcdot u_{n} + yu_{n – 1} – q_{n – 1}u_{n}) = ycdot u_{n – 1} + x – q_{n – 1}y)u_{n}$。写成程序就是：
1 void exgcdint a, int b, int& d, int& x, int& y) { 2 if !b) 3 d = a, x = 1, y = 0; 4 else { 5 exgcdb, a % b, d, y, x); 6 y -= a / b) * x; 7 } 8 }
另外提一句，可以用这样的一个方法来证明定理2.4。
定理2.5的证明 $a = a, mb) = a, am, mb) = a, a, b)m) = a, m)$，所以$amid m$。
定理2.6的证明 设$d = a_{1}/m, a_{2} / m, cdots, a_{k}/m), D = a_{1}, a_{2}, cdots, a_{k})$。因为$dmid a_{i} / m$，所以$mdmid a_{i}$，由定义可得$mdgeqslant D$。因为$D mid a_{i}$，又因为$D / m mid a_{i} / m$，所以$D / mgeqslant d$，所以$D geqslant md$，因此$D = md$。
解不定方程
例子 解不定方程$3x_{1} + 5x_{2} = 11 x_{1}, x_{2}in mathbb{Z})$。
首先介绍一下数学解法：
$x_{1} = frac{1}{3}left 11 – 5x_{2} ight ) = 3 – x_{2}+frac{1}{3}left 2 – 2x_{2} ight )$。
$x_{1}$是整数的充分必要条件是$frac{1}{3}left 2 – 2x_{2} ight )in mathbb{Z}$。因此设$x_{3} = frac{1}{3}left 2 – 2x_{2} ight )$
所以有$3x_{3} = 2 – 2x_{2}$。移项得：$x_{2} = frac{1}{2}left 2 – 3x_{3} ight ) = 1 – x_{3} – frac{1}{2}x_{3}$。
设$x_{4} = frac{1}{2}x_{3}in mathbb{Z}$。因此有$x_{3} = 2x_{4}, x_{4} in mathbb{Z}$。
所以$x_{2} = 1 – frac{3}{2}x_{3} = 1 – 3x_{4}$，$x_{1} = frac{1}{3}left [ 11 – 5left 1 – 3x_{4}ight ) ight ]=2 + 5x_{4}$。
这个做法的本质是对整个不定方程用辗转相除法，不断消去$x_{1}, x_{2}, cdots$，转化成等价的不定方程，直到有一个未知数的系数的绝对值为1为止。最后再倒着推回去。
如果调用上面的函数呢？我们首先会得到一组数$u, v$使得$3u + 5v = 3, 5) = 1$，然后可得$311u) + 511v) = 11$。于是便愉快地得到了一组特解。
然后有个问题，假如在方程$a_{1}x_{1} + a_{2}x_{2} = c x_{1}, x_{2}in mathbb{Z})$中，$a_{1}, a_{2})
mid c$那么会发生什么？答案是无解。
定理3.1 在不定方程$a_{1}x_{1} + a_{2}x_{2} + cdots +a_{n}x_{n} = c x_{1}, cdots, x_{n}in mathbb{Z}, a_{i}
eq 0)$中，存在解的充分必要条件是$a_{1}, a_{2}, cdots, a_{n})mid c$。
证明 必要性由$a_{1}, a_{2}, cdots, a_{n})mid a_{1}x_{1} + a_{2}x_{2} + cdots +a_{n}x_{n}$可得。充分性由定理2.4易证。
继续考虑二元一次不定方程，我们可以用辗转相除法求出一组特解，那么能不能表示所有解呢？答案是可以的。
定理3.2 设二元一次不定方程$a_{1}x_{1} + a_{2}x_{2} = c$有解，它的一组特解为$u_{1}, u_{2}$，那么它的所有解为
$left{egin{matrix}x_{1} = u_{1} + frac{a_{2}}{a_{1}, a_{2})}cdot t\ x_{2} = u_{2} – frac{a_{1}}{a_{1}, a_{2})}cdot tend{matrix}ight. left tin mathbb{Z} ight )$
证明 容易验证上式给出的解一定是原方程的解。现在证明原方程的解一定可以这样表示。联立等式有$a_{1}x_{1} + a_{2}x_{2} = a_{1}u_{1} + a_{2}u_{2}$。
所以有$a_{1}x_{1} – u_{1}) = -a_{2}x_{2} – u_{2})$。所以$frac{a_{1}}{a_{1}, a_{2})}x_{1} – u_{1}) = -frac{a_{2}}{a_{1}, a_{2})}x_{2} – u_{2})$。
由整除定义可知：$frac{a_{1}}{a_{1}, a_{2})} mid frac{a_{2}}{a_{1}, a_{2})}x_{2} – u_{2})$。根据定理2.5可得$left frac{a_{1}}{a_{1}, a_{2})},frac{a_{2}}{a_{1}, a_{2})} ight ) = 1$。然后根据定理2.6可得$frac{a_{1}}{a_{1}, a_{2})} mid x_{2} – u_{2})$。同理可得$frac{a_{2}}{a_{1}, a_{2})} mid x_{1} – u_{1})$。
由此，定理得证。
（to be continued…）