欧拉定理 & 扩展欧拉定理

2023-08-14 08:56 由 Oneway` 发表于 #其他

观前提醒：「文章仅供学习和参考，如有问题请在评论区提出」

前置
欧拉定理
扩展欧拉定理
参考资料

前置

剩余类（同余类）

给定一个正整数 $n$ ，把所有的整数根据模 $n$ 的余数 $r\in [0, n - 1]$ 分为 $n$ 类，每一类就可以被表示为 $C_{r} = nx + r$ 。那么这类数所构成的集合就称为模 $n$ 的剩余类。

完全剩余系（完系）

给定一个正整数 $n$ ，有 $n$ 个不同的模 $n$ 的剩余类（因为余数 $r\in [0, n - 1]$ ）。

从这 $n$ 个不同的剩余类中各取出一个元素，总共 $n$ 个数，将这些数构成一个新的集合，则称这个集合为模 $n$ 的完全剩余系。

例如：$n = 5$ 时，$\{ 0, 1, 2, 3, 4 \}$ ， $\{ 5, 1, -3, 8, 9 \}$ 都是一个模 $5$ 的完全剩余系。

因为他们都有 $5$ 个不同的模 $5$ 的剩余类 $r \in [0, 4]$ 。

简化剩余系（缩系）

给定一个正整数 $n$ ，有 $\varphi(n)$ 个不同的模 $n$ 的余数 $r$ 与 $n$ 互质的剩余类。

从这 $\varphi(n)$ 个剩余类中各取出一个元素，总共 $\varphi(n)$ 个数，将这些数构成一个新的集合，则称这个集合为模 $n$ 的简化剩余系。

$\varphi(n)$ 为欧拉函数，$1 \sim n$ 中与 $n$ 互质的数的个数。

例如：$n = 5$ 时，$\{ 1, 2, 3, 4\}$ 是一个模 $5$ 的简化剩余系。$n = 10$ 时，$1, 3, 7, 9$ 是一个模 $10$ 的简化剩余系。

显然，模 $n$ 的简化剩余系中所有的数都与 $n$ 互质。

欧拉函数

$1 \sim n$ 与 $n$ 互质的数的个数称为欧拉函数，记作 $\varphi(n)$ 。

\[\begin{align} n = p_{1}^{a_{1}} p_{2}^{a_{2}} p_{3}^{a_{3}} ... p_{k}^{a_{k}}\\ \varphi(n) = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \end{align} \]

欧拉定理

定义：若 $\gcd(a, n) = 1$ ，则 $a^{\varphi(n)} \equiv 1 \pmod{n} $ 。

证明

设 $\{ r_{1}, r_{2},...r_{\varphi(n)}\}$ 是一个模 $n$ 的简化剩余系。

那么 $r_{i}$ 就是和 $n$ 互质，又因为 $\gcd(a, n) = 1$ ，所以 $a$ 与 $n$ 也是互质的。

那么 $\{ ar_{1}, ar_{2},...ar_{\varphi(n)}\}$ 也是一个模 $n$ 的简化剩余系。所以

\[\begin{align} {\textstyle \prod_{i = 1}^{\varphi(n)}}r_{i} &\equiv {\textstyle \prod_{i = 1}^{\varphi(n)}} ar_{i} \pmod{n} \\ {\textstyle \prod_{i = 1}^{\varphi(n)}}r_{i} &\equiv a ^{\varphi(n)}{\textstyle \prod_{i = 1}^{\varphi(n)}} r_{i} \pmod{n} \\ a ^{\varphi(n)} &\equiv 1 \pmod{n} \\ \end{align} \]

扩展欧拉定理

\[a^{b} = \begin{cases} a ^ {b}&, b < \varphi(m), \mod (m)\\ a ^ {b \mod \varphi(m) + \varphi(m)}&, b\ge \varphi(m), \mod(m) \end{cases} \]

P5091 【模板】扩展欧拉定理 - 洛谷

给定三个正整数 $a, b, m$ ，求 $a ^ b \mod m$ 。

$1 \le a \le 10^9, 1 \le m \le 10^9, 1 \le b \le 10^{20000000}$ 。

可以根据扩展欧拉定理，当 $b < \varphi(m)$ 时，用快速幂求解，当 $b \ge \varphi(m)$ 时，通过定理进行降幂，然后再用快速幂求解。

实现代码

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

typedef long long LL;

// 快速幂, a ^ k % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 求 n 的欧拉函数
int get_phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res = res / i * (i - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

// 对 b 进行降幂
int de_pow(string s, int phi) {
    int res = 0;
    bool flag = false;
    for (int i = 0; s[i]; i++) {
        res = res * 10 + s[i] - '0';
        if (res >= phi) flag = true, res %= phi;
    }
    if (flag) res += phi;
    return res;
}

int main() {
    int a, m;
    string b;
    cin >> a >> m >> b;

    int phi = get_phi(m);
    int B = de_pow(b, phi);
    cout << qmi(a, B, m) << "\n";

    return 0;
}

参考资料

522 剩余系欧拉定理扩展欧拉定理_董晓算法