同余
本章主要记录有关同余、费马小定理、欧拉定理、扩展欧几里得算法、裴蜀定理、乘法逆元、威尔逊定理、线性同余方程、中国剩余定理、扩展中国剩余定理、BSGS以及扩展BSGS的学习笔记。
由于内容复杂且关联较少，建议配备 ctrl+F 进行快乐食用。
一、基础知识：
这个板块着重介绍同余的基本知识，虽然多为数学竞赛内容，但也对信息学竞赛有不少帮助，定理和性质为拓展内容。
本部分参考《初等数论》进行撰写。
1.1 基本定义、定理与性质：
定义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$ 除后所得的最小非负余数相等，即若
$$
a=q_1m+r_1,0\leq r_1<m\
b=q_2m+r_2,0\leq r_2<m,
$$
则 $r_1=r_2$。
性质Ⅰ$\quad$ 同余是一种等价关系，即有
$$
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}
$$
性质Ⅱ$\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_nxn+\cdots+a_0$，$g(x)=b_nxn+\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)$ 的范围，有
$$
ab=(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;
}