问题及解答

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 算法可以确定性地判断某个整数是否一定是素数.
 

\[
(x+a)^n=x^n+\sum_{i=1}^{n-1}C_n^i x^{n-i}a^i +a^n,
\]

注意到 $a$ 与 $n$ 互素, 故由 Fermat 小定理, $a^{n-1}\equiv 1\pmod n$. 而 $n$ 是素数, 故根据 Claim, 等价于 $n|C_n^i$, $\forall\ i=1,2,\ldots, n-1$. 于是

\[
(x+a)^n\equiv x^n+a^n\equiv x^n+a \pmod n
\]