【费马小定理】
若 $p$ 为素数，$\text{gcd}(a,p)=1$，则 $a^{p-1} \equiv 1 (\bmod p)$。
另一个形式：对于任意整数 $a$，有 $a^p \equiv a\ (\bmod p)$。


【证明】
设一个质数为 $p$，我们取一个不为 $p$ 倍数的数 $a$。
构造一个序列：$A=\{1,2,3,...,p-1\}$，这个序列有着这样一个性质：
$\begin{matrix} \prod_{i=1}^n A_i\end{matrix} \equiv \begin{matrix}\coprod_{i=1}^n (x_i \times a)\ (\bmod p)\end{matrix}$
证明：
$\because (A_i,p)=1,\ (A_i \times a,p)=1$
又因为每一个 $A_i \times a\ (\bmod p)$ 都是独一无二的，且 $A_i \times a\ (\bmod p) < p$
得证（每一个 $A_i \times a$ 都对应了一个 $A_i$)
设 $f=(p-1)!$, 则 $f \equiv a \times A_1 \times a \times A_2 ... \times A_{p-1}\ (\bmod p)\\\\
a^{p-1} \times f \equiv f\ (\bmod p)\\\\
a^{p-1} \equiv 1\ (\bmod p)$
Q.E.D.