前置知识
取模
引入
对于 \(p\in\mathbb{P},a\in\mathbb{N}^+\) 且 \((a,p)=1\)，也就是 \(p\) 为素数且正整数 \(a\) 与 \(p\) 互质，有： \[a^{p-1}\equiv1\pmod p\]
引理1
若 \((c,p)=1\)，则 \(ac\equiv bc\pmod p\) 等价于 \(a\equiv b\pmod p\)。
证明
\[ac\equiv bc\pmod p\]
\[ac-bc\equiv0\pmod p\]
\[c(a-b)\equiv0\pmod p\]
\[\because(c,p)=1\]
\[\therefore a-b\equiv0\pmod p\]
\[a\equiv b\pmod p\]
引理2
若 \(a_1,a_2,\cdots,a_p\) 为 \(\bmod p\) 的完全剩余系，那么对于任意与 \(p\) 互质的 \(c\)，\(ca_1,ca_1,\cdots,ca_n\) 也是 \(\bmod p\) 的完全剩余系。
完全剩余系
\(n\) 的一个剩余类包含所有 \(\bmod n\) 等于某个特定值的数，所以 \(n\) 一共有 \(n\) 个剩余类。
\(n\) 的完全剩余系是一个大小为 \(n\) 的集合，它从 \(n\) 的每个剩余类中选取一个数（也就是每个元素 \(\bmod n\) 的结果各不相同）。
证明
利用反证法。
假设存在 \(ca_i\equiv ca_j\pmod p\)，根据引理1可知 \(a_i\equiv a_j\pmod p\)，产生矛盾，因此假设不成立。
证明
显然 \(0,1,2,\cdots,p-1\) 是 \(\bmod p\) 的一个完全剩余系。
\(\because(a,p)=1\)
\(\therefore a,2a,\cdots,(p-1)a\) 也是 \(\bmod p\) 的完全剩余系。
则有：
\[1\times2\times\cdots\times p-1\equiv a\times2a\times\cdots\times(p-1)a\pmod p\]
\[(p-1)!\equiv(p-1)!a^{p-1}\pmod p\]
\[a^{p-1}\equiv1\pmod p\]