【欧拉函数公式】欧拉函数，又称φ函数，是数论中一个非常重要的函数，常用于研究整数的性质。它由瑞士数学家欧拉（Leonhard Euler）提出，用来计算小于或等于某个正整数n，并且与n互质的正整数的个数。这个函数在密码学、数论和组合数学中有广泛应用。
一、欧拉函数的基本定义
对于任意正整数n，欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。例如：
- φ(1) = 1
- φ(2) = 1
- φ(3) = 2
- φ(4) = 2
- φ(5) = 4
二、欧拉函数的计算公式
欧拉函数的计算公式基于n的素因数分解。若n可以分解为以下形式：
$$
n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}
$$
其中，$p_1, p_2, \ldots, p_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)
$$
三、欧拉函数的性质
1. 当n为质数时，φ(n) = n - 1
因为所有小于n的正整数都与n互质。
2. 若a和b互质，则φ(ab) = φ(a) × φ(b)
3. φ(1) = 1
4. φ(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)，其中p为质数，k ≥ 1
四、常见数值表
| n | φ(n) | 解释 |
| 1 | 1 | 只有1本身，与1互质 |
| 2 | 1 | 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, 2, 3, 4, 5, 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互质 |
五、应用举例
假设我们想求φ(12)，首先对12进行素因数分解：
$$
12 = 2^2 \times 3
$$
根据公式：
$$
\phi(12) = 12 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4
$$
验证：1, 5, 7, 11 都与12互质，共4个，结果正确。
六、总结
欧拉函数是一个描述数论中“互质”关系的重要工具，其计算依赖于数的素因数分解。通过掌握欧拉函数的公式和性质，可以更深入地理解数的结构及其在实际问题中的应用。无论是学习数学还是进入计算机科学领域，了解欧拉函数都是必不可少的知识点。