更相减损术

步骤：

  1. 令 p 、q 分别为正整数，且 p > q；
  2. 更新 p，令 p = p - q；
  3. 若 p < q，交换 p 、q 的值；
  4. 若 p == q 则 p 为原 p 、q 的最大公约数，否则重复步骤2；

个人思考：

假设 p 、q 的最大公约数为 d，则 p = k1d 、q = k2d 。由步骤1的条件不难推出 k1 > k2 ，且 k1 、k2 的最大公约数是1。通过步骤2和步骤3可以发现，不断更新 p 、q 的值实际上就是不断减小 k1 、k2 的值，并且步骤3会强制使得更新后 k1 > k2 。另外，在不断更新过程中 k1 、k2 的最大公约数始终为1，因为已经假设了 d 为 p 、q 的最大公约数，若 k1 、k2 的最大公约数不始终为1，则 d 不可能是最大公约数，会与假设矛盾。因此在 k1 、k2 不断减小中，最终两者会趋近相等，且保持两者最大公约数为1，因此，最终会有k1 = k2 = 1。而此时步骤4就会成立，且p 、q 均更新成了最大公约数 d。

辗转相除法

步骤：

  1. 令 p 、q 分别为正整数；
  2. 更新 p 、q，令 r = p mod q， p = q，q = r；
  3. 若 q = 0，则 p 是原 p 、q 的最大公约数，否则重复步骤2；

个人思考

假设 p 、q 的最大公约数为 d，则 p = k1d 、q = k2d，且 k1 、k2 的最大公约数是1。步骤1中没有了 p > q 的限制，是因为即使 p < q ，经过步骤2之后，仍然能有 p > q 。而在 p > q 时，有k1 > k2，并且由步骤2可知，r = (k1 - k2k3)d，其中 k3 为 p / q 的商，且更新后 k1' = k2 、k2' = (k1 - k2k3)，且 k1' 和 k2' 的最大公约数也始终为1。由此也可看出，不断更新 p 、q 同样会不断减小 k1 、k2 ，而最终会有k1 = k2 = 1。此时 p = q，再执行步骤2，即可得到步骤3的成立。在 p = q之前，不存在在迭代过程中出现 k3 = k1 / k2 的情况。因为，假设在第 i 次迭代时，出现 k3 = k1 / k2，则表明在第 i-1次迭代时，k1' 和 k2' 的最大公约数不为1，这与假设矛盾。还可以这样理解，若出现 k3 = k1 / k2 ，则表明所求得的最大公约数为 k2d，当且仅当 k2 = 1 时满足假设，因此，当且仅当 k2 = 1 时，会出现 k3 = k1 / k2 ，而此时 p = d，q = 0 满足步骤3的终止条件。

两种方法的比较

在本质上，更相减损术和辗转相除法都是通过不断迭代来减小 k1 、k2 ，从而最终得到最大公约数 d。其实更相减损术可看作辗转相除法在每次迭代过程中的 k3 = 1，的特例。因此，在速度上，辗转相除法要更快，因为在每次迭代过程中 k3 必然大于等于1。