【欧拉函数公式】在数论中，欧拉函数（Euler's Totient Function）是一个非常重要的函数，通常用符号 φ(n) 表示。它表示小于或等于 n 的正整数中与 n 互质的数的个数。这个函数由瑞士数学家欧拉提出，广泛应用于密码学、数论等领域。
一、欧拉函数的基本定义
对于任意正整数 n，φ(n) 表示在 1 到 n 的范围内，与 n 互质的整数的个数。两个数如果最大公约数为 1，则它们互质。
例如：
- φ(1) = 1（只有 1 一个数）
- φ(2) = 1（只有 1）
- φ(3) = 2（1 和 2）
- φ(4) = 2（1 和 3）
二、欧拉函数的计算公式
1. 基本公式（基于质因数分解）
若 n 的质因数分解为：
$$
n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}
$$
则欧拉函数的计算公式为：
$$
\phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)
$$
2. 特殊情况
- 若 n 是质数 p，则 φ(p) = p - 1
- 若 m 和 n 互质，则 φ(mn) = φ(m) × φ(n)
三、欧拉函数的性质
| 性质 | 描述 |
| 1 | φ(1) = 1 |
| 2 | φ(p) = p - 1（p 为质数） |
| 3 | φ(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1) |
| 4 | 若 m 和 n 互质，则 φ(mn) = φ(m) × φ(n) |
| 5 | 对于任意 n，φ(n) ≤ n - 1，当且仅当 n 为质数时等号成立 |
四、欧拉函数的应用
- 密码学：在 RSA 加密算法中，欧拉函数用于计算密钥对。
- 模运算：欧拉定理指出，若 a 与 n 互质，则 $ a^{\phi(n)} \equiv 1 \mod n $
- 数论研究：用于分析数的结构和分布。
五、常见数值表
| n | φ(n) | 说明 |
| 1 | 1 | 只有 1 |
| 2 | 1 | 1 |
| 3 | 2 | 1, 2 |
| 4 | 2 | 1, 3 |
| 5 | 4 | 1, 2, 3, 4 |
| 6 | 2 | 1, 5 |
| 7 | 6 | 1, 2, 3, 4, 5, 6 |
| 8 | 4 | 1, 3, 5, 7 |
| 9 | 6 | 1, 2, 4, 5, 7, 8 |
| 10 | 4 | 1, 3, 7, 9 |
六、总结
欧拉函数 φ(n) 是一个描述与 n 互质的正整数数量的函数，具有简洁而强大的数学表达形式。通过质因数分解可以高效地计算其值，并在多个数学领域中发挥重要作用。掌握欧拉函数的计算方法和性质，有助于深入理解数论中的许多问题。
