欧拉定理
思想
若 \(a\) 与 \(n\) 互质，则 \(a^{\varphi(n)} \equiv 1\pmod n\)；
容易得出当 \(n\) 为质数时， \(a^{n - 1}\equiv 1 \pmod n\)。
证明
假设与 \(1\sim n\) 中与 \(n\) 互质的数字为 \(x_1, x_2, x_3, \cdots x_{\varphi(n)}\)，且两两不同。
现将它们全部乘以 \(a\) 得到 \(ax_1,ax_2,ax_3,\cdots,ax_{\varphi(n)}\)，它们模 \(n\) 的余数一定两两不同。
利用反证法：
假设 \(ax_i \equiv ax_j\pmod n\)，那么
\[\begin{aligned} ax_i-ax_j&\equiv 0\pmod n\\ a(x_i-x_j)&\equiv 0\pmod n \end{aligned} \]因为 \(\gcd(a, n) = 1\)，所以
\[\begin{aligned} x_i-x_j&\equiv 0\pmod n \end{aligned} \]但是 \(x_i, x_j\) 都小于 \(n\) 且互不相同，不可能 \(x_i-x_j\equiv 0\pmod n\)。
所以 \(ax_1,ax_2,ax_3,\cdots,ax_{\varphi(n)}\)，它们模 \(n\) 的余数一定两两不同，共有 \(\varphi(n)\) 种余数。
然后我们发现 \(ax_1,ax_2,ax_3,\cdots,ax_{\varphi(n)}\) 模 \(n\) 的余数一定与 \(n\) 互质。
利用反证法：
假设 \(ax_i\) 模上 \(n\) 的余数与 \(n\) 不互质，其公因子为 \(g\)，即 \(n = gs\)，余数 \(r = gp\)。
那么 \(ax_i = qn + r = q(gs)+gp = g(qs + p)\)。
而 \(n = gs\)，所以 \(ax_i\) 与 \(n\) 不互质。
根据定义，\(a, x_i\) 均与 \(n\) 互质，那么 \(ax_i\) 与 \(n\) 也必须互质，所以假设不成立。
所以 \(ax_1,ax_2,ax_3,\cdots,ax_{\varphi(n)}\) 模 \(n\) 的余数一定与 \(n\) 互质。
根据上面的证明，\(ax_1,ax_2,ax_3,\cdots,ax_{\varphi(n)}\) 模 \(n\) 的余数一定两两不同，模 \(n\) 的余数一定与 \(n\) 互质，说明它们的余数正好对应 \(x_1, x_2, x_3, \cdots, x_{\varphi(n)}\)，所以
\[\begin{aligned} a^{\varphi(n)}x_1x_2x_3\cdots x_{\varphi(n)} &\equiv x_1x_2x_3\cdots x_{\varphi(n)}\pmod n\\ (a^{\varphi(n)} - 1)x_1x_2x_3\cdots x_{\varphi(n)} &\equiv 0\pmod n \end{aligned} \]因为 \(\gcd(x_1x_2x_3\cdots x_{\varphi(n)}, 1) = 1\)，所以
\[\begin{aligned} a^{\varphi(n)} - 1&\equiv 0\pmod n\\ a^{\varphi(n)}&\equiv 1\pmod n \end{aligned} \] 标签：pmod,定理,varphi,cdots,模板,ax,互质,欧拉,equiv From： https://www.cnblogs.com/Yuan-Jiawei/p/18315352