欧拉函数的性质：欧拉函数的性质

定义

欧拉函数 φ(n) 定义为：
φ(n) = { k ∈ [1, n] | gcd(k, n) = 1 }

• φ(1) = 1（与 1 互质的数只有 1）
• φ(2) = 1（与 2 互质的数只有 1）
• φ(3) = 2（与 3 互质的数有 1、2）
• φ(4) = 2（与 4 互质的数有 1、3）

函数值

• 若 n 是质数，则 φ(n) = n - 1
• 若 n = p^k（p 为质数，k 为正整数），则 φ(n) = p^k - p^{k-1} = p^{k-1}(p - 1)
• 若 n = p₁^{k₁} × p₂^{k₂} × ⋯ × p_m^{k_m}（p₁, p₂, ⋯, p_m 为不同质数），则
  φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ⋯ × (1 - 1/p_m)

与模运算的关系

欧拉定理指出：若 a 与 n 互质，则
a^{φ(n)} ≡ 1 (mod n)

• 取 n = 10，φ(10) = 4，a = 3（与 10 互质），则 3⁴ = 81 ≡ 1 (mod 10)

与完全互素集合的关系

φ(n) 表示模 n 的乘法群的大小，即模 n 下与 n 互质的整数个数。

乘性函数性质

欧拉函数是积性函数，即若 m 和 n 互质，则
φ(m × n) = φ(m) × φ(n)

• φ(6) = φ(2 × 3) = φ(2) × φ(3) = 1 × 2 = 2
• φ(15) = φ(3 × 5) = φ(3) × φ(5) = 2 × 4 = 8

莫比乌斯反演公式

欧拉函数与莫比乌斯函数 μ(n) 有关系：
φ(n) = ∑_{d|n} μ(d) × (n/d)

其他性质

• φ(n) 是偶数，除非 n = 1 或 2
• 若 n > 1，则 φ(n) < n
• 若 n 是平方因子数，则 φ(n) 是偶数

应用

• 密码学：欧拉函数在 RSA 加密算法中用于计算模数的欧拉函数值
• 数论问题：用于计算模逆元、判断模运算的周期等
• 算法设计：在求解与 n 互质的数的个数时，欧拉函数提供高效方法