带余除法与欧几里得算法

带余除法的精确表述

当你用一个整数去除另一个整数时，通常不会正好除尽。[[division-algorithm|带余除法]]对此作了精确表述：对任意整数 a 和任意正整数 b，恰好存在唯一一对整数 q（商）和 r（余数），使得 a = b·q + r 且 0 ≤ r < b。余数总是非负的，并且严格小于除数。

Divide 47 by 6:
  47 = 6 · 7 + 5     (q = 7, r = 5,  0 ≤ 5 < 6) ✓

Divide -47 by 6 (watch the sign!):
  -47 = 6 · (-8) + 1   (q = -8, r = 1)
  NOT  6 · (-7) - 5, because r must satisfy 0 ≤ r < 6.

The remainder r = 0 exactly when b divides a.

余数必须落在 0 ≤ r < b 范围内——即使被除数为负也是如此。

追踪余数求最大公约数

两个数的[[greatest-common-divisor|最大公约数]]和指南一中的最大公因数是同一概念，只是名字更正式。对大数而言，列出所有因数很慢。[[euclidean-algorithm|欧几里得算法]]则快得惊人，它依赖一个美妙的事实：gcd(a, b) = gcd(b, r)，其中 r 是 a 除以 b 的余数。用较小的一对替换较大的一对，GCD 保持不变，于是你只需重复，直到余数变为 0。

gcd(252, 105):
  252 = 105 · 2 + 42
  105 =  42 · 2 + 21
   42 =  21 · 2 +  0   ← remainder 0, stop

The last NONZERO remainder is 21.
So gcd(252, 105) = 21.

(Compare: 252 = 2^2·3^2·7, 105 = 3·5·7,
 shared part = 3·7 = 21. Same answer.)

每一行把它的除数和余数送入下一行；最后一个非零余数就是 GCD。

用较大数除以较小数；记下余数。
再用上一步的除数除以该余数；记下新余数。
继续进行。当余数为 0 出现时，那一行的除数就是 GCD。

附带收获：逆向回代

如果你执行欧几里得算法，然后把各行逆向往上回代，就能把 GCD 写成组合 d = a·x + b·y，其中 x、y 为整数。这就是[[bezouts-identity|裴蜀恒等式]]，也是下一篇指南中求解方程的引擎。两个数[[relatively-prime|互素]]当且仅当它们的 GCD 为 1——即它们的分解中不共享任何素数。