同余式

如果两个整数 $a,b$ 对 $m$ 取余的余数相同，则 $a,b$ 模 $m$ 同余，记作 $a\equiv b(mod\ m)$

乘法逆元

若两个整数 $a,b$ 互质，且满足同余方程 $a\cdot x\equiv 1(mod\ b)$ ，则定义 $x$ 为 $a\ mod\ b$ 的乘法逆元，记作 $a^{-1}$

例如：$4x\equiv1(mod\ 5)$ 可以解得 $x=4,9,14\cdots(4+5\lambda)$ ，一般取小于 $b$ 的乘法逆元方程的特解

费马小定理

若 $p$ 为质数，且 $a,p$ 互质，则满足同余式 $a^{p-1}\equiv1(mod\ p)$ ，例如：$2^{3-1}\equiv1(mod\ 3)$

  • 证明如下：

​ 首先存在一个质数为 $p$ ，根据欧拉函数的性质，与它互质的数即为 $[1,p-1]$ 其中的元素组成的序列，记为：

$$ A=\{1,2,3,\cdots,p-1\} $$

​ 需要证明以下同余式成立：

$$ \prod_{i=1}^{p-1} (a\times A_i)\equiv \prod_{i=1}^{p-1}A_i(mod\ p)\impliedby a^{p-1}\times \prod_{i=1}^{p-1} A_i\equiv \prod_{i=1}^{p-1}A_i(mod \ p) $$

​ 即说明每一个 $a\times A_i(mod \ p)$ 的余数都是互不相同的，推导过程有：

​ 假设 $a\times A_i(mod\ p),a\times A_j(mod\ p)$ 的余数相同且为 $r$ ，则满足 $a\times A_i=xp+r,a\times A_j=yp+r$

$$ \implies a(A_i-A_j)=(x-y)p $$

​ 若 $r$ 存在，则 $a(A_i-A_j)$ 一定不为 $p$ 的倍数，当 $A_i\ne A_j $ 时 $(x-y)p$ 一定为 $p$ 的倍数，则等式不成立

​ 反之就说明了每一个 $a\times A_i(mod \ p)$ 的余数都是互不相同

又因为 $a\times A_i(mod\ p)<p$ 恒成立，所以与 $A_i(mod \ p)$ 的余数集合必然相同

则：

$$ a^{p-1}\times \prod_{i=1}^{p-1} A_i\equiv \prod_{i=1}^{p-1}A_i(mod \ p) $$

两侧消去 $\prod_{i=1}^{p-1}A_i$ 后得到方程

$$ a^{p-1}\equiv 1 (mod\ p) $$

例如：$p=5,A=\{ 1,2,3,4\},a=2$，那么 $a\times A=\{2,4,6,8\},a\times A\ \%\ p=\{2,4,1,3\}=A\ \%\ p=\{1,2,3,4\}$

快速幂加速计算乘法逆元

给定两个整数 $a,p$ ，$p$ 为质数，求 $a$ 模 $p$ 的乘法逆元

根据费马小定理有：$a^{p-1}\equiv1(mod \ p)\iff a\times a^{p-2}\equiv1(mod\ p)$，则 $a^{p-2}$ 即为 $a$ 模 $p$ 的乘法逆元

cin>>a>>p;
cout<<quickpow(a,p-2,p);//调用快速幂计算a^(p-2)，过程中仍然需要对p取余

long long quickpow(long long a,long long b,long long p){
    long long res=1;
    while (b){
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}