欧拉函数

欧拉函数 (Euler’s Totient Function) 详解

欧拉函数 φ(n) 是数论中一个非常重要的函数，它表示小于或等于 n 的正整数中与 n 互质的数的个数。

定义

对于正整数 n，欧拉函数 φ(n) 定义为：

φ(n) = 小于或等于 n 的正整数中与 n 互质的数的个数

其中”互质”意味着两个数的最大公约数为1。

计算方法

1. 对于质数 p

如果 p 是质数，那么：

φ(p) = p - 1

因为1,2,…,p-1都与p互质。

2. 对于质数的幂 pᵏ

φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p)

因为在1到pᵏ之间，只有p的倍数不与pᵏ互质，这样的数有pᵏ⁻¹个。

3. 对于任意正整数 n

利用中国剩余定理和积性函数性质，如果n的标准质因数分解为：

n = p₁ᵏ¹ × p₂ᵏ² × ... × pₘᵏᵐ

那么：

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₘ)

示例计算

1. φ(10):

   10 = 2 × 5
   φ(10) = 10 × (1 - 1/2) × (1 - 1/5) = 10 × 1/2 × 4/5 = 4

   实际与10互质的数有1,3,7,9，共4个。

2. φ(12):

   12 = 2² × 3
   φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4

   实际与12互质的数有1,5,7,11，共4个。

在代码中的应用

在你提供的代码中，计算了φ(210):

210 = 2 × 3 × 5 × 7
φ(210) = 210 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5) × (1 - 1/7)
       = 210 × 1/2 × 2/3 × 4/5 × 6/7
       = 48

这意味着在每210个连续整数中，有48个数不被2,3,5,7整除（即与210互质）。

性质

1. 积性函数：如果m和n互质，则φ(mn) = φ(m)φ(n)
2. 欧拉定理：如果a和n互质，则a^φ(n) ≡ 1 (mod n)
3. 费马小定理：当n是质数p时的特例，a^(p-1) ≡ 1 (mod p)

欧拉函数在密码学（如RSA算法）、数论和组合数学中都有广泛应用。