数论中的欧拉函数究竟是什么？
摘要：欧拉函数（Euler's totient function），记作 (phi(n))，是数论中一个非常重要的函数。它的定义很简单： 对于正整数 (n)，(phi(n)) 表示小于等于 (n) 且与
欧拉函数（Euler's totient function），记作 \(\phi(n)\)，是数论中一个非常重要的函数。它的定义很简单：
对于正整数 \(n\)，\(\phi(n)\) 表示小于等于 \(n\) 且与 \(n\) 互质的正整数的个数。
\(\phi(1) = 1\)（只有 1 与 1 互质）
\(\phi(5) = 4\)（1, 2, 3, 4 都与 5 互质）
\(\phi(9) = 6\)（与 9 互质的数：1, 2, 4, 5, 7, 8）
\(\phi(10) = 4\)（与 10 互质的数：1, 3, 7, 9）
欧拉函数积性性质
欧拉函数的积性性质（multiplicative property）是它最重要的特性之一，也是各种计算和应用的基础。这个性质说的是：
如果 \(m\) 和 \(n\) 互质（即 \(\gcd(m, n) = 1\)），那么 \(\phi(mn) = \phi(m) \cdot \phi(n)\)
这个性质的证明需要使用中国剩余定理，可以证明 \(\phi(mn)\) 集合中包含的每个数和 \(\phi(m)\) 和 \(\phi(n)\) 集合的直积元素一一对应，所以他们的数量相等（具体证明略）。