欧几里得算法求解最大公因数（gcd）正确性的证明
欧几里得算法是求解最大公因数（gcd）的简单且高效的算法。它的求解方法是以下的一个递归式：
（注意：上式规定 \(a > b\)，以方便讨论。由于 \(\gcd(a, b) = \gcd(b, a)\)，这样规定也不会使这个式子失去一般性。如果想计算诸如 \(\gcd(12, 18)\) 之类的值，只要用上式计算 \(\gcd(18, 12)\) 即可。）
举个例子：\(\gcd(18, 12) = \gcd(12, 6) = \gcd(6, 0) = 6\)。
我们可以先分析一下这个递归式：第一种情况，当 \(b = 0\) 时，有 \(\gcd(a, 0) = a\)，这是很显然的。因为任何数都是 \(0\) 的因数，又因为 \(a\) 是它本身最大的因数。我们不妨把这个情况当作“基本情况”，而第二个式子就是要把非一般的情况，转化为我们所知的、容易计算的基本情况。而这篇文章，主要就是证明第二种情况的式子为什么成立，即证明 \(\gcd(a, b) = \gcd(b, a \bmod b)\)。
要证明这个式子正确，我们先证明一个命题：设 \(a\) 与 \(b\) 的公因数所构成的集合为 \(A\)，\(b\) 与 \(a \bmod b\) 的公因数构成的集合为 \(B\)，则 \(A = B\)。换句话说，就是要证明所有 \(a\) 与 \(b\) 的公因数，都是 \(b\) 与 \(a \bmod b\) 的公因数（即 \(A \in B\)）；反过来，所有 \(b\) 与 \(a \bmod b\) 的公因数，也都是 \(a\) 与 \(b\) 的公因数（即 \(B \in A\)）。证明了这个命题之后，既然 \(A\) 与 \(B\) 相等，那么它们中最大的那个元素当然也就相等了。而 \(A\) 与 \(B\) 中的最大元素，不就分别是 \(\gcd(a, b)\) 和 \(\gcd(b, a \bmod b)\) 吗！
虽然我们把原先要证明的命题扩大了：原本只需证明 \(a\) 与 \(b\) 的最大公因数，等于 \(b\) 与 \(a \bmod b\) 的最大公因数；现在要证明 \(a\) 与 \(b\) 的所有公因数，等于 \(b\) 与 \(a \bmod b\) 的所有公因数。但是由于去掉了“最大”的特殊条件，要证明起来反而更容易。
具体怎么证明呢？
设 \(g\) 是 \(a\) 和 \(b\) 的一个公因数，且 \(a = a'g\) , \(b = b'g\)，要证明的就是 \(g | (a \bmod b)\) （注：“\(|\)” 符号表示整除，\(x | y\) 就表示 \(x\) 是 \(y\) 的因数）。从 \(\bmod\) 运算的定义出发，若 \(a = kb + r\)，其中 \(k\) 是满足 \(kb \le a\) 的最大正整数，则 \(a \bmod b = r = a - kb\)。
把 \(a = a'g\) , \(b = b'g\) 代入，就得到 \(a - kb = a'g - kb'g = g(a' - kb')\)，所以显然 \(g | (a \bmod b)\) 。上命题得证。用几个具体的数验证一下，设 \(a = 18\). \(b = 12\)，则 \(a \bmod b - 6\),\(A = {1, 2, 3, 6}\),\(B = {1, 2, 3, 6}\)，确实 \(A = B\)。
综上，欧几里得算法的正确性证毕。