带余除法

小学的长除法总以一个商和一个余数收尾：17 除以 5 得 3 余 2。带余除法正是对这件事的精确保证：它总能成立，而且总给出唯一的答案 — 商与余数从无歧义。

其陈述是：给定整数 a 和正整数 b，存在唯一的整数 q（商）与 r（余数），使得 a = b 乘以 q + r，且余数被限制在 0 ≤ r < b。余数小于除数且非负，正是它把答案钉死为唯一的原因。例如 17 = 5 乘以 3 + 2，再没有别的取法能让 r 落在该范围内。

尽管名字里有“算法”，它其实是一条定理，而非一步步的操作流程 — “算法”是历史叫法。一个细微之处：被除数为负时仍须保持 r 非负，所以 -17 除以 5 得 q = -4、r = 3，因为 -17 = 5 乘以 (-4) + 3。这条有保证的余数是欧几里得算法以及整套同余与模运算机制的基础。