数论中的欧拉函数究竟是什么？

欧拉函数（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)\) 集合的直积元素一一对应，所以他们的数量相等（具体证明略）。让我们通过例子来理解这个证明： 取 \(m = 3\)，\(n = 4\)（互质），\(mn = 12\) \(A = \{1, 2\}\)（与 3 互质的数），\(\phi(3) = 2\) \(B = \{1, 3\}\)（与 4 互质的数），\(\phi(4) = 2\) \(C = \{1, 5, 7, 11\}\)（与 12 互质的数），\(\phi(12) = 4\) 建立对应关系： \((a, b)\) 同余方程组 解 \(x\) \((1, 1)\) \(x \equiv 1 \pmod{3}, x \equiv 1 \pmod{4}\) \(x = 1\) \((1, 3)\) \(x \equiv 1 \pmod{3}, x \equiv 3 \pmod{4}\) \(x = 7\) \((2, 1)\) \(x \equiv 2 \pmod{3}, x \equiv 1 \pmod{4}\) \(x = 5\) \((2, 3)\) \(x \equiv 2 \pmod{3}, x \equiv 3 \pmod{4}\) \(x = 11\) 确实建立了 \(A \times B\) 到 \(C\) 的一一对应！ 如何计算欧拉函数 素数的情况：如果 \(p\) 是素数，显然 \(\phi(p) = p - 1\) 例：\(\phi(7) = 6\)，\(\phi(13) = 12\) 合数的情况：有了积性性质，我们就能推导出欧拉函数的通用计算公式： 如果 \(n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)，那么： \[\begin{aligned} \phi(n) &= \phi(p_1^{k_1}) \cdot \phi(p_2^{k_2}) \cdots \phi(p_r^{k_r}) \\ &= (p_1^{k_1} - p_1^{k_1-1}) \cdot (p_2^{k_2} - p_2^{k_2-1}) \cdots (p_r^{k_r} - p_r^{k_r-1}) \\ &= n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right) \end{aligned} \] 例题1：计算 \(\phi(100)\) 质因数分解：\(100 = 2^2 \cdot 5^2\) \(\phi(100) = 100 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40\) 例题2：计算 \(\phi(36)\) 质因数分解：\(36 = 2^2 \cdot 3^2\) \(\phi(36) = 36 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12\) def euler_phi(n): """计算欧拉函数 φ(n)""" result = n p = 2 # 质因数分解 while p * p <= n: if n % p == 0: while n % p == 0: n //= p result -= result // p p += 1 if n > 1: result -= result // n return result 欧拉定理 欧拉定理是欧拉函数最重要的应用之一，它是费马小定理的推广： 如果 \(\gcd(a, n) = 1\)，那么： \[a^{\phi(n)} \equiv 1 \pmod{n} \] 例子：取 \(n = 10\)，\(\phi(10) = 4\)，\(a = 3\)（\(\gcd(3, 10) = 1\)）： \[3^4 = 81 \equiv 1 \pmod{10} \] 欧拉函数 \(\phi(n)\) 作为数论中计算与 \(n\) 互质正整数个量的关键工具，其核心价值体现在欧拉定理 \(a^{\phi(n)} \equiv 1 \pmod{n}\)（当 \(\gcd(a,n)=1\) 时）这一优美等式中，这一定理不仅为模逆元计算和模幂运算提供了理论基础，更是现代密码学（尤其是RSA加密算法）的安全基石，通过将难以分解的大数质因数与相对容易的模幂运算相关联，构建了非对称加密的核心机制，使安全的数据传输成为可能。