帶餘除法

小學的長除法總以一個商和一個餘數收尾：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。這條有保證的餘數是歐幾里得演算法以及整套同餘與模運算機制的基礎。