費馬小定理

把數升到高次冪，通常會讓它的大小急劇膨脹。但若你只關心它除以一個質數後的餘數，就會冒出一種意外的規律：這些冪會落入一個可預測、且總會循環回去的模式。費馬小定理把這個模式精確地定了下來。

定理是：若 p 是質數，a 是任意整數，則 a^p ≡ a (mod p)。當 a 不被 p 整除時，可兩邊約去 a，得到常被引用的形式 a^(p−1) ≡ 1 (mod p)。例如取 p = 5, a = 2：2^4 = 16 = 15 + 1，而 16 ≡ 1 (mod 5)。

它是計算上的得力工具，也是密碼學的基石之一，因為它能把巨大的指數在質數模下大幅壓縮。兩點要誠實說明。其一，簡潔的 a^(p−1) ≡ 1 形式要求 a 不被 p 整除；若 p 整除 a，則兩邊都直接為 0。其二，逆命題不成立：一個數 n 通過 a^(n−1) ≡ 1 (mod n) 並不保證它是質數 — 合數中的卡邁克爾數會騙過這個檢驗 — 所以它給出的是質性的有力證據，而非證明。