【欧拉函数公式】欧拉函数是数论中一个重要的概念，广泛应用于密码学、数论以及组合数学等领域。它由瑞士数学家欧拉（Leonhard Euler）提出，用于计算小于或等于某个正整数 $ n $ 且与 $ n $ 互质的正整数的个数。通常用符号 $ \phi(n) $ 表示。
一、欧拉函数的基本定义
对于任意正整数 $ n $，欧拉函数 $ \phi(n) $ 的值表示在 $ 1 $ 到 $ n $ 的整数中，与 $ n $ 互质的数的个数。互质指的是两个数的最大公约数为 1。
例如：
- $ \phi(1) = 1 $（只有1）
- $ \phi(2) = 1 $（只有1）
- $ \phi(3) = 2 $（1和2）
- $ \phi(4) = 2 $（1和3）
二、欧拉函数的公式
欧拉函数的计算可以通过以下几种方式实现：
1. 质因数分解法
若已知 $ n $ 的质因数分解形式为：
$$
n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}
$$
则欧拉函数的公式为：
$$
\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)
$$
2. 递推公式
对于某些特殊形式的 $ n $，可以使用递推的方式计算 $ \phi(n) $。例如：
- 若 $ p $ 是质数，则 $ \phi(p) = p - 1 $
- 若 $ p $ 是质数，$ k $ 是正整数，则 $ \phi(p^k) = p^k - p^{k-1} $
三、欧拉函数的性质
| 性质 | 描述 | |
| 1 | 若 $ a $ 和 $ b $ 互质，则 $ \phi(ab) = \phi(a)\phi(b) $ | |
| 2 | 若 $ a $ 是质数，则 $ \phi(a) = a - 1 $ | |
| 3 | 对于任意正整数 $ n $，有 $ \sum_{d | n} \phi(d) = n $ |
| 4 | $ \phi(n) $ 是偶数，当 $ n > 2 $ 时 |
四、常见数值表
| 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 |
五、应用举例
1. 密码学中的应用：RSA算法依赖于欧拉函数来生成密钥对。
2. 模运算：在模 $ n $ 下，所有与 $ n $ 互质的数构成乘法群，其阶即为 $ \phi(n) $。
3. 数论问题：如求解同余方程、研究数的分布等。
六、总结
欧拉函数 $ \phi(n) $ 是数论中一个非常基础而重要的函数，通过质因数分解可以高效地计算其值。掌握它的性质和公式，有助于理解更复杂的数论问题和实际应用。无论是数学研究还是工程实践，欧拉函数都具有不可替代的作用。