问题

Claim: $\binom{n}{k}\equiv 0 (\mod n)$ 对所有 $0 < k < n$ 成立当且仅当 $n$ 是素数.

利用此性质, Fermat 小定理及二项式展开, 容易证明:

定理: 设 $n\geqslant 2$, $0 < a < n$, 且 $a$ 与 $n$ 互素, 则

\[
n \mbox{是素数}\Leftrightarrow (x+a)^n\equiv x^n +a \pmod n
\]


(注意: 这里, $x$ 是一个自由的变量, 它不能用数去代入, 而必须将多项式展开, 并比较系数.)

Remark:

这个定理是 AKS 算法所依赖的定理. AKS 算法可以确定性地判断某个整数是否一定是素数.