同余

本章主要记录有关同余、费马小定理、欧拉定理、扩展欧几里得算法、裴蜀定理、乘法逆元、威尔逊定理、线性同余方程、中国剩余定理、扩展中国剩余定理、BSGS以及扩展BSGS的学习笔记。

由于内容复杂且关联较少，建议配备 ctrl+F 进行快乐食用。

正在继更ing

一、基础知识

这个板块着重介绍同余的基本知识，虽然多为数学竞赛内容，但也对信息学竞赛有不少帮助，定理和性质为拓展内容。

本部分参考《初等数论》进行撰写。

1.1$\quad$基本定义、定理与性质

定义1（同余）$\quad$ 设 $m\neq0$。若 $m\mid a-b$，即 $a-b=km$，则称 $m$ 为模，$a$ 同于与 $b$ 模 $m$ 以及 $b$ 是 $a$ 对模 $m$ 的剩余，记作

$a\equiv b\pmod{m} \tag{1}$

不然，则称 $a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余，记作 $a\not\equiv b\pmod{m}$

式 $(1)$ 称为模 $m$ 的同余式，或简称同余式。

由于 $m\mid a-b$ 等价于 $-m\mid a-b$ ，所以同余式 $(1)$ 等价于

$a\equiv b\pmod{(-m)}$

定理1$\quad$ $a$ 同余于 $b$ 模 $m$ 的充要条件是 $a$ 和 $b$ 被 $m$ 除后所得的最小非负余数相等，即若

$\begin{aligned} a=q_1m+r_1&,0\leq r_1<m\\ b=q_2m+r_2&,0\leq r_2<m, \end{aligned}$

则 $r_1=r_2$。

性质Ⅰ$\quad$ 同余是一种等价关系，即有

$\begin{aligned} a\equiv a\pmod{m}\\ a\equiv b\pmod{m}\iff b\equiv a\pmod{m}\\ a\equiv b\pmod{m}\;,\;b\equiv c\pmod{m}\Rightarrow a\equiv c\pmod{m} \end{aligned}$

性质Ⅱ$\quad$ 同余式可以相加，即若有

$a\equiv b\pmod{m}\;,\;c\equiv d\pmod{m}\tag{2}$

则有

$a+c\equiv b+d\pmod m$

性质Ⅲ$\quad$ 同余式可以相乘，即若式 $(2)$ 成立，则

$ac\equiv bd\pmod m$

性质Ⅳ$\quad$ 设 $f(x)=a_nx^n+\cdots+a_0$，$g(x)=b_nx^n+\cdots+b_0$ 是两个整系数多项式，满足

$a_j\equiv b_j\pmod m\;,\;0\leq j<n\tag{3}$

那么，若 $a\equiv b\pmod m$，则

$f(a)\equiv g(b)\pmod m$

特别地，对所有整数 $x$ 有

$f(x)\equiv g(x)\pmod m\tag{4}$

定义2$\quad$ 设 $f(x)=a_nx^n+\cdots+a_0$ 和 $g(x)=b_nx^n+\cdots+b_0$ 是两个整系数多项式。当满足条件 $(3)$ 时，称多项式 $f(x)$ 同余于多项式 $g(x)$ 模 $m$，记作

$f(x)\equiv g(x)\pmod m$

当满足 $f(x)\equiv g(x)\pmod m$ 时，称多项式 $f(x)$ 等价于多项式 $g(x)$ 模 $m$，式 $(4)$称为模 $m$ 的恒等同余式

性质Ⅴ$\quad$ 设 $d\geq1$，$d\mid m$，那么，若式 $(1)$ 成立，则 $a\equiv b\pmod d$

性质Ⅵ$\quad$ 设 $d\not=0$，那么 $a\equiv b\pmod m$ 等价于 $da\equiv db\pmod{\left\vert d\right\vert m}$

性质Ⅶ$\quad$ 同余式 $ca\equiv cb\pmod m$ 等价于 $a\equiv b\pmod{\frac m{\gcd(c,m)}}$

特别地，当 $\gcd(c,m)=1$ 时，上述同余式等价于 $a\equiv b\pmod m$

性质Ⅷ$\qquad$ 若 $m\geq1$，$\gcd(a,m)=1$，则存在 $c$ 使得

$ca\equiv1\pmod m\tag{5}$

定义3$\quad$ 若存在 $m\geq1$，$\gcd(a,m)=1$，且满足式 $(5)$，我们把 $c$ 称为 $a$ 对模 $m$ 的逆，记作 $a^{-1}\pmod m$ 或 $a^{-1}$

性质Ⅸ$\quad$ 同余式组

$a\equiv b\pmod{m_j}\;,\;j=1,2,\cdots,k$

同时成立的充要条件是

$a\equiv b\pmod{[m_1,m_2,\cdots,m_k]}$

1.2$\quad$同余类与剩余系

定义4（同余类和剩余系）$\quad$ 对于 $\forall a\in [0,m-1]$，集合 $\{a+km\}(k\in\mathbb{Z})$ 的所有数模 $m$ 同余，余数都是 $a$，该集合成为模 $m$ 的同余类，简记为 $\overline{a}$。

模 $m$ 的同余类一共有 $m$ 个，分别为 $\overline{0},\overline{1},\overline{2},\cdots,\overline{m-1}$。它们构成 $m$ 的完全剩余系。

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

二、费马小定理和欧拉定理

前置芝士：欧拉函数。

利用同余基本知识和欧拉函数，即可证明费马小定理和欧拉定理。

2.1$\quad$费马小定理

定理2（费马小定理）$\quad$ 若 $p$ 是质数，则对于任意整数 $a$，有

$a^p\equiv a\pmod p$

2.2$\quad$欧拉定理

定理3（欧拉定理）$\quad$ 若正整数 $a,n$ 互质，则

$a^{\phi(n)}\equiv1\pmod n$

其中，$\phi(n)$ 为欧拉函数。

特别地，当 $p$ 是质数时，$\phi(p)=p-1$，并且只有 $p$ 的倍数与 $p$ 不互质，所以，只要 $a$ 不是 $p$ 的倍数，就有

$a^{p-1}\equiv1\pmod p$

两边同乘 $a$ 就是费马小定理。

证$\quad$ 设 $n$ 的简化剩余系为 $\{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\phi(n)}}\}$。对于 $\forall a_i,a_j$，若 $a\times a_i\equiv a\times a_j\pmod n$，则 $a\times(a_i-a_j)\equiv 0$。因为 $a,n$ 互质，所以 $a_i-a_j\equiv 0$，即 $a_i\equiv a_j$。故当 $a_i\not=a_j$ 时，$aa_1,aa_j$ 也代表不同的同余类。

又因为简化剩余系关于模 $n$ 乘法封闭，故 $\overline{aa_1}$ 也在简化剩余系集合中。因此，集合 $\{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\phi(n)}}\}$ 与集合 $\{\overline{aa_1},\overline{aa_2},\cdots,\overline{aa_{\phi(n)}}\}$ 都能表示 $n$ 的简化剩余系，故有

$a^{\phi(n)}\prod\limits_{i=1}^{\phi(n)} a_i\equiv\prod\limits_{i=1}^{\phi(n)}aa_i\equiv \prod\limits_{i=1}^{\phi(n)}a_i\pmod n$

两边同时除以 $\prod\limits_{i=1}^{\phi(n)}a_i$ 可得

$a^{\phi(n)}\equiv1\pmod n$

当 $p$ 为质数时，$\phi(p)=p-1$，并且只有 $p$ 的倍数与 $p$ 不互质。所以，只要 $a$ 不是 $p$ 的倍数，$a^{p-1}\equiv1\pmod p$ 显然成立。两边同乘 $a$ 即费马小定理。

证毕。

2.3$\quad$欧拉定理的推论

推论1（欧拉定理推论）$\quad$ 若正整数 $a,n$ 互质，则对于任意正整数 $b$，有

$a^b\equiv a^{b\mod{\phi(n)}}\pmod n$

证$\quad$ 设 $b=q\times\phi(n)+r$，其中 $0\leq r<\phi(n)$，即 $r=b\mod{\phi(n)}$。利用欧拉定理有

$a^b\equiv a^{q\times\phi(n)+r}\equiv(a^{\phi(n)})^q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\mod{\phi(n)}+\phi(n)}\pmod n$

证毕。

特别地，当 $a,n$ 不一定互质且 $b>\phi(n)$ 时，有

$a^b\equiv a^{b\mod{\phi(n)+\phi(n)}}\pmod n$

2.4$\quad$光速幂

给定 $a$ 和 $c$，每次询问给出 $b$，求 $a^b\bmod c$。

我们可以先运用 $a^b\bmod a^{b\bmod \phi(n)+\phi(n)}\pmod c$，将 $b$ 缩小到 $2\phi(c)(<2c)$ 的范围，有

$a^b=(a^{\sqrt c})^{\left\lfloor\frac{b}{\sqrt c}\right\rfloor}\times a^{b\bmod \sqrt c}$

其中，$\frac{b}{\sqrt c}<2\sqrt c$，$b\bmod \sqrt c<\sqrt c$

我们预处理 $(a^{\sqrt c})^i$ 和 $a^j$ 即可 $O(\sqrt c)$ 预处理，$O(1)$ 回答询问。

三、扩展欧几里得算法

前置芝士：欧几里得算法。

本部分着重介绍扩展欧几里得算法、裴蜀定理和乘法逆元相关知识。

3.1$\quad$裴蜀定理

定理4（裴蜀定理） $\quad$ $\forall a,b\in\mathbb{Z}$，一定存在一组 $x,y\in\mathbb{Z}$，满足

$ax+by=\gcd(a,b)$

证$\qquad$ 在欧几里得算法的最后一步，即 $b=0$ 时，我们一定会得出一组整数 $\begin{cases}x=1\\b=0\end{cases}$，使得 $a\times1+0\times0=\gcd(a,0)$。

由欧几里得算法得 $\gcd(a,b)=\gcd(b,a\bmod b)$。假设存在一组整数 $x,y$，满足 $bx+(a\bmod b)y=\gcd(b,a\bmod b)$。

因为 $bx+(a\bmod b)y$

$\begin{aligned}
\;\;&=bx+(a-b\left\lfloor\dfrac{a}{b}\right\rfloor)y \\
&=bx+ay-b\left\lfloor\dfrac{a}{b}\right\rfloor y \\
&=ay+b(x-b\left\lfloor\dfrac{a}{b}\right\rfloor)
\end{aligned}$

所以，令 $x’=y$，$y’=x-\left\lfloor\dfrac{a}{b}\right\rfloor y$，就得到了 $ax’+by’=\gcd(a,b)$。

对以上过程应用数学归纳法，可知裴蜀定理一定成立。

证毕。

3.2$\quad$扩展欧几里得算法

上面证明的过程中，我们通过 $ax+(a\bmod b)y=\gcd(a,b)$ 推出了 $ax’+by’=\gcd(a,b)$。按照欧几里得算法的思路，并给出整数 $x$ 和整数 $y$ 的计算方法成为扩展欧几里得算法。

下面给出扩展欧几里得算法过程：

给定 $a$ 和 $b$，递归 $\operatorname{exgcd}(a,b)$；
是否 $b=0$。如果是，返回 $\begin{cases}x=1\\y=0\end{cases}$；如果不是，递归 $\operatorname{exgcd}(b,a\bmod b)$，并重复进行1和2操作，直至条件成立；
每次递归结束后，计算 $\begin{cases}x’=y\\y’=x-\left\lfloor\dfrac{a}{b}\right\rfloor y\end{cases}$。

也可以在算法过程中顺便记录 $\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 temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}

ll a,b,x,y;
cin>>a>>b;
ll d=exgcd(a,b,x,y);

上述程序求出方程 $ax+by=\gcd(a,b)$ 的一组特解 $x_0,y_0$，并返回 $\gcd(a,b)$，即 $d$。

对于方程 $ax+by=c$，当且仅当 $d\mid c$ 时有解。我们可以求出 $ax+by=d$ 的一组特解 $x_0,y_0$，然后令 $x_0,y_0$ 同时乘上 $\dfrac{c}{d}$，就得到了方程 $ax+b=c$ 的特解

$\dfrac{c}{d}x_0\;,\;\dfrac{c}{d}y_0$

对于方程 $ax+by=d$，我们将其特解表示为 $x_0,y_0$，有 $a(x+m)+b(y-n)=ax+by+am-bn=d$。因为 $ax+by=d$，可以推出 $am-bn=0\Rightarrow am=bn\Rightarrow \dfrac{a}{b}=\dfrac{n}{m}$。由于 $\gcd(a,b)=d$，故 $m$ 和 $n$ 最小只能取 $\dfrac{b}{d}$ 和 $\dfrac{a}{d}$，能保证 $m$ 和 $n$ 为整数。所以，方程 $ax+by=d$ 的通解为

$\begin{cases}x_1=x_0+\dfrac{b}{d}k\\ \\y_1=y_0-\dfrac{a}{d}k\end{cases}(k\in\mathbb{Z})$

3.3$\quad$线性同余方程

给定整数 $a,b,m$，求一个整数 $x$ 满足 $ax\equiv b\pmod m$，或者给出无解。

定义5（线性同余方程）$\qquad$ 在整数域内，关于 $x$ 的同余方程 $ax\equiv b\pmod m$ 称为一次同余方程，也称线性同余方程。

$ax\equiv b\pmod m$ 等价于 $m\mid (ax-b)$，一定存在一个整数 $k$，有 $ax+mk=b$。我们可以利用扩展欧几里得算法对其进行计算。

3.4$\quad$乘法逆元

定义6（乘法逆元）$\qquad$ 若整数 $b,m$ 互质，并且 $b\mid a$，则存在一个整数 $x$，使得 $\dfrac{a}{b}\equiv ax\pmod m$。称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}\pmod m$。

因为 $\dfrac{a}{b}\equiv a\times b^{-1}\equiv\dfrac{a}{b}\times b\times b^{-1}\pmod m$，所以 $b\times b^{-1}\equiv1\pmod m$。

下面是一些求解乘法逆元的方法。

方法一：解线性同余方程求解乘法逆元

如果只保证 $b,m$ 互质，那么乘法逆元可以通过求解同余方程 $bx\equiv1\pmod m$ 得到。算法过程已在上文中提及，不再赘述。

方法二：快速幂求解乘法逆元

本方法使用有前提条件。

如果 $m$ 是质数，并用 $p$ 表示 $m$，并且 $b<p$，根据费马小定理， $b^{p-1}\equiv1\pmod p$，即

$b\times b^{p-2}\equiv1\pmod p$

因此，当模数 $p$ 为质数时，$b^{p-2}$ 即为 $b$ 的乘法逆元。

我们直接对 $b^{p-2}$ 进行快速幂计算即可得到答案。

方法三：线性求解乘法逆元

给定 $n,p$，求出 $1,2,\cdots,n$ 在模 $p$ 意义下的乘法逆元。

显而易见，$1^{-1}\equiv1\pmod p$。

假设当我们递归到 $i(i>1)$ 时已经把前 $i-1$ 个的乘法逆元算出来了，我们设 $j=p\bmod i$，$k=\left\lfloor\dfrac{p}{i}\right\rfloor$，有 $p=ki+j$，即

$ki+j\equiv 0\pmod p$

两边同乘 $i^{-1}j^{-1}$ 得

$\begin{aligned} kj^{-1}+i^{-1}&\equiv0\pmod p\\ i^{-1}&\equiv kj^{-1}\pmod p\\ i^{-1}&\equiv \left\lfloor\dfrac{p}{i}\right\rfloor(p\bmod i)^{-1}\pmod p \end{aligned}$

void work(){
    scanf("%d%d",&n,&p);
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(long long)(p - p / i) * inv[p % i] % p;
    }
    for(int i=1;i<=n;i++) printf("%d\n",inv[i]);
}

方法四：线性求解任意 $n$ 个数的逆元

任意给定 $n$ 个数 $a_1,a_2,\cdots,a_n$，求它们在模 $p$ 意义下的乘法逆元，其中，$p$ 为质数。

我们设

$s_i=\prod_{i=1}^ia_i$

通过快速幂或者扩展欧几里得算法求得 $s_i$ 的乘法逆元记为 $sv_i$，即

$sv_i=s_i^{-1}\pmod p$

我们将 $sv_1$ 乘上 $a_i$，会与 $a_i^{-1}\pmod p$ 相消，得

$a_i\times sv_1=sv_{i-1}$

我们就能递推线性求解乘法逆元。

ll n,p,k,a[MAXN],s[MAXN],t[MAXN];
ll ans=0,temp;
int qpow(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1){
        if(b&1) ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
    }
    return ans;
}
void work(){
    s[0]=1;
    t[n+1]=1;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]*a[i]%p;
    }
    t[n+1]=qpow(s[n],p-2,p);
    for(int i=n;i;i--){
        t[i]=t[i+1]*a[i]%p;
    }
    temp=k;
    for(int i=1;i<=n;i++){
        ans=(ans+(t[i+1]*s[i-1]%p)*temp)%p;
        temp=temp*k%p;
    }
    printf("%lld",ans);
}

3.5$\quad$威尔逊定理

定理5（威尔逊定理）$\quad$ 对于任意素数 $p$，有 $(p-1)!\equiv-1\pmod p$。

证$\quad$ 我们知道，$x^2\equiv1\pmod p$ 的解只有 $x\equiv\pm1\pmod p$，所以 $2\sim p-2$ 和逆元两两对应。剩下 $1\times (p-1)\equiv -1\pmod p$。

证毕。

四、中国剩余定理

前置芝士：乘法逆元。

本节主要介绍有关中国剩余定理和扩展中国剩余定理，是解决线性同余方程组问题的重要方法。

4.1$\quad$中国剩余定理

定理6（中国剩余定理，孙子定理）$\quad$ 设 $m_1,m_2,\cdots,m_n$ 是两两互质的整数，$m=\prod_{i=1}^n{m_i}$，$M_i=m/m_i$，$t_i$ 是线性同余方程 $M_it_i\equiv1\pmod{m_i}$ 的一个解。对于任意的 $n$个整数 $a_1,a_2,\cdots,a_n$，方程组

$\begin{cases}x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \cdots\\ x\equiv a_n\pmod{m_n}\end{cases}$

有整数解，解为 $x=\sum_{i=1}^na_iM_it_i$。

证$\quad$ 因为 $M_i=m/m_i$ 是除 $m_i$ 之外所有模数的倍数，所以 $\forall k\not=i\;,\;a_iM_it_i\equiv0\pmod{m_k}$。又因为 $a_iM_it_i\equiv a_i\pmod{m_i}$，所以代入 $x=\sum_{i=1}^na_iM_it_i$，原方程组成立。

证毕。

按照中国剩余定理，我们可以计算线性同余方程组的一个通解（最小解）。另外，我们可以用扩展欧几里得算法求解逆元。

int n,a[MAXN],m[MAXN];
ll M,ans,summ[MAXN];
ll qpow(int a,int b,int mod){
    ll w=1;
    for(;b;b>>=1){
        if(b&1) w=w*a%mod;
        a=a*a%mod;
    }
    return w;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
void work(){
    M=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m[i]>>a[i];
        M*=m[i];
    }
    for(int i=1;i<=n;i++) summ[i]=M/m[i];
    for(int i=1;i<=n;i++){
        ll x=0,y=0;
        exgcd(summ[i],m[i],x,y);
        if(x<0) x+=m[i];
        ans+=a[i]*summ[i]*x;
        ans%=M;
    }
    cout<<ans;
}

4.2$\quad$扩展中国剩余定理

中国剩余定理只能处理模数两两互质的情况，无法处理普遍情况。我们可以使用扩展中国剩余定理进行推算。

对于每两个线性同余方程组 $x\equiv a_1\pmod {m_1}\;,\;x\equiv a_2\pmod{m_2}$，将其转化为不定方程 $x=pm_1+a_1=qm_2+a_2$，移项有

$pm_1-qm_2=a_2-a_1$

有裴蜀定理得，方程组有整数解当且仅当 $\gcd(m_1,m_2)|(a_2-a_1)$。这时我们就可以用扩展欧几里得算法得到一组可行解 $(p,q)$，则原来的两个方程可以合并为

$x\equiv m_1p+a_1\pmod{\text{lcm}(m_1,m_2)}$

我们逐一进行合并即可求解。

typedef __int128 ll;
int n;
struct node{
    ll a,m;
};
queue<node> qu;
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 temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
ll lcm(ll x,ll y,ll d){
    return x/d*y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        qu.push(node{b,a});
    }
    for(int i=1;i<n;i++){
        node a,b;
        a=qu.front();qu.pop();
        b=qu.front();qu.pop();
        ll k1,k2;
        if(a.a>b.a) swap(a,b);
        ll c=b.a-a.a;
        ll d=exgcd(a.m,b.m,k1,k2);
        k1*=c/d;
        k2*=c/d;
        ll q=b.m/d,p=a.m/d;
        if(k1<0){
            ll k=ceil((1.0-k1)/q);
            k1+=k*q;
            k2-=k*p;
        }
        else{
            ll k=(k1-1)/q;
            k1-=k*q;
            k2+=k*p;
        }
        node now;
        now.a=k1*a.m+a.a;
        now.m=q*a.m;
        now.a%=now.m;
        qu.push(now);
    }
    node ans=qu.front();
    printf("%lld",(long long)(ans.a%ans.m));
    return 0;
}

五、高次同余方程与BSGS算法

5.1$\quad$BSGS算法

给定 $a,b,p$，已知 $a\perp p$，求解 $x$ 满足

$a^x\equiv b\pmod p$

令 $x=A\left\lceil\sqrt p\right\rceil-B$，其中， $0\leq A,B\leq \left\lceil\sqrt p\right\rceil$，有 $a^{A\left\lceil\sqrt p\right\rceil-B}\equiv b\pmod p$，整理得

$a^{A\left\lceil\sqrt p\right\rceil}\equiv ba^B\pmod p$

我们逐一枚举 $B$ 即可知道所有 $ba^B$。然后建立 hash 表，逐一计算 $a^{A\left\lceil\sqrt p\right\rceil}$，找到与之相等的 $ba^B$ 即可求出 $x=A\left\lceil\sqrt p\right\rceil-B$。

时间复杂度 $O(\sqrt p)$。

ll BSGS(){
    map<ll,ll> hash;
    hash.clear();
    b%=p;
    ll t=sqrt(p)+1;
    for(ll i=0;i<t;i++){
        ll val=b*qpow(a,i,p)%p;
        hash[val]=i;
    }
    a=qpow(a,t,p);
    if(a==0) return (b==0?1:-1);
    for(ll i=0;i<=t;i++){
        ll val=qpow(a,i,p);
        ll j=hash.find(val)==hash.end()?-1:hash[val];
        if(j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;
}