欧拉定理 扩展欧拉定理 总结

欧拉定理（Euler's theorem，ET）

定义

如果正整数 \(a \perp n\)，\(a^{\varphi(n)} \equiv 1 \pmod p\).
特殊情况：费马小定理

没人觉得欧拉和费马很好磕吗？

证明

令 \(X = \{x \mid 1 \le x \le n,x \perp n\}, Y = \{ax_1 \bmod n, ax_2 \bmod n, ... , ax_{\varphi(n)} \bmod n\}\)。

---

性质一 \(Y\) 中所有数互不相同

反证法：
假设存在 \(i \not = j\) 使得 \(ax_i \equiv ax_j \pmod n\)，则 \(n \mid a(x_i - x_j)\)。应为 \(a \perp n\)，所以 \(n \mid (x_i - x_j)\)，因为 \(x_i - x_j \le n\)，所以 \(x_i = x_j\)，与 \(i \not = j\) 矛盾。

性质二 \(Y\) 中所有数与 \(n\) 互质

\[\because x \perp n \]

\[\therefore \gcd(x, n) = 1 \]

\[\because \gcd(a, n) = 1 \]

\[\therefore \gcd(ax, n) = 1 \]

\[\therefore \gcd(ax \bmod n, n) = 1 \]

---

\(X\) 的定义也可以等价地转化为所有数互不相同且所有数都与 \(n\) 互质，所以可得 \(X = Y\)。则有

\[x_1 \times x_2 \times ... \times x_{\varphi(n)} \equiv ax_1 \times ax_2 \times ... \times ax_{\varphi(n)} \pmod n \]

\[x_1 \times x_2 \times ... \times x_{\varphi(n)} \equiv a^{\varphi(n)}(x_1 \times x_2 \times ... \times x_{\varphi(n)}) \pmod n \]

因为 \(x \perp n\)，所以它们都有关于 \(n\) 的逆元

\[a^{\varphi(n)} \equiv 1 \pmod n \]

欧拉定理得证。

应用

应用一 求逆元

\(a^{-1} \equiv a^{\varphi(n) - 1} \pmod n\)

应用二 指数降幂

对于 \(a ^ b \bmod n\)，若 \(a \perp n\)，则

\[a^b \equiv a^{b \bmod \varphi(n)} \pmod n \]

扩展欧拉定理（ExET）

对于任意正整数 \(a, n\)（不要求互质），和非负整数 \(b\)

\[a^b = \begin{cases}a^b \bmod n & b < \varphi(n) \\ a^{(b \bmod \varphi(n)) + \varphi(n)} & b \ge \varphi(n)\end{cases} \]

不会证

要点

• ET 基本没用（除非固定模数，或要求互质）
• ExET 一定要注意第一种情况，在取模前要先判断是否大于 \(\varphi(n)\)
• 实现时一般用递归，并考虑本身作为指数。

Problem

P5091 【模板】扩展欧拉定理

P4139 上帝与集合的正确用法

题解

可以对层都运用 ExET 作取模，而每次的模数都会用 \(\varphi\) 迭代，最多 \(\log p\) 次

启示

• 模数都会用 \(\varphi\) 迭代，最多 \(\log p\) 次

CF906D Power Tower

题解

虽然区间很大，但模数最多迭代 \(log p\) 次，所以暴力作，由于区间不像上一题的无限，要注意快速幂时判断两种情况。

启示

• 乘法加法运算取模前一定要判断情况

CF185D Visit of the Great

不会

P2350 [HAOI2012] 外星人 - 洛谷

题解

观察
迭代的过程可以发现，要想变成 \(1\)，总是要通过质因子 \(2\)，于是迭代次数等于二变一的次数，我们可以对每一个质因子考虑他会贡献多少个 \(2\) 到 \(1\)，这个是完全加性的，所以可以用欧拉筛预处理。注意 \(2 \not \mid n\) 的情况。

启示

• 在唯一分解的角度下考虑问题
• 模拟考虑
• 部分加性与完全加性，和部分积性与完全积性的区别，在于计算函数值时，是考虑对每种质因子的答案作加法或乘法还是对每个质因子的答案作加发或乘法

Sum - HDU 4704 - Virtual Judge

题解

使用插板法和二项式定理可以发现 \(ans = 2^{n - 1}\) 欧拉定理即可。
问题来了，我们该如何解决 \(n - 1\)？注意到存在 ET

启示

• 正确地根据情况选择正确的方法（底数和模数互质就可以用 ET）

Calculation - HDU 2837 - Virtual Judge

板子