浅谈同余1(常用定理和乘法逆元)

点个赞吧，球球了~

下一篇:$浅谈同余2(扩展欧几里得，中国剩余定理，BSGS)$

https://www.acwing.com/file_system/file/content/whole/index/content/7882318/

$\LaTeX$太多了，分成几个部分
0x00 总写(瞎说)

同余是数学中非常重要的东西，这里会写出同余的基本运用

若$a \bmod m = b \bmod m$则称$a, b$模$m$同余，记做$a \equiv b \pmod m$

0x10 欧拉定理和推论，费马小定理
欧拉定理:
若正整数$a, n$互质，则$a^{\varphi {(n)}} \equiv 1 \pmod n$

不会证明

费马小定理:
若$p$是质数，则对于任意正整数$a$,有$a ^ p \equiv a \pmod p$

欧拉定理左右两边乘上$p$就是费马小定理

欧拉定理的推论
若正整数$a, n$互质，则对于任意正整数$b$,有$a^b \equiv a ^ {b \bmod {\varphi ( n )}} \pmod n$

证明:
设$b = q \times \varphi ( n ) + r$ , 其中$0\le r \lt \varphi ( n )$, 即$r = b \bmod \varphi ( n )$
于是:$a^b \equiv a^{q \times \varphi ( n ) + r} \equiv ( a ^ {{\varphi ( n) } ^ q} ) \times {a ^ r} \equiv {1 ^ q \times {a^r}} \equiv a ^ r \equiv a ^ {b \bmod \varphi ( n )} \pmod n$
证毕

所以乘方级的取模为:$a \bmod n ^ {b \bmod \varphi(n)}$

0x10 乘法逆元
若正整数$b, m$互质，并且$b|a$, 则存在一个整数$x$, 使得$a \div b \equiv a \times x \pmod m$
称$x$为$b$的模$m$乘法逆元，记做$b^{-1\} \pmod m $
因为$a \div b \equiv a \times b ^ {-1} \equiv a \div b \times b \times b ^ {-1} \pmod m$,所以$b\times b^{-1} \pmod m$

如果$m$是质数并且$b<m$,根据费马小定理，$b^{m - 1} \equiv 1 \pmod m$,即$b\times b^{p-2} \equiv 1 \pmod m$
因此，当模数$m$为质数时，$b^{m - 2}$即为$b$的乘法逆元,可以用快速幂来解决

$Code$:

int gcd(int a, int b) {
    return a % b == 0 ? b : gcd(b, a % b);
}

int fast_power(int a, int b, int p) {
    if (gcd(a, p) > 1) return -1;
    
    a %= p;
    int res = 1;
    
    while (b) {
        if (b & 1) res = res * a % p;
        
        b >>= 1;
        a = a * a % p;
    }
    
    return res;
}

t = fast_power(a, p - 2, p);

但是当$m$不是质数且$b, m$互质时，费马小定理不再适用，要用扩展欧几里得算法计算同余方程
$b \times x \equiv 1 \pmod m$

线性求$1 \sim n$乘法逆元

$inv(i) = -\lfloor \frac{p}{i} \rfloor \times inv(p \bmod i) \bmod p$

证明有空补
只能用这种方法，别的算法都比这些要求一串要慢。

#### $Code$:

res[1] = 1;
for (int i = 2; i <= n; i ++ ) {
    res[i] = (long long)(p - p / i) * res[p % i] % p;
    printf("%lld\n", res[i]);
}