最近回顾之前写的 RSA 算法相关的文章时，因为 RSA 跟质数有关，突然联想到欧几里德求任意两个自然数最大公约数的方法（又叫辗转相除法）：拿 较小数 n 去除 较大数 m，如果 m 正好被整除，则 n 理所当然是最大公约数；而如果不能被整除，则得到一个 余数 r，这个时候则把 r 当成较小数，n 当成较大数，再走一次上面的流程……总之，到最后一定会得到一个 余数 或者说 较小数 r’ 能整除较大数，较小数 r’ 就是一开始 m 和 n 两个数的最大公约数。
如果用 f(x, y) 来表示获取 x 和 y 两个正整数的最大公约数的函数，用 x mod y 来表示 x 除以 y 取余数的操作，那么上述欧几里德求最大公约数公式也可以用公式表示为：
x 和 y 均为自然数，假设 r = x mod y：
当 r 不为 0 时 f(x, y) = f(y, r)
当 r 为 0 时 f(x, y) = y
因为最大公约数英文为 Greatest Common Divisor，所以上述的 f(x, y) 中的 f 又常常用最大公约数的缩写 gcd 代替。
一开始我总觉得这个公式非常反直觉，想不通为什么最大公约数会跟余数有关系。经过证明，的确如此，但就算证明出来依然觉得反直觉（其实上学那会儿很多数学公式都会带给我这种感觉……）。不过这里我想运用一下我最近了解到的关于人脑的两个知识点来解决这个问题：第一，人脑善于通过具体的例子归纳总结而不是反过来；第二，人脑善于用图形来思考问题。
先假设有两根线，一根长 51 厘米，一根长 187 厘米，我们的目的是为了找到一根线（必须是 1 厘米的整数倍），正好能丈量这两根线。很显然，一根 1 厘米的线一定是满足这个需求的。问题是，用来丈量的线，最长可以到多长？
我们不妨先假设最长的线有 n 厘米，那 51 必须是 n 的整数倍，187 也必须是 n 的整数倍。另外，我们可以很容易通过把 187 厘米的线与 51 厘米的线对齐的方式，从 153 厘米的线上剪 51 厘米的线下来，剩下的 136 厘米很显然也必须是 n 的整数倍。
我们再利用 51 厘米线再从 136 厘米的线上剪 51 厘米下来……如此反复又剪了2次，136 厘米的线还剩下 34 厘米。同样，34 也必须是 n 的整数倍。其实上面的过程也可以描述为：如果有一个数 n，能整除 187 和 51，那 n 必须也能整除 187 除以 51 的余数 34。
我们把上面的结论再归纳一下，把具体的长度去掉，可以这么说：如果有一个自然数 n，能整除自然数 a 和 b，那 n 也必须能整除 a 除以 b 的余数。
再回到上面的例子。既然 187，51，34 三个数都能被 n 整除，再结合刚才的归纳，那不管是 187 除以 34 的余数也好，还是 51 除以 34 的余数也好，也都必须得能被 n 整除。很容易算出来上面所说的两个余数都是 17，并且到这个地步，我们也一眼能看出 17 已经能整除 34 本身。
以下是正儿八经的证明：
假如有一个自然数 c，能整除另外两个自然数 a 和 b，那必然存在两个正整数 m 和 n，能让：
a = mc；b = nc；
另外，如果 a mod b 为 r，且 r > 0，那必有一个自然数 k，能让：
a = kb r；
将上式 a 和 b 替换为 mc 和 nc，得到：
mc = knc r;
即 r = mc - knc = c(m - kn)
因为 m，k，n 都是自然数，m - kn 也必须是自然数，则 r 一定是 c 的整数倍。
虽然为了看起来正规一点，还是写了代数证明，但我还是觉得，公式、定义等一切抽象化的结果，其实都是人们对自己已经掌握的一种知识的精炼，但如果你只是刚开始学，与其强行理解别人的结论，远不如自己用具体的例子去归纳来得轻松和扎实，比如说网上都说要不断用两个数里较小的数去除以余数来获取最大公约数，但通过上面的例子可以看出并不一定非要用较小的数来除以余数。
要注意的是，上面的证明过程只证明了两个数它们任意一个公约数都是这两个数相除的余数的约数，但欧几里德法求出来的数一定是最大的那个公约数吗？这可也是需要证明的：
我们先假设欧几里德法最后得到的最小可能余数，也就是某个约数，为 c，实际的最大公约数为 g，因为 c 肯定能整除最大公约数 g，所以 c ≤ g；
而我们通过之前的证明，可以得到通过辗转相除，无论是哪一步产生的余数，都能被原两个数任意一个公约数整除，其中包括最大公约数 g，所以又会得到 c ≥ g；
综上所述，c 只能等于 g。
,
