同余

• • • 定义

    • 性质

    • 最大公约数

      • 欧几里得算法
      • 裴蜀定理
      • 扩展欧几里得算法

    • 费马小定理

    • 欧拉定理

    • 威尔逊定理

    • 中国剩余定理

    • 乘法逆元

定义

同余类

对于 $\mathrm{\forall }a\in [0,m-1]\backslash forall\; a\backslash in\; [0,m-1]$，集合 $\{a+km\}(k\in \mathbb{Z})\backslash lbrace\; a+km\backslash rbrace(k\backslash in\backslash mathbb\; Z)$ 的所有数模 $mm$ 同余，余数都是 $aa$ 。该集合称为一个模 $mm$ 的同余类，简记为 $\bar{a}\backslash bar\; a$ 。

剩余系 模 $mm$ 的同余类一共有 $mm$ 个，分别为 $\bar{1},\bar{2},\cdots ,\stackrel{\mathrm{—}\mathrm{—}}{}\backslash bar\; 1,\backslash bar\; 2,\backslash cdots,\backslash overset\{——\}\{m-1\}$ 。他们构成 $mm$ 的完全剩余系。

$11$~$mm$ 中与 $mm$ 互质的数代表的同余类共有 $\phi (m)\backslash varphi(m)$ 个，它们构成 $mm$ 的简化剩余系。

性质

最大公约数

欧几里得算法

裴蜀定理

对任意整数 $a,b,x,y,ax+bya,b,x,y,ax+by$ 一定是 $\gcd (a,b)\backslash gcd(a,b)$的倍数

$\mathrm{特}\mathrm{别}\mathrm{的}\mathrm{\exists }x,y\in \mathbb{Z},\mathrm{满}\mathrm{足}ax+by=\gcd (a,b)\backslash small\; 特别的\backslash exist\; x,y\backslash in\backslash mathbb\; Z,\backslash small满足\backslash quad\; ax+by=\backslash gcd(a,b)$

扩展欧几里得算法

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y); //也可以写成
    ll t=x;             // ll d=exgcd(b,a%b,y,x);
    x=y;                 //y-=(a/b)*x;
    y=t-y*(a/b);
    return d;
}

该算法解得 $x_0,y_{0}x\_0,y\_0$ 为一组特解，$dd$ 为 $\gcd (a,b)\backslash gcd(a,b)$ 对于不定方程 $ax+by=cax+by=c$ 的通解可以表示为:

令 $m_1=\frac{b}{d},m_2=\frac{a}{d}m\_1=\backslash frac\{b\}\{d\}\backslash \; ,m\_2=\backslash frac\{a\}\{d\}$ ，则有 $x=x_{min}+k{m}_1,y=y_{min}+k{m}_{2}x=x\_\{min\}+km\_1,\backslash \; y=y\_\{min\}+km\_2$

故 $x_{min}=x(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1),y_{min}=y(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)x\_\{min\}=x\backslash pmod\; \{m\_1\},\; y\_\{min\}=y\backslash pmod\{m\_2\}$

费马小定理

若 $pp$ 是素数，则对于任意整数 $aa$ ，有 $a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)a^p\backslash equiv\; a\backslash pmod\; p$

欧拉定理

若正整数 $a,na,n$ 互质，则 $a^{\phi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)a^\{\backslash varphi(n)\}\backslash equiv\; 1\backslash pmod\; n$, 其中 $\phi (n)\backslash varphi(n)$ 为欧拉函数

推论：若正整数 $a,na,n$ 互质，则对于任意正整数 $bb$，有 $a^b\equiv a^{b\mathrm{m}\mathrm{o}\mathrm{d}\phi (n)}(\mathrm{m}\mathrm{o}\mathrm{d}n)a^b\backslash equiv\; a^\{b\; \backslash bmod\; \backslash varphi\; (n)\}\backslash pmod\; n$

特别地，当 $a,na,n$ 不一定互质且 $b\ge \phi (n)b\backslash geq\backslash varphi(n)$ 时，有$a^b\equiv a^{b\mathrm{m}\mathrm{o}\mathrm{d}\phi (n)+\phi (n)}(\mathrm{m}\mathrm{o}\mathrm{d}n)a^b\backslash equiv\; a^\{b\; \backslash bmod\; \backslash varphi\; (n)+\backslash varphi(n)\}\backslash pmod\; n$

即扩展欧拉定理(欧拉降幂公式)有：

威尔逊定理

任意一个大于1的数是素数的充要条件为：

中国剩余定理

设 $m_1,m_2,\cdots ,m_{n}m\_1,m\_2,\backslash cdots,m\_n$ 是两两互素的整数，$m={\prod }_{i=1}^n{m}_i,M_i=\frac{m}{mi},M_i^{-1}m=\backslash prod\_\{i=1\}^n\; m\_i,\backslash \; M\_i=\backslash frac\{m\}\{mi\},\backslash \; M\_i^\{-1\}$ 是 $M_{i}M\_i$ 在模 $m_{i}m\_i$ 下的逆元。对于任意的 $nn$ 个整数 $a_1,a_2,\cdots ,a_{n}a\_1,a\_2,\backslash cdots,a\_n$ ，方程组

有整数解，解为 $x={\sum }_{i=1}^n{a}_i{M}_i{M}_i^{-1}x=\backslash sum\_\{i=1\}^n\; a\_i\; M\_i\; M\_i^\{-1\}$

原理：其中的第 $ii$ 项，由于 $M_i^{-1}M\_i^\{-1\}$ 是 $M_{i}M\_i$ 在模 $m_{i}m\_i$ 下的逆元,故在令该项对 $m_{i}m\_i$ 取模时得到 $a_{i}a\_i$，而对于其他所有项，由于 $M_{i}M\_i$ 为其他所有模数的公倍数，故为 $00$

ll CRT(vector<Pll>&v){//v[i].ft=mi,v[i].sd=ai
    ll M = 1, ans = 0,m;
    for(auto&it:v)M *= it.ft;
    for(auto&it:v){
        m = M / it.ft;
        ans = (ans + it.sd * m * inv(m, it.ft)) % M;
    }
    return ans;
}

当问题中的模数 $m_{i}m\_i$ 不再两两互素时，可多次扩展欧几里得进行求解 扩展中国剩余定理

ll exCRT(vector<Pll>&v){//v[i].ft=mi,v[i].sd=ai
    ll a, b, c, x, y, M = v[0].ft, ans = v[0].sd;
    for(int i=1;i<(int)v.size();i++)
    {
        a=M,b=v[i].ft,c=(v[i].sd-ans%b+b)%b;
        ll gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1;
        x=quick_mul(x,c/gcd,bg);
        ans+=x*M;
        M*=bg;
       ans=(ans%M+M)%M;
    }
    return ans;
}

乘法逆元

定义 若整数 $a,pa,p$ 互素 $a\ast x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a*x\backslash equiv1\backslash pmod\; p$，则称 $xx$ 为 $aa$ 的模 $mm$ 乘法逆元

• 若 $pp$ 为素数，则可以利用费马小定理有 $a\ast a^{p-2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a*a^\{p-2\}\backslash equiv\; 1\backslash pmod\; p$, 故只需要用快速幂求解 $a^{p-2}a^\{p-2\}$

• 若 $pp$ 不一定是素数，那么可以通过求解同余方程 $a\ast x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a*x\backslash equiv\; 1\backslash pmod\; p$ ,利用扩展欧几里得算法即可

线性逆元递推公式

若要求对 $11$~$nn$ 个数求模 $pp$ 的逆元，可推导关系得到递推公式线性求解

首先 $1^{-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)1^\{-1\}\backslash equiv1\backslash pmod\; p$

令

有 $k\ast i+r\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)k*i+r\backslash equiv0\backslash pmod\; p$，则 $i\equiv -r\ast k^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)i\backslash equiv-r*k^\{-1\}\; \backslash pmod\; p$，

故 $i^{-1}\equiv -r^{-1}\ast k(\mathrm{m}\mathrm{o}\mathrm{d}p)i^\{-1\}\backslash equiv-r^\{-1\}*k\backslash pmod\; p$

$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \ast (p\mathrm{m}\mathrm{o}\mathrm{d}i{)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)\backslash quad\; i^\{-1\}\backslash equiv-\backslash lfloor\backslash frac\{p\}\{i\}\backslash rfloor*(p\backslash bmod\; i)^\{-1\}\backslash pmod\; p$

$i^{-1}\equiv (p-\lfloor \frac{p}{i}\rfloor )\ast (p\mathrm{m}\mathrm{o}\mathrm{d}i{)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)\backslash quad\; i^\{-1\}\backslash equiv(p-\backslash lfloor\backslash frac\{p\}\{i\}\backslash rfloor)*(p\backslash bmod\; i)^\{-1\}\backslash pmod\; p$