帶餘除法與歐幾里得演算法

帶餘除法的精確表述

當你用一個整數去除另一個整數時，通常不會正好除盡。[[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——即它們的分解中不共享任何質數。