欧拉定理与欧拉函数
一、课上练习
编程练习
二、知识总结
✨ 核心思想
欧拉定理是费马小定理的推广，它揭示了整数幂运算在模运算下的周期性规律。欧拉函数 φ(n) 计算的是 1 到 n 中与 n 互素的正整数个数，是数论中最重要的函数之一。
✨ 欧拉函数 φ(n)
定义：φ(n) 表示 1 到 n 中与 n 互素的正整数的个数。
特殊值：
- φ(1) = 1
- 若 p 是素数，则 φ(p) = p - 1
- 若 p 是素数，则 φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1)
计算公式：
设 n 的质因数分解为 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，则：
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)
重要性质：
- 积性函数：若 gcd(a, b) = 1，则 φ(a × b) = φ(a) × φ(b)
- 因子和：∑(d|n) φ(d) = n，即 n 的所有因子的欧拉函数值之和等于 n
- 与素数的关系：n > 2 时，φ(n) 为偶数
✨ 欧拉定理
定理内容：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。
费马小定理（特殊情况）：若 p 为素数且 gcd(a, p) = 1，则 a^(p-1) ≡ 1 (mod p)。
推论：若 gcd(a, n) = 1，则 a^(-1) ≡ a^(φ(n)-1) (mod n)，即可利用欧拉定理求模逆元。
✨ 代码实现
1// 计算单个数的欧拉函数值
2// 时间复杂度 O(√n)
3long long euler_phi(long long n) {
4 long long result = n;
5 for (long long i = 2; i * i <= n; i++) {
6 if (n % i == 0) {
7 // i 是 n 的质因子
8 result = result / i * (i - 1);
9 while (n % i == 0) {
10 n /= i;
11 }
12 }
13 }
14 // 如果 n 还有大于 √n 的质因子
15 if (n > 1) {
16 result = result / n * (n - 1);
17 }
18 return result;
19}1#include <iostream>
2using namespace std;
3
4const int MAXN = 1000005;
5int phi_table[MAXN]; // 存储欧拉函数值
6int primes[MAXN]; // 素数表
7bool is_composite[MAXN]; // 是否为合数
8int prime_cnt = 0;
9
10// 线性筛法同时求欧拉函数
11void euler_sieve(int n) {
12 phi_table[1] = 1;
13 for (int i = 2; i <= n; i++) {
14 if (!is_composite[i]) {
15 // i 是素数
16 primes[prime_cnt++] = i;
17 phi_table[i] = i - 1;
18 }
19 for (int j = 0; j < prime_cnt && (long long)i * primes[j] <= n; j++) {
20 int k = i * primes[j];
21 is_composite[k] = true;
22 if (i % primes[j] == 0) {
23 // primes[j] 是 i 的因子
24 phi_table[k] = phi_table[i] * primes[j];
25 break;
26 } else {
27 // primes[j] 与 i 互素，利用积性
28 phi_table[k] = phi_table[i] * (primes[j] - 1);
29 }
30 }
31 }
32}
33
34int main() {
35 int n;
36 cin >> n;
37 euler_sieve(n);
38 // 输出 1~n 的欧拉函数值
39 for (int i = 1; i <= n; i++) {
40 cout << "phi(" << i << ") = " << phi_table[i] << endl;
41 }
42 return 0;
43}✨ 应用示例
示例 1：计算 φ(12)
12 = 2² × 3，所以 φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4。
验证：1 到 12 中与 12 互素的数为 {1, 5, 7, 11}，共 4 个。
示例 2：利用欧拉定理计算 7^222 mod 10
φ(10) = 10 × (1 - 1/2) × (1 - 1/5) = 4
因为 gcd(7, 10) = 1，由欧拉定理：7^4 ≡ 1 (mod 10)
222 = 4 × 55 + 2
所以 7^222 = (7^4)^55 × 7^2 ≡ 1^55 × 49 ≡ 9 (mod 10)
示例 3：求 3 模 10007 的逆元（10007 为素数）
由费马小定理：3^(10007-1) ≡ 1 (mod 10007)
所以 3^(-1) ≡ 3^(10005) (mod 10007)
用快速幂即可计算。
✨ 解题步骤详解
- 判断是否满足条件：使用欧拉定理前，必须确认 gcd(a, n) = 1
- 计算欧拉函数：对模数 n 进行质因数分解，代入公式计算 φ(n)
- 指数化简：将指数对 φ(n) 取模，即 a^b mod n = a^(b mod φ(n)) mod n（需要 gcd(a,n)=1）
- 快速幂计算：用快速幂算法计算最终结果
- 特殊情况处理：当 gcd(a, n) ≠ 1 时，需要用扩展欧拉定理
扩展欧拉定理：
a^b ≡ a^(b mod φ(n) + φ(n)) (mod n)，当 b ≥ φ(n) 时成立（不要求 gcd(a,n)=1）。
✨ 常见错误
- 忘记检查 gcd(a, n) = 1 的前提条件，直接套用欧拉定理
- 计算 φ(n) 时遗漏大于 √n 的质因子
- 线性筛中
i % primes[j] == 0时的 φ 值计算错误 - 数据范围较大时未使用
long long，导致乘法溢出 - 混淆欧拉定理和扩展欧拉定理的适用条件
- 在
result = result / i * (i - 1)中先除后乘的顺序不能颠倒，否则可能损失精度
✨ 算法评价
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 单个数 φ(n) | O(√n) | O(1) | 查询单个值 |
| 线性筛 φ | O(n) | O(n) | 批量求 1~n 的值 |
| 快速幂 + 欧拉定理 | O(√n + log b) | O(1) | 大幂模运算 |
欧拉函数和欧拉定理是竞赛数论的核心工具，在密码学（RSA 算法）、同余方程求解、组合计数等方面都有广泛应用。