剩余系

剩余类（同余类）

所有模 $n$ 的余数为 $r$ 的整数所构成的集合，称为模 $n$ 的剩余类，表示为 $C_r = nx + r$ .

例如： $n = 5, r = 3$ , 则 $C_3 = 5x + 3$ 为模 $5$ 的一个剩余类，模 $5$ 都为 $3$ .

完全剩余系（完系）

对于正整数 $n$ ，有 $n$ 个不同的模 $n$ 的剩余类，从这 $n$ 个不同的剩余类中各取一个元素， $n$ 个新元素构成一个新的集合，则称这个集合为模 $n$ 的完全剩余系。

简单来说：一个元素数量为 $n$ 的集合，如果每个元素模 $n$ 都不相同，则为完全剩余系。

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

简化剩余系（缩系）

在完全剩余系的基础上，减去与 $n$ 不互质的数，则称为简化剩余系（缩系）。其有 $\varphi(n)$ 个不同的元素。

例如： $n = 5$ , 则 $\{1, 2, 3, 4\}$ 是一个模 $5$ 的简化剩余系，其在完全剩余系上删除了 $0$ .

欧拉定理

欧拉函数

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

\varphi(n) = n \times \prod_{i-1}^{s} \frac{p_i-1}{p_i}

证明

欧拉函数是 积性函数^[1]（证明略），即对任意满足 $\gcd(a, b) = 1$ 的整数 $a, b$ ，有 $\varphi(ab) = \varphi(a)\varphi(b)$ . 特别地，当 $n$ 是奇数时 $\varphi(2n) = \varphi(n)$ ．

若 $n = p^k$ ，对于 $1 \sim p^k$ 的所有整数中 , 除 $p^{k-1}$ 个 $p$ 的倍数外其它数都与 $p^k$ 互质
故

\varphi(p^k) = p^k - p^{k-1} = p^{k-1} \times (p - 1)

由唯一分解定理^[2]，又称算术基本定理：每个大于 $1$ 的自然数，要么本身就是素数，要么可以写为 $2$ 个或以上的素数的积，而且这些素因子按大小排列之后，写法仅有一种方式。

数学表示为：

n = p_1^{k_1}p_2^{k_2}...p_s^{k_s} = \prod_{i=1}^{s} p_i^{k_i}

由唯一分解定理与欧拉函数的积性：

\begin{aligned} \varphi\left(n\right) &= \varphi\left(p_1^{k_1}p_2^{k_2}\dots p_s^{k_s}\right) = \varphi\left(p_1^{k_1}\right) \varphi\left(p_2^{k_2}\right)\dots \varphi\left(p_s^{k_s}\right) \\ &= \prod_{i=1}^{s} \varphi\left(p_i^{k_i}\right) = \prod_{i=1}^{s}\left(p_i^{k_i - 1}(p_i - 1)\right) = \prod_{i=1}^{s}\left(p_i^{k_i}(1 - \frac{1}{p_i})\right) \\ &= \prod_{i=1}^{s}\left(p_i^{k_i}(\frac{p_i - 1}{p_i})\right) = n \prod_{i=1}^s \left(\frac{p_i-1}{p_i}\right) \end{aligned}

证毕。

C++ 代码求欧拉函数，使用试除法，时间复杂度 $O(\sqrt{n})$

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

欧拉定理

若 $gcd(a, m) = 1$ ，则

a^{\varphi(m)} \equiv 1 \pmod{m}

例如： $a = 3, m = 4$ , 则 $3^{\varphi(4)} \equiv 3^2 \equiv 1 \pmod{4}$

证明

设 $\{r_1, r_2, \dotsb, r_{\varphi(m)}\}$ 是一个模 $m$ 的缩系，则 $\{ar_1, ar_2, \dotsb, ar_{\varphi(m)}\}$ 也是一个模 $m$ 的缩系，因为 $gcd(a, m) = 1$ .

所以， $\prod_{i=1}^{\varphi(m)} r_i \equiv \prod_{i=1}^{\varphi(m)} ar_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)} r_i \pmod{m}$ ，约去 $\prod_{i=1}^{\varphi(m)} r_i$ ，
得： $a^{\varphi(m)} \equiv 1 \pmod{m}$ ，证毕.

费马小定理

当 $m$ 为质数时，由于 $\varphi(m) = m-1$ ，带入欧拉定理，可得费马小定理 ^[3]

a^{m-1} \equiv 1 \pmod{m}

可见，费马小定理是欧拉定理在 $m$ 为质数时的特殊情况。或者说，欧拉定理是费马小定理的更一般形式。

扩展欧拉定理

\begin{aligned} a^b \equiv \begin{cases} a^b, & b < \varphi(m), & \pmod{m} \\ a^{b\mod \varphi(m) + \varphi(m)}, & b \ge \varphi(m), & \pmod{m} \end{cases} \end{aligned}

当 $b$ 小的时候，不用降幂，直接跑快速幂。
当 $b$ 是大数时，先降幂，再跑快速幂。

扩展欧拉定理降幂

int depow(int phi, string s) {
    int b = 0, flag = 0;
    for(auto i: s) {
        b = b * 10 + (i - '0');
        if(b >= phi) {
            flag = 1;
            b %= phi;
        }
    }
    if(flag) b += phi;
    return b;
}

int qpow(ll a, string s, ll mod) {
    ll res = 1;
    int b = depow(get_phi(mod), s);
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}