欧拉函数（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}\)，那么：
例题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 = np = 2# 质因数分解while p * p <= n:if n % p == 0:while n % p == 0:n //= presult -= result // pp += 1if n > 1:result -= result // nreturn result
欧拉定理
欧拉定理是欧拉函数最重要的应用之一，它是费马小定理的推广：
如果 \(\gcd(a, n) = 1\)，那么：
例子：取 \(n = 10\)，\(\phi(10) = 4\)，\(a = 3\)（\(\gcd(3, 10) = 1\)）：
欧拉函数 \(\phi(n)\) 作为数论中计算与 \(n\) 互质正整数个量的关键工具，其核心价值体现在欧拉定理 \(a^{\phi(n)} \equiv 1 \pmod{n}\)（当 \(\gcd(a,n)=1\) 时）这一优美等式中，这一定理不仅为模逆元计算和模幂运算提供了理论基础，更是现代密码学（尤其是RSA加密算法）的安全基石，通过将难以分解的大数质因数与相对容易的模幂运算相关联，构建了非对称加密的核心机制，使安全的数据传输成为可能。