数论基础

【第四讲】

第四讲我们要学习的概念有：

欧拉函数
欧拉定理
扩展欧拉定理

一、欧拉函数

在上一讲中，我们了解到了欧拉函数计算逆元的方法，接下来我们来详细探究欧拉函数

1.1 定义

欧拉函数 $\phi(n)$ 表示小于等于 $n$ 的正整数中与 $n$ 互质（ $\gcd(i,n)=1$ ）的数的个数

例如：

$\phi(6)$ ：小于等于 6 且与 6 互质的数有 1 和 5，因此 $\phi(6)=2$
$\phi(7)$ ：小于等于 7 且与 7 互质的数有 1、2、3、4、5、6，因此 $\phi(7)=6$
$\phi(8)$ ：小于等于 8 且与 8 互质的数有 1、3、5、7，因此 $\phi(8)=4$

1.2 计算公式

让我们回忆一下算术基本定理，每个大于1的正整数都可以唯一地表示为有限个质数的乘积

n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_n}=\prod_{i=1}^{n}p_{i}^{a_{i}}

其中 $p$ 表示质数，则 欧拉函数

\phi(n)=n\times (1-\frac{1}{p_{1}})\times (1-\frac{1}{p_{2}})\times ...\times (1-\frac{1}{p_{k}})=n\prod_{p|n}(1-\frac{1}{p})

特别地，当 $p$ 为质数时， $\phi(p)=p-1$ ，即 $p$ 和 $1\sim p-1$ 的数均互质

另外，欧拉函数为 积性函数 ，满足 $\phi(m)\times \phi(n)=\phi(mn)$

欧拉函数计算公式的推导可以从 概率论 和 容斥原理 两个角度展开，以下给出详细证明过程：

1.2.1 从概率论角度推导

核心思想

欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 的数中与 $n$ 互质的数的比例，即 $\frac{\varphi(n)}{n}$ 。我们可以通过计算每个质因数不整除随机数的概率，然后利用独立性假设得到这个比例。

推导步骤

质因数分解：设 $n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$ ，其中 $p_i$ 是 $n$ 的不同质因数。
事件定义：对于每个质因数 $p_i$ ，定义事件 $A_i$ 为“一个随机数 $m \leq n$ 能被 $p_i$ 整除”。
概率计算：
- 事件 $A_i$ 发生的概率为 $\frac{1}{p_i}$ （因为在 $1$ 到 $n$ 中，每 $p_i$ 个数中有一个能被 $p_i$ 整除）。
- 事件 $A_i$ 不发生的概率为 $1 - \frac{1}{p_i}$ 。
独立性假设：假设事件 $A_1, A_2, \dots, A_k$ 相互独立（实际上在模 $n$ 下近似成立），则所有事件都不发生的概率为：
$\prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$
结论：与 $n$ 互质的数的比例即为上述概率，因此：
$\frac{\varphi(n)}{n} = \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) \implies \varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

1.2.2 从集合容斥原理角度推导

核心思想

利用容斥原理计算 $1$ 到 $n$ 中不被任何质因数 $p_1, p_2, \dots, p_k$ 整除的数的个数。

推导步骤

全集与子集：设全集 $U = \{1, 2, \dots, n\}$ ，子集 $A_i = \{m \in U \mid p_i \mid m\}$ （即被 $p_i$ 整除的数）。
目标：计算 $\left|U - \bigcup_{i=1}^{k} A_i\right|$ ，即不被任何 $p_i$ 整除的数的个数。
容斥原理公式：
$\left|\bigcup_{i=1}^{k} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{k-1} |A_1 \cap A_2 \cap \dots \cap A_k|$
计算各交集的大小：
- $|A_i| = \frac{n}{p_i}$ （被 $p_i$ 整除的数的个数）。
- $|A_i \cap A_j| = \frac{n}{p_i p_j}$ （同时被 $p_i$ 和 $p_j$ 整除的数的个数）。
- 一般地， $|A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_s}| = \frac{n}{p_{i_1} p_{i_2} \dots p_{i_s}}$ 。
代入容斥公式：
$\left|\bigcup_{i=1}^{k} A_i\right| = n \left( \sum_{i} \frac{1}{p_i} - \sum_{i<j} \frac{1}{p_i p_j} + \sum_{i<j<k} \frac{1}{p_i p_j p_k} - \dots + (-1)^{k-1} \frac{1}{p_1 p_2 \dots p_k} \right)$
化简：
$\left|U - \bigcup_{i=1}^{k} A_i\right| = n - \left|\bigcup_{i=1}^{k} A_i\right| = n \left(1 - \sum_{i} \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \dots + (-1)^{k} \frac{1}{p_1 p_2 \dots p_k} \right)$
注意到右边括号内的表达式恰好是乘积展开式：
$\prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$
因此
$\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

1.2.3 示例

以 $n = 6$ 为例验证两种推导方法：

质因数分解： $6 = 2 \times 3$ ，质因数为 $2$ 和 $3$
概率论角度：
- 随机数不被 $2$ 整除的概率： $1 - \frac{1}{2} = \frac{1}{2}$
- 随机数不被 $3$ 整除的概率： $1 - \frac{1}{3} = \frac{2}{3}$
- 两者同时成立的概率： $\frac{1}{2} \times \frac{2}{3} = \frac{1}{3}$
- 因此 $\varphi(6) = 6 \times \frac{1}{3} = 2$ ，与实际结果一致（ $1$ 和 $5$ 与 $6$ 互质）
容斥原理角度：
- 被 $2$ 整除的数： $2, 4, 6$ （共 $3$ 个）
- 被 $3$ 整除的数： $3, 6$ （共 $2$ 个）
- 同时被 $2$ 和 $3$ 整除的数： $6$ （共 $1$ 个）
- 根据容斥公式： $3 + 2 - 1 = 4$ ，因此不被任何质因数整除的数有 $6 - 4 = 2$ 个

1.3 代码

1.3.1 计算欧拉函数

C++：

#include <bits/stdc++.h>
using namespace std;

// 计算单个n的欧拉函数φ(n)
long long euler_phi(long long n) {
    long long res = n; // 初始值为n
    // 分解质因数
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) { // p是n的质因数
            // 乘以(1 - 1/p)，即先除以p再乘以(p-1)
            res = res / p * (p - 1);
            // 去除所有p的因子（避免重复计算）
            while (n % p == 0) {
                n /= p;
            }
        }
    }
    // 若剩余n是大于1的质数（未被分解）
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

// 测试
int main() {
    cout << euler_phi(6) << endl;  // 输出：2（1,5与6互质）
    cout << euler_phi(7) << endl;  // 输出：6（1-6与7互质）
    cout << euler_phi(8) << endl;  // 输出：4（1,3,5,7与8互质）
    return 0;
}

Python:

def euler_phi(n):
    res = n  # 初始值为n
    # 分解质因数
    p = 2
    while p * p <= n:
        if n % p == 0:  # p是n的质因数
            # 乘以(1 - 1/p)
            res = res // p * (p - 1)
            # 去除所有p的因子
            while n % p == 0:
                n //= p
        p += 1
    # 剩余n为质数
    if n > 1:
        res = res // n * (n - 1)
    return res

# 测试
print(euler_phi(6))  # 输出：2
print(euler_phi(7))  # 输出：6
print(euler_phi(8))  # 输出：4

1.3.2 预处理欧拉函数

C++：

#include <bits/stdc++.h>
using namespace std;

// 预处理1到n的欧拉函数，返回phi数组（phi[0]无用，phi[1..n]有效）
vector<int> euler_phi_sieve(int n) {
    vector<int> phi(n + 1);
    // 初始化：phi[i] = i
    for (int i = 0; i <= n; ++i) {
        phi[i] = i;
    }
    // 筛法更新
    for (int p = 2; p <= n; ++p) {
        if (phi[p] == p) {  // p是质数（未被处理过）
            for (int m = p; m <= n; m += p) {  // 遍历p的所有倍数
                phi[m] = phi[m] / p * (p - 1);
            }
        }
    }
    return phi;
}

// 测试
int main() {
    int n = 10;
    vector<int> phi = euler_phi_sieve(n);
    for (int i = 1; i <= n; ++i) {
        cout << "phi(" << i << ") = " << phi[i] << endl;
    }
    return 0;
}

Python：

def euler_phi_sieve(n):
    phi = list(range(n + 1))  # 初始化：phi[i] = i
    for p in range(2, n + 1):
        if phi[p] == p:  # p是质数
            for m in range(p, n + 1, p):  # 遍历p的倍数
                phi[m] = phi[m] // p * (p - 1)
    return phi

# 测试
n = 10
phi = euler_phi_sieve(n)
for i in range(1, n + 1):
    print(f"phi({i}) = {phi[i]}")

二、欧拉定理

2.1 定理内容

若整数 $a$ 与正整数 $n$ 互质，即 $\gcd(a,n)=1$ ，则

a^{\phi(n)}\equiv1(\mod n)

其中 $\phi(n)$ 是欧拉函数，表示小于等于 $n$ 且与 $n$ 互质的正整数的个数

证明：

构造简化剩余系：设模 $n$ 的简化剩余系为 $S = \{r_1, r_2, \dots, r_{\phi(n)}\}$ ，其中每个 $r_i$ 满足 $1 \leq r_i \leq n$ 且 $\gcd(r_i, n) = 1$ 。
生成新的简化剩余系：由于 $a$ 与 $n$ 互质，将 $S$ 中每个元素乘以 $a$ 后，得到集合
$T = \{a \cdot r_1, a \cdot r_2, \dots, a \cdot r_{\phi(n)}\}$
性质1 ：每个 $a \cdot r_i$ 仍与 $n$ 互质（因为 $\gcd(a, n) = 1$ 且 $\gcd(r_i, n) = 1$ ，乘积的最大公约数为1）

性质2： $T$ 中元素模 $n$ 两两不同余（若 $a \cdot r_i \equiv a \cdot r_j \pmod{n}$ ，则由 $\gcd(a, n) = 1$ 可消去 $a$ ，得
$r_i \equiv r_j \pmod{n}$
与 $S$ 是简化剩余系矛盾

因此， $T$ 也是模 $n$ 的简化剩余系，与 $S$ 包含的元素完全相同（仅顺序可能不同）
乘积相等性：由于 $S$ 和 $T$ 是同一集合的不同排列，它们的元素乘积模 $n$ 相等：
$\prod_{i=1}^{\phi(n)} r_i \equiv \prod_{i=1}^{\phi(n)} (a \cdot r_i) \pmod{n}$
化简推导：

右边乘积可整理为
$\prod_{i=1}^{\phi(n)} (a \cdot r_i) = a^{\phi(n)} \cdot \prod_{i=1}^{\phi(n)} r_i$
因此有
$\prod_{i=1}^{\phi(n)} r_i \equiv a^{\phi(n)} \cdot \prod_{i=1}^{\phi(n)} r_i \pmod{n}$
由于每个 $r_i$ 与 $n$ 互质，它们的乘积也与 $n$ 互质（即 $\gcd\left(\prod_{i=1}^{\phi(n)} r_i, n\right) = 1$ ），因此可两边同时消去乘积项，得：
$1 \equiv a^{\phi(n)} \pmod{n}$
即 $a^{\phi(n)} \equiv 1 \pmod{n}$ ，定理得证

2.2 费马小定理

欧拉定理 是 费马小定理 的推广，而 费马小定理 是 欧拉定理 的特殊情况

当 $n$ 为质数 $p$ 时，欧拉函数 $\phi(p)=p-1$ ，此时欧拉定理退化为费马小定理

a^{p-1}\equiv1(\mod p)

2.3 欧拉降幂公式

欧拉降幂的本质是利用欧拉定理将指数 $b$ 压缩为一个较小的数，使得 $a^{b}\mod m$ 的结构不变

由欧拉定理，若 $\gcd(a,m)=1$ ，则

a^{\phi(m)\equiv q}\ (\mod m)

因此，对于任意指数 $b$ ，可将其表示为

b=q\cdot \phi(m)+r

其中 $q$ 是整数， $0\le r<\phi(m)$

此时

a^{b}\equiv(a^{\phi(m)})^{q}\cdot a^{r}\equiv 1^{q}\cdot a^{r}\equiv a^{r}\ (\mod m)

即

a^b \equiv a^{b \mod \phi(m)} \mod m

示例：

计算 $5^{1000000000}\mod 7$ 。

步骤：

计算 $phi(7)$ ：7是质数， $phi(7) = 7 - 1 = 6$ ；

验证 $gcd(5, 7) = 1$ ，满足基本降幂条件

降幂：指数 $1000000000 \mod 6$ ，因 $1000000000 = 6 \times 166666666 + 4$ ，故 $r = 4$

计算： $5^4 \mod 7 = 625 \mod 7 = 625 - 7 \times 89 = 625 - 623 = 2$
结果： $5^{1000000000} \mod 7 = 2$ 。

C++：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 计算最大公约数
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算欧拉函数φ(n)
ll euler_phi(ll n) {
    ll res = n;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

// 快速幂：计算 (a^b) mod m
ll fast_pow(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

// 判断大指数字符串b是否 >= phi(m)
bool is_b_ge_phi(const string &b_str, ll phi) {
    // 若phi为0，特殊处理（实际phi(m)>=1）
    if (phi == 0) return true;
    // 将phi转为字符串比较
    string phi_str = to_string(phi);
    if (b_str.size() > phi_str.size()) return true;
    if (b_str.size() < phi_str.size()) return false;
    // 长度相等时逐位比较
    return b_str >= phi_str;
}

// 大指数字符串b对mod取模
ll mod_big(const string &b_str, ll mod) {
    ll res = 0;
    for (char c : b_str) {
        res = (res * 10 + (c - '0')) % mod;
    }
    return res;
}

// 欧拉降幂主函数（支持大指数字符串输入）
ll euler_pow(ll a, const string &b_str, ll m) {
    if (m == 1) return 0; // 任何数模1都为0
    ll phi = euler_phi(m);
    ll g = gcd(a, m);
    
    // 计算降幂后的指数
    ll exp;
    if (g == 1) {
        // 基本降幂：a与m互质
        exp = mod_big(b_str, phi);
    } else {
        // 扩展降幂：a与m不互质
        if (is_b_ge_phi(b_str, phi)) {
            exp = mod_big(b_str, phi) + phi;
        } else {
            // 指数小于phi，直接转换为整数计算
            exp = stoll(b_str); // 注意：若b_str过长可能溢出，实际可优化为逐位计算幂
        }
    }
    
    // 计算降幂后的结果
    return fast_pow(a, exp, m);
}

int main() {
    // 示例：计算5^1000000000 mod 7
    ll a = 5;
    string b_str = "1000000000"; // 大指数用字符串表示
    ll m = 7;
    cout << euler_pow(a, b_str, m) << endl; // 输出：2
    return 0;
}

Python:

import math

# 计算欧拉函数φ(n)
def euler_phi(n):
    res = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res -= res // p
        p += 1
    if n > 1:
        res -= res // n
    return res

# 快速幂：计算 (a^b) mod m
def fast_pow(a, b, m):
    res = 1
    a %= m
    while b > 0:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

# 欧拉降幂主函数（支持大指数，Python天然支持大整数）
def euler_pow(a, b, m):
    if m == 1:
        return 0  # 任何数模1都为0
    phi = euler_phi(m)
    g = math.gcd(a, m)
    
    # 计算降幂后的指数
    if g == 1:
        # 基本降幂：a与m互质
        exp = b % phi
    else:
        # 扩展降幂：a与m不互质
        if b >= phi:
            exp = b % phi + phi
        else:
            exp = b  # 指数小于phi，直接使用原指数
    
    # 计算降幂后的结果
    return fast_pow(a, exp, m)

# 示例：计算5^1000000000 mod 7
a = 5
b = 1000000000  # Python支持直接处理大整数
m = 7
print(euler_pow(a, b, m))  # 输出：2

三、扩展欧拉定理

欧拉定理要求 $a$ 与 $n$ 互质，即 $\gcd(a,n)=1$ ，但实际问题中并不能总是满足这一情况，于是就有了对欧拉定理的扩展， 扩展欧拉定理

3.1 定理内容

若 $m$ 是正整数， $a$ 是任意整数， $b$ 是正整数，则：

a^b \equiv \begin{cases} a^b \ (\mod m) & \text{若 } b < \phi(m) \\ a^{b \mod \phi(m) + \phi(m)} \ (\mod m)& \text{若 } b \geq \phi(m) \end{cases}

特别地，当 $\gcd(a,m)=1$ 时，无论 $b$ 是否大于 $\phi(m)$ ，均可以使用

a^{b}\equiv a^{b\mod \phi(m)}\ (\mod m)

即欧拉降幂公式

3.2 定理证明

扩展欧拉定理的证明需分情况讨论，核心思路是利用质因数分解和数学归纳法

情况1 ： $\gcd(a,m)=1$

此时退化为欧拉定理，直接应用欧拉降幂公式，即 $a^{b}\equiv a^{b\mod \phi(m)}\ (\mod m)$

情况2 ： $\gcd(a,m)\ne 1$ 且 $b\ge\phi(m)$

需证 $a^{b}=a^{b \mod \phi(m) + \phi(m)} \ (\mod m)$

（1）质因数分解：设 $m = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}$ ，只需证明对每个质数幂 $p_i^{k_i}$ 成立，即

a^b \equiv a^{b \mod \phi(p_i^{k_i}) + \phi(p_i^{k_i})} \mod p_i^{k_i}

再由 中国剩余定理（CRT） 合并

（2）单质数幂的证明：

设 $p$ 是质数， $k \geq 1$ ，需证
$a^b \equiv a^{b \mod \phi(p^k) + \phi(p^k)} \mod p^k$
其中 $\phi(p^k) = p^k - p^{k-1}$
若 $p \mid a$ （即 $a$ 含质因数 $p$ ），设 $a = p^s \cdot t$ （ $s \geq 1$ 且 $\gcd(t, p) = 1$ ）：
- 当 $s \geq k$ 时，
  $a^b \equiv 0 \mod p^k$
  且
  $a^{b \mod \phi(p^k) + \phi(p^k)} \equiv 0 \mod p^k$
  等式成立
- 当 $1 \leq s < k$ 时，由欧拉定理
  $t^{\phi(p^k)} \equiv 1 \mod p^k$
  故
  $t^b = t^{b \mod \phi(p^k) + \phi(p^k) \cdot q} \equiv t^{b \mod \phi(p^k)} \cdot (t^{\phi(p^k)})^q \equiv t^{b \mod \phi(p^k)} \mod p^{k-s}$
  两边同乘 $p^s$ 得
  $a^b \equiv a^{b \mod \phi(p^k) + \phi(p^k)} \mod p^k$

（3）合并结果：对所有质数幂成立，故对 $m$ 成立。

3.3 示例

计算 $2^{1000} \mod 12$ ：

步骤1：分解 $12 = 2^2 \times 3$ ，计算 $\phi(12) = 12 \times (1-\frac{1}{2}) \times (1-\frac{1}{3}) = 4$ 。

步骤2： $gcd(2, 12) = 2 \neq 1$ ，且 $1000 \geq 4$ ，适用扩展形式。

步骤3：降幂： $1000 \mod 4 + 4 = 0 + 4 = 4$ 。

步骤4：计算 $2^4 \mod 12 = 16 \mod 12 = 4$ ，故 $2^{1000} \equiv 4 \mod 12$ 。

C++:

#include <bits/stdc++.h>
using namespace std;

// 计算欧拉函数φ(n)
int euler_phi(int n) {
    int res = n;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

// 快速幂：计算 (base^exp) % mod
int fast_pow(int base, int exp, int mod) {
    int result = 1;
    base %= mod; // 确保base在模范围内
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// 扩展欧拉定理计算：a^b mod m（处理a与m不互质的情况）
int extended_euler(int a, int b, int m) {
    if (m == 1) return 0; // 任何数模1为0
    
    int phi = euler_phi(m);
    int g = gcd(a, m);
    
    // 扩展欧拉定理条件：a与m不互质且b >= phi(m)
    if (g != 1 && b >= phi) {
        int exp = (b % phi) + phi; // 降幂公式
        return fast_pow(a, exp, m);
    } else {
        // 不满足扩展条件时直接计算（包括b < phi的情况）
        return fast_pow(a, b, m);
    }
}

int main() {
    // 示例：计算2^1000 mod 12
    int a = 2, b = 1000, m = 12;
    cout << extended_euler(a, b, m) << endl; // 输出：4
    return 0;
}

Python:

import math

# 计算欧拉函数φ(n)
def euler_phi(n):
    res = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res -= res // p
        p += 1
    if n > 1:
        res -= res // n
    return res

# 快速幂：计算 (base^exp) % mod
def fast_pow(base, exp, mod):
    result = 1
    base %= mod  # 确保base在模范围内
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

# 扩展欧拉定理计算：a^b mod m（处理a与m不互质的情况）
def extended_euler(a, b, m):
    if m == 1:
        return 0  # 任何数模1为0
    
    phi = euler_phi(m)
    g = math.gcd(a, m)
    
    # 扩展欧拉定理条件：a与m不互质且b >= phi(m)
    if g != 1 and b >= phi:
        exp = (b % phi) + phi  # 降幂公式
        return fast_pow(a, exp, m)
    else:
        # 不满足扩展条件时直接计算（包括b < phi的情况）
        return fast_pow(a, b, m)

# 示例：计算2^1000 mod 12
a = 2
b = 1000
m = 12
print(extended_euler(a, b, m))  # 输出：4

数论基础4

数论基础

【第四讲】

一、欧拉函数

1.1 定义

1.2 计算公式

1.2.1 从概率论角度推导

核心思想

推导步骤

1.2.2 从集合容斥原理角度推导

核心思想

推导步骤

1.2.3 示例

1.3 代码

1.3.1 计算欧拉函数

1.3.2 预处理欧拉函数

二、欧拉定理

2.1 定理内容

2.2 费马小定理

2.3 欧拉降幂公式

三、扩展欧拉定理

3.1 定理内容

3.2 定理证明

3.3 示例