欧拉函数 基本定义 欧拉函数通常记作 φ(n)，定义为对于正整数 n，φ(n) 表示小于等于 n 且与 n 互素的正整数的个数。两个数互素意味着它们的最大公约数为 1。例如，φ(9) = 6，因为小于等于 9 且与 9 互素的正整数是 1, 2, 4, 5, 7, 8。 计算单个数的欧拉函数 如果 n 是素数，那么 φ(n) = n - 1，因为 1 到 n-1 的所有正整数都与 n 互素。 更一般地，如果 n 是某个素数 p 的 k 次幂（即 n = p^k），那么 φ(p^k) = p^k - p^{k-1}。这是因为在 1 到 p^k 的总共 p^k 个数中，只有那些是 p 的倍数的数才不与 p^k 互素，而 p 的倍数有 p^{k-1} 个（即 p 1, p 2, ..., p* p^{k-1}）。 欧拉函数的乘性性质 欧拉函数是一个乘性函数。这意味着如果两个正整数 m 和 n 互素（即 gcd(m, n) = 1），那么 φ(mn) = φ(m)φ(n)。这个性质非常重要，它允许我们将计算任意合数的欧拉函数分解为计算其素因数幂次的欧拉函数。 通用计算公式 结合乘性性质和素因数幂次的公式，我们可以得到计算任意正整数 n 的欧拉函数的通用公式。首先将 n 进行素因数分解：n = p₁^{k₁} * p₂^{k₂} * ... * pᵣ^{kᵣ}，其中 pᵢ 是不同的素数，kᵢ 是正整数。那么，φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/pᵣ)。这个公式直接由乘性性质和 φ(pᵢ^{kᵢ}) = pᵢ^{kᵢ} (1 - 1/pᵢ) 推导而来。 欧拉定理 欧拉函数在数论中一个核心的应用是欧拉定理。该定理指出：如果正整数 a 和 n 互素（即 gcd(a, n) = 1），那么 a^{φ(n)} ≡ 1 (mod n)。欧拉定理是费马小定理的推广（当 n 为素数 p 时，φ(p) = p-1，欧拉定理即变为 a^{p-1} ≡ 1 (mod p)）。这个定理在密码学（如RSA算法）和简化模幂运算中至关重要。