【欧拉函数公式】欧拉函数，又称欧拉总计函数，是数论中一个重要的函数，通常用符号 φ(n) 表示。它表示的是小于或等于 n 的正整数中与 n 互质的数的个数。欧拉函数在密码学、数论以及计算机科学中有着广泛的应用，尤其是在 RSA 加密算法中。
一、欧拉函数的基本定义
对于任意正整数 n，欧拉函数 φ(n) 定义为：
> φ(n) = 正整数中小于等于 n 且与 n 互质的数的个数。
其中，“互质”指的是两个数的最大公约数为 1。
二、欧拉函数的计算公式
1. 当 n 为质数时：
如果 n 是质数，则所有小于 n 的正整数都与 n 互质，因此：
$$
φ(n) = n - 1
$$
2. 当 n 为合数时：
若 n 可以分解为质因数的乘积形式，即：
$$
n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}
$$
则欧拉函数可由以下公式计算：
$$
φ(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)
$$
三、欧拉函数的性质
| 性质 | 描述 |
| 1. | 如果 a 和 b 互质，则 φ(ab) = φ(a)·φ(b) |
| 2. | 若 n 是质数 p 的幂次，即 n = p^k，则 φ(p^k) = p^k - p^{k-1} |
| 3. | 对于任意正整数 n，有 φ(n) ≤ n - 1，当且仅当 n 是质数时取等号 |
| 4. | φ(1) = 1（因为 1 与自身互质） |
四、欧拉函数的典型值表
| n | φ(n) | 说明 |
| 1 | 1 | 只有一个数，与自身互质 |
| 2 | 1 | 小于等于 2 的数中，只有 1 与 2 互质 |
| 3 | 2 | 1, 2 与 3 互质 |
| 4 | 2 | 1, 3 与 4 互质 |
| 5 | 4 | 1, 2, 3, 4 与 5 互质 |
| 6 | 2 | 1, 5 与 6 互质 |
| 7 | 6 | 1~6 都与 7 互质 |
| 8 | 4 | 1, 3, 5, 7 与 8 互质 |
| 9 | 6 | 1, 2, 4, 5, 7, 8 与 9 互质 |
| 10 | 4 | 1, 3, 7, 9 与 10 互质 |
五、欧拉函数的用途
1. 密码学：在 RSA 算法中，欧拉函数用于生成公钥和私钥。
2. 模运算：根据欧拉定理，若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n)。
3. 数论研究：欧拉函数是研究数的分布、素数分布的重要工具。
六、总结
欧拉函数 φ(n) 是一个描述与 n 互质的数的个数的数学函数，其计算方法依赖于 n 的质因数分解。通过公式 φ(n) = n × ∏(1 - 1/p)，可以高效地计算出 φ(n) 的值。欧拉函数不仅在理论数学中具有重要意义，在实际应用中也发挥着关键作用，尤其在现代密码学领域。