前置知识

定理内容

若\(gcd(a,n)=1\)，则有\(a^{\psi(n)}\equiv 1\ (mod\ n)\)
当n为素数时，\(\psi(n)=n-1\)，即\(a^{n-1}\equiv 1\ (mod\ n)\)，这就得到了费马小定理。

证明

令\(\Phi_n\)表示模n的最小正缩系：
\(\Phi_n=\{c_1,c_2,\cdots,c_{\psi(n)}\}\)
取一个与n互质的数a，即\(gcd(a,n)=1\)
那么\(a\cdot\Phi_n=\{a\cdot c_1,a\cdot c_2,\cdots,a\cdot c_{\psi(n)}\}\)也是n的一个缩系。

\(\because a\perp n,c_i\perp n\therefore a\cdot c_i\perp n\)
\(\because c_i\equiv r_i\ (mod\ n),a\equiv 1\ (mod\ n)\therefore a\cdot c_i\equiv r_i\ (mod\ n)\)

首先有：

\[\begin{equation*} \underset{i=1}{\overset{\psi(n)}{\Pi}}(a\cdot c_i)\equiv \underset{i=1}{\overset{\psi(n)}{\Pi}}c_i\ (mod\ n) \end{equation*}\]

又有：

\[\begin{equation*} \underset{i=1}{\overset{\psi(n)}{\Pi}}(a\cdot c_i)= a^{\psi(n)}\cdot\underset{i=1}{\overset{\psi(n)}{\Pi}}c_i \end{equation*}\]

即：

\[\begin{equation*} a^{\psi(n)}\cdot\underset{i=1}{\overset{\psi(n)}{\Pi}}c_i\equiv \underset{i=1}{\overset{\psi(n)}{\Pi}}c_i\ (mod\ n) \end{equation*}\]

因为：

\[\begin{equation*} gcd(a^{\psi(n)},\underset{i=1}{\overset{\psi(n)}{\Pi}}c_i)=1 \end{equation*}\]

两边同时除以\(\underset{i=1}{\overset{\psi(n)}{\Pi}}c_i\)得：

\[\begin{equation*} a^{\psi(n)}\equiv 1\ (mod\ n) \end{equation*}\]