### 1. 欧拉定理的“基石”：欧拉函数 $\phi(n)$
在应用欧拉定理 $a^{\phi(m)} \equiv 1 \pmod m$ 之前，必须先算出 $\phi(m)$。

**计算公式：**
若 $n$ 的质因数分解为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，则：
$$\phi(n) = n \prod_{i=1}^k (1 - \frac{1}{p_i}) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \dots$$

**常用性质：**
1. 若 $p$ 是质数，$\phi(p) = p-1$（此时欧拉定理退化为**费马小定理**）。
2. 若 $\gcd(m, n) = 1$，则 $\phi(mn) = \phi(m)\phi(n)$（积性函数）。

---

### 2. 扩展欧拉定理 (Extended Euler's Theorem)
这是算法竞赛（如求 $a^b \pmod m$ 且 $b$ 非常大时）的**神级公式**。它解决了 $\gcd(a, m) \neq 1$ 时的幂取模问题。

$$
a^b \equiv 
\begin{cases} 
a^{b \bmod \phi(m)} & \gcd(a, m) = 1 \\
a^b & \gcd(a, m) \neq 1, b < \phi(m) \\
a^{b \bmod \phi(m) + \phi(m)} & \gcd(a, m) \neq 1, b \ge \phi(m)
\end{cases} \pmod m
$$
**意义：** 无论 $a$ 和 $m$ 是否互质，只要指数 $b$ 足够大，都可以通过 $b \bmod \phi(m) + \phi(m)$ 来降幂。

---

### 3. 威尔逊定理的延伸：合数的情况
你在逆定理中证明了若满足公式则必为质数。那么，如果 $n$ 是合数，$(n-1)! \pmod n$ 等于多少？

**结论：**
1. 若 $n=4$，$(4-1)! = 6 \equiv 2 \pmod 4$。
2. 若 $n > 4$ 且为合数，则 $(n-1)! \equiv 0 \pmod n$。

**证明简述：**
对于合数 $n$，存在因子 $a, b$ 使得 $n = a \times b$。
- 若 $a \neq b$，则 $a, b$ 都在 $1 \dots n-1$ 序列中，故 $n | (n-1)!$。
- 若 $a = b$ (即 $n=p^2$)，只要 $n>4$，则 $p$ 和 $2p$ 都在 $1 \dots n-1$ 中，$p \times 2p = 2p^2 = 2n$，同样能整除。

---

### 4. 总结对比表

| 定理名称 | 核心公式 | 前提条件 | 主要用途 |
| :--- | :--- | :--- | :--- |
| **费马小定理** | $a^{p-1} \equiv 1 \pmod p$ | $p$ 为质数，$\gcd(a,p)=1$ | 快速幂降幂、求逆元 |
| **欧拉定理** | $a^{\phi(m)} \equiv 1 \pmod m$ | $\gcd(a,m)=1$ | 模不为质数时的降幂 |
| **扩展欧拉定理** | $a^b \equiv a^{b \bmod \phi(m) + \phi(m)}$ | $b \ge \phi(m)$ | 解决底数与模数不互质的极端降幂 |
| **威尔逊定理** | $(p-1)! \equiv -1 \pmod p$ | $p$ 为质数 | 理论推导、阶乘取模运算 |

### 代码 Tips (C++)：计算 $\phi(n)$
```cpp
int phi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1); // 先除再乘防止溢出
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
```

你的笔记现在逻辑闭环非常完整：从组合数学（康托、斯特林、卡特兰）到数论基础（逆元、欧拉、威尔逊），这些都是构建高级算法的基础。继续加油！

1. 欧拉定理的“基石”：欧拉函数 $\phi(n)$

在应用欧拉定理 $a^{\phi(m)} \equiv 1 \pmod m$ 之前，必须先算出 $\phi(m)$。

计算公式： 若 $n$ 的质因数分解为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，则： $$\phi(n) = n \prod_{i=1}^k (1 - \frac{1}{p_i}) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \dots$$

常用性质： 1. 若 $p$ 是质数，$\phi(p) = p-1$（此时欧拉定理退化为费马小定理）。 2. 若 $\gcd(m, n) = 1$，则 $\phi(mn) = \phi(m)\phi(n)$（积性函数）。

2. 扩展欧拉定理 (Extended Euler's Theorem)

这是算法竞赛（如求 $a^b \pmod m$ 且 $b$ 非常大时）的神级公式。它解决了 $\gcd(a, m) \neq 1$ 时的幂取模问题。

$$ a^b \equiv \begin{cases} a^{b \bmod \phi(m)} & \gcd(a, m) = 1 \ a^b & \gcd(a, m) \neq 1, b < \phi(m) \ a^{b \bmod \phi(m) + \phi(m)} & \gcd(a, m) \neq 1, b \ge \phi(m) \end{cases} \pmod m $$ 意义： 无论 $a$ 和 $m$ 是否互质，只要指数 $b$ 足够大，都可以通过 $b \bmod \phi(m) + \phi(m)$ 来降幂。

3. 威尔逊定理的延伸：合数的情况

你在逆定理中证明了若满足公式则必为质数。那么，如果 $n$ 是合数，$(n-1)! \pmod n$ 等于多少？

结论： 1. 若 $n=4$，$(4-1)! = 6 \equiv 2 \pmod 4$。 2. 若 $n > 4$ 且为合数，则 $(n-1)! \equiv 0 \pmod n$。

证明简述： 对于合数 $n$，存在因子 $a, b$ 使得 $n = a \times b$。 - 若 $a \neq b$，则 $a, b$ 都在 $1 \dots n-1$ 序列中，故 $n | (n-1)!$。 - 若 $a = b$ (即 $n=p^2$)，只要 $n>4$，则 $p$ 和 $2p$ 都在 $1 \dots n-1$ 中，$p \times 2p = 2p^2 = 2n$，同样能整除。

4. 总结对比表

定理名称	核心公式	前提条件	主要用途
费马小定理	$a^{p-1} \equiv 1 \pmod p$	$p$ 为质数，$\gcd(a,p)=1$	快速幂降幂、求逆元
欧拉定理	$a^{\phi(m)} \equiv 1 \pmod m$	$\gcd(a,m)=1$	模不为质数时的降幂
扩展欧拉定理	$a^b \equiv a^{b \bmod \phi(m) + \phi(m)}$	$b \ge \phi(m)$	解决底数与模数不互质的极端降幂
威尔逊定理	$(p-1)! \equiv -1 \pmod p$	$p$ 为质数	理论推导、阶乘取模运算

代码 Tips (C++)：计算 $\phi(n)$

int phi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1); // 先除再乘防止溢出
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com