费马小定理

把数升到高次幂，通常会让它的大小急剧膨胀。但若你只关心它除以一个素数后的余数，就会冒出一种意外的规律：这些幂会落入一个可预测、且总会循环回去的模式。费马小定理把这个模式精确地定了下来。

定理是：若 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) 并不保证它是素数 — 合数中的卡迈克尔数会骗过这个检验 — 所以它给出的是素性的有力证据，而非证明。