剩余系概念和欧拉、扩展欧拉定理

剩余类（又称同余类）

定义 ：给定一个正整数$n$，把所有整数根据模$n$的余数$r \in [0,n- 1 ]$ 分为 $n$ 类，每一类表示为 $C_r = nx + r$ 的形式，这类数所构成的一个集合称为模 $n$ 的剩余类 。

​ 例：$n = 7,r = 4$，则 $C_4 = 7x + 4$ 为模$7$的一个剩余类

完全剩余系

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

例：$n = 7$,则$\{0,1,2,3,4,5,6\}$是一个完全剩余系，而$\{5,-1,7,8,9,3,11\}$也是一个完全剩余系

简化剩余系 (又称 缩系)

定义 ：给定一个正整数 $n$ ,有$n$个不同的模$n$的剩余类,而我们可以挑出$\phi(n)个模n的余数与n互质且各不相同的剩余类$ ，从这 $\phi(n)$ 个剩余类中各取出一个元素，总共 $\phi(n)$ 个数，将这些数构成一个新的集合，则称这个集合为模 $n$ 的简化剩余系。

例 ：$n = 7$，由于 $n$ 是个质数，所以可以知道在$[0,n-1]$ 中满足与 $n$ 互质的数的个数有 $n - 1$ 个，也就是 模n余 $\{1,2,3,4,5,6\}$ ,从这6个余数所属的剩余系各选一个数，比如说$\{1,2,3,4,5,6\}$就构成模$n$的缩系

​ $n = 6$，在 $[0,n - 1]$ 中与$n$互质的数有 $\{1,5\}$ ，则这 $2$ 个余数所属的剩余系各选一个数比如说$\{1,5\}$ 就构成了模 $n$ 的缩系。

欧拉函数

定义 ：欧拉函数$\phi(n)$表示在$[1,n]$中与 $n$ 互质的数的个数 。

定理 ：若正整数 $n$ 的标准分解式为 $n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}…p_k^{\alpha_k}$ ，则有
$$\phi(n) = \prod_{i = 1}^{k}(p_i^{\alpha_i} - p_{i-1}^{\alpha_{i-1}}) = n\prod_{i = 1}^{k}(1 - \frac{1}{p_i})$$
证明 :

​ 由算数基本定理可以得到
$$n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}…p_k^{\alpha_k}，(p_i为互不相同的素数，a_i皆为正整数)$$
​ $a \in [1,n]$ 若要与 $n$ 互质，需要满足 $gcd(a,n) = 1$。而我们需要求的 与n互质的数的个数，其实可以通过用 总共 $n$ 个数 减去 与 $n$ 不互质的数的个数 得到。因此我们只要枚举出所有 $n$ 的约数，然后 用 $n$ 减去所有大小在 $[1,n]$ 内 $n$ 的约数倍数(包括约数)的个数，最终得到的结果就是与 $n$ 互质的数的个数。

​ 设 $N_{p_1}$ 为 $[1,n]$中 $p_1$ 倍数的个数， $N_{p_2}$ 为 $[1,n]$ 中 $p_2$ 倍数的个数，.... ， $N_{p_k}$ 为 $[1,n]$ 中 $p_k$ 倍数的个数 ， $N_{p_1p_2}$ 为 $[1,n]$ 中 $p_1p_2$ 倍数的个数，$N_{p_1p_3}$ 为 $[1,n]$ 中$p_1p_3$ 倍数的个数 ，… ，$N_{p_{k-1}p_k}$ 为 $[1,n]$ 中 $p_{k-1}p_k$ 倍数的个数，… ，$N_{p_1\cdot …\cdot p_k}$ 为 $[1,n]$ 中 $p_1\cdot…\cdot p_k$ 倍数的个数，

​ 那么有

​ $N_{p_1} = \frac{n}{p_1},…,N_{p_k} = \frac{n}{p_k},…,N_{p_1\cdot…\cdotp_k} = \frac{n}{p_1\cdot …\cdot p_k}$.

​ 由容斥定理可以得到
$$\begin{array}{ll} \phi(n) = & n - N_{p_1} - N_{p_2} - … - N_{p_k} \\\ & + N_{p_1p_2} + … + N_{p_{k-1}p_k} \\\ & - \ … \\\ & + (-1)^k\cdot N_{p_1\cdot …\cdot p_k} \\\ \ \ \ \ \ \ \ = & n\prod_{i = 1}^{k}(1 - \frac{1}{p_i}) \end{array}$$
证毕。

欧拉定理 ：

若 $gcd(a,n) = 1$ ,则 $a^{\phi(n)} \equiv 1 (\mod n)$

证明 ：

​ 设 $\{r_1,r_2,r_3,…,r_{\phi(n)}\}$ 是 模 $n$ 的一个缩系，

​ 由于 $gcd(a,n) = 1,则$$\{ar_1,ar_2,ar_3,…,ar_{\phi(n)}\}$，也是 模 $n$ 的一个缩系，那么有
$$\begin{array}{ll} \prod_{i = 1}^{\phi(n)} r_i & \equiv \prod_{i = 1}^{\phi(n)} ar_i \\ & \equiv a^{\phi(n)} \cdot \prod_{i = 1}^{\phi(n)} r_i (\mod n) \end{array}$$
​ 得到 $\prod_{i = 1}^{\phi(n)} r_i (\mod n) \equiv a^{\phi(n)} \cdot \prod_{i = 1}^{\phi(n)} r_i (\mod n)$ ，

​ 因为 $gcd(r_i,n) = 1$ ,所以提出 $\prod_{i = 1}^{\phi(n)} r_i (\mod n)$ ，于是有 $1 \equiv a^{\phi(n)} (\mod n)$

​ 证毕。

可以发现，当 $n$ 为素数时且 $gcd(a,n) = 1$ ，那么有 $\phi(n) = n - 1$，根据欧拉定理可以得到 $a^{\phi(n)} \equiv a^{n - 1} \equiv 1 (\mod n)$ ，这恰好就是费马小定理的结论，所以其实可以将费马小定理看作欧拉函数的特例。

欧拉定理推论 ：

​ 若 $gcd(a,n) = 1$ ，则
$$a ^ b \equiv a ^{\phi(n)\lfloor{\frac{b}{\phi(n)}\rfloor} + b \mod \phi(n)} \equiv 1 \cdot a ^ {b \mod \phi(n)} \equiv a ^ {b \mod \phi(n)} (\mod n)$$

扩展欧拉定理

$$a^b \equiv \left\\{ \begin{array}{ll} a^b , b < \phi(n) & ,(\mod n) \\\ a^{(b \mod \phi(n))\ +\ \phi(n)} , b \ge \phi(n) & ,(\mod n) \\\ \end{array} \right.$$

当 $b \ge \phi(n)$ 时的证明 ：

​ 先分类讨论，

​ 对于 $gcd(a,n) = 1$ 时，有
$$a ^ b \equiv a ^ {b \mod \phi(n)} (\mod n)$$
​ 又因为 $a^{\phi(n)} \equiv 1 (\mod n )$ ，所以有
$$a ^ {b \mod \phi(n)} \equiv a ^ {b \mod \phi(n)} \cdot 1 \equiv a ^ {b \mod \phi(n)} \cdot a^{\phi(n)} \equiv a ^ {b \mod \phi(n) + \phi(n)} (\mod n)$$
​ 而对于$gcd(a,n) \ne 1$ ，通过算数基本定理 我们可以得到 $n = p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}$ ，我们要证明
$$a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} (\mod n)$$
​ 其实只需要证明对于每一个$p_i^{\alpha_i}$ ，都有 $a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} (\mod p_i^{\alpha_i})$ 。

​ 那么这是为什么呢 ？

​ 首先 假设已经求出
$$a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} (\mod p_i^{\alpha_i}) \\\ a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} (\mod p_j^{\alpha_j})$$
​ 因为 $gcd(p_i^{\alpha_i},p_j^{\alpha_j}) = 1$ ， 设 $t = a^{(b \mod \phi(n))\ +\ \phi(n)}$ ，则可以通过上式递推得
$$\left\\{ \begin{array}{ll} a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} \equiv t (\mod p_i^{\alpha_i}) \\\ a^b \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} \equiv t (\mod p_j^{\alpha_j}) \\\ \end{array} \right. \\\ \Rightarrow \left\\{ \begin{array}{ll} a^b - t \equiv 0 (\mod p_i^{\alpha_i}) \\\ a^b - t \equiv 0 (\mod p_j^{\alpha_j}) \\\ \end{array} \right. \\\ \Rightarrow \left\\{ \begin{array}{ll} p_i^{\alpha_i} | (a^b - t) \\ p_j^{\alpha_j} | (a^b - t) \\ \end{array} \right. \\\ \Rightarrow p_i^{\alpha_i} \cdot p_j^{\alpha_j}\ | \ (a^b - t)$$

这样就合并了两个式子，而如果合并 $k-1$ 次就可以得到 $n |(a^b - t)$ ，此时有

$$a^b - t \equiv 0 ( \mod n) \\\ a^b \equiv t \equiv a^{(b \mod \phi(n))\ +\ \phi(n)} ( \mod n) \\\ $$

​ 方向可行，那就继续讨论 $p_i^{\alpha_i}$ 的情况 ：

​ 假设 $gcd(p_i^{\alpha_i},a) = 1$

​ 则有 $a^{\phi(p_i^{\alpha_i})} \equiv 1 (\mod p_i^{\alpha_i})$ ，因为欧拉函数是积性函数，且$gcd(\frac{n}{p_i^{\alpha_i}},p_i^{a_i}) = 1$ ，所以有 $\phi(n) = \phi(\frac{n}{p_i^{\alpha_i}}) \cdot \phi(p_i^{\alpha_i}) \Rightarrow \phi(p_i^{\alpha_i})|\phi(n)$ ，所以有
$$a^{\phi(p_i^{\alpha_i})} \equiv 1 (\mod p_i^{\alpha_i})\\\ \Rightarrow (a^{\phi(p_i^{\alpha_i})})^{\phi(\frac{n}{p_i^{\alpha_i}})} \equiv 1^{\phi(\frac{n}{p_i^{\alpha_i}})} (\mod p_i^{\alpha_i}) \\\ \Rightarrow a^{{\phi(p_i^{\alpha_i})}*{\phi(\frac{n}{p_i^{\alpha_i}})}} \equiv 1 (\mod p_i^{\alpha_i}) \\\ \Rightarrow a^{\phi(n)} \equiv 1 (\mod p_i^{\alpha_i})$$
​

​ 所以有
$$\begin{array}{ll} a^b & \equiv a^{\phi(n) \cdot \lfloor\frac{b}{\phi(n)} \rfloor + b \mod \phi(n) } \\\ & \equiv 1\cdot a ^ {b \mod \phi(n)} \\\ & \equiv a ^ {b \mod \phi(n)} \cdot a^{\phi(n)} \\\ & \equiv a ^ {b \mod \phi(n)\ +\ \phi(n)} (\mod p_i^{\alpha_i}) \end{array}$$
(小插曲 ：其实本来想根据 $p_i^{\alpha_i} | n$ ，$p_i^{\alpha_i} \ge 1$，$a^{\phi(n)} \equiv 1 (\mod n)$ 推出 $a^{\phi(n)} \equiv 1 (\mod p_i^{\alpha_i})$ ，但是想起这里已经假设$gcd(a,m) \ne 1$ ，所以不能用欧拉定理推出$a^{\phi(n)} \equiv 1 (\mod n)$，那这个递推就不成立)

​ 而对于 $gcd(p_i^{\alpha_i},a) \ne 1$ 时，

​ 由于 $p_i^{\alpha_i}$ 只有$p_i$这一个质因子，所以有$a$ 一定是$p_i$的倍数。

​ 设 $a = q \cdot p_i$ ，其中 $q \in N^*$

​ 因为 $\phi(p_i^{\alpha_i}) = p_i^{\alpha_i} \times (1 - \frac{1}{p_i}) = p_i^{\alpha_i - 1} \cdot (p_i- 1)$ ，易证 $\phi(p_i^{\alpha_i}) \ge \alpha_i$ (分类讨论然后balabala)

​ 于是可以得到 $b \ge \phi(n) \ge \phi(p_i^{\alpha_i}) \ge \alpha_i$

​ 因为 $b \ge \phi(n)$ ，

​ 当 $\phi(n) \le b < \phi(n) * 2$ 时，可以得到 $b \mod \phi(n) + \phi(n) = b$ ;

​ 而当 $\phi(n) * 2 \le b$ 时，有 $b > b \mod \phi(n) + \phi(n)$ .

因此有 $b \ge b \mod \phi(n) + \phi(n) \Rightarrow b - (b \mod \phi(n) + \phi(n)) \ge 0$

​ 将 $a = qp_i$ 代入得 $a^b \equiv (qp_i)^b (\mod p_i^{\alpha_i})$

​ 所以有
$$\begin{array}{ll} a^b & \equiv (qp_i)^b \\\ & \equiv (qp)_i^{b - ((b\mod \phi(n))+ \phi(n))}\cdot (qp_i)^{b\mod \phi(n))+ \phi(n)} \\\ & \equiv a^{(b \mod \phi(n)) + \phi(n)} \\\ & \equiv (qp)_i^{b - \alpha_i}\cdot q^{\alpha_i}\cdot p_i^{\alpha_i} \\\ & \equiv 0 (\mod p_i^{\alpha_i}) \end{array}$$
​ 证毕

参考 ：

​ $Pecco$ : https://zhuanlan.zhihu.com/p/131536831

​ 董晓 : https://www.bilibili.com/video/BV1iN4y1K7ZN

LG P5091 扩展欧拉定理

#include <iostream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = long long ;
using pii = pair<int,int> ;
char CH,NUM[40];bool F;int LEN;
template <typename T>
inline void R(T &x){
    x = 0,F = 0,CH = getchar();
    while (CH < '0' || CH > '9' ){if (CH == '-') F = 1;CH = getchar();}
    while (CH >= '0'&& CH <= '9' ){x = (x << 3) + (x << 1) + (CH & 15) ; CH = getchar() ;}
    if (F) x = -x ;
}
template <typename T>
inline void W(T x) {
    if (!x){ putchar('0'); return ;} LEN = 0; 
    if (x < 0) putchar('-'), x = -x; 
    while(x) NUM[++LEN] = (x - x / 10 * 10 ) + 48, x /= 10;
    while(LEN) putchar(NUM[LEN--]); 
}
const int maxn = 1e5 + 10 ,maxm = 2e7 + 10 ;
inline int qpow(int a,int b,int p){
    int res = 1;
    a %= p;
    while (b){
        if (b & 1) res = 1ll * res * a % p ;
        b >>= 1 ;
        a = 1ll * a * a % p ;
    }
    return res ;
}
int main(){
    int a,m,phi,tmp;
    int b = 0;
    R(a),R(m);
    phi = tmp = m;
    for (int i = 2 ; i < maxn ; ++ i)
        if (tmp % i == 0){
            while (tmp % i == 0) tmp /= i ;
            phi = phi / i * (i - 1);
        }
    if (tmp ^ 1) phi = phi / tmp * (tmp - 1);
    b = 0 ;
    bool flag = 0 ;
    while ( (CH = getchar()) >= '0' && CH <= '9'){
        b = (b << 3) + ( b << 1 ) + (CH & 15);
        if (b >= phi){
            flag = 1 ;
            b %= phi ;
        }
    }
    if (flag) b += phi ;
    W(qpow(a,b,m));
    return 0;
}