同余方程与不定方程

ni_ju_ge · 2025-06-22 11:23:16 · 算法·理论

本文总结了一些有关同余方程与不定方程的常用定理、公式。

同余方程

定义

若 a\bmod m=b\bmod m，那么称 a,b 对模 m 同余，记为 a\equiv b\pmod m。

逆元

若 p 与 a 互质且 ax\equiv 1\pmod p，则称 x 是 a 在模 p 意义下的逆元，一般记为 a^{-1}。

容易发现，若有 0<b<p 为 a^{-1}，则对于任意的 0<i\le \infty 皆有 bi 为 a^{-1}。一般所说的逆元为最小的 b。

费马小定理

若 p 是与 a 互质的质数，则有 a^{p-1}\equiv 1\pmod p。

证明

构造数集 A=\{1,2,\dots,p-1\}。

证明：\prod_{i=1}^{p-1}a\times A_i\equiv \prod_{i=1}^{p-1}A_i\pmod p。

若有 aA_i\bmod p=aA_j\bmod p=r(1\le i<j\le p-1)，设 aA_i=xp+r,aA_j=yp+r，两式相减得 (A_i-A_j)a=(x-y)p。由于 a,p 互质且 A_i-A_j<p 所以该等式不成立，故每个 aA_i 模 p 的值都是独一无二的，又因为余数只有 p-1 个，故余数集必为 A 的一个排列，于是 \prod_{i=1}^{p-1}a\times A_i\equiv \prod_{i=1}^{p-1}A_i\pmod p 得证。

将左边的 a 提取出来，得 a^{p-1}\prod_{i=1}^{p-1}A_i\equiv \prod_{i=1}^{p-1}A_i\pmod p，化简得 a^{p-1}\equiv 1\pmod p。

费马小定理求逆元

因为有 a^{p-1}\equiv p\pmod p，可得 a\times a^{p-2}\equiv p\pmod p，对比逆元的式子 ax\equiv 1\pmod p 容易发现 x=a^{p-2}，注意这里的 x 不一定 a 模 p 意义下的最小逆元。

注意到有些非质数的数同样满足该定理，例如 341=11\times 13，这样的数被称为伪素数。

剩余系

剩余类

对于任意的一个数 n，根据 a\bmod p 的不同，可以把 a 分为 n 个剩余类，余数为 r 的类表示为 C_r=xp+r。

完全剩余系(完系)

从 n 的每个剩余类中各取出一个元素，这些元素组成了模 n 的完系。

简化剩余系(缩系)

对于 \varphi(n) 个与 n 互质的 r，在这 \varphi(n) 个 C_r 中各取一个元素，组成了模 n 的缩系。

这里 \varphi(n) 是指与 n 互质且 <n 的正整数的个数，在 筛法与函数-筛法求欧拉函数 一节详细介绍。

威尔逊定理

#### 必要性若 $p$ 为质数。构造模 $p$ 的 **缩系** $A=\{1,2,\dots,p-1\}$。取一个 $a\in[1,p-1]$，因为 $a,p$ 互质，故 $\{a,2a,\dots,ap-a\}$ 也为模 $p$ 的 **缩系**，因此只存在一个 $x\in[1,p-1]$ 使得 $ax\equiv 1\pmod p$。 - 若 $a=x$，则有 $x^2\equiv 1\pmod p$，因式分解得 $(x+1)(x-1)\equiv 0\pmod p$，因为 $x,p$ 互质，则 $x=1$ 或 $x=p-1$。 - 若 $a\not=x$，则有 $2\le a,x\le p-2$，由于每个 $a$ 对应着唯一的 $x$ ，所以有 $\dfrac{p-2-2+1}{2}=\dfrac{p-3}{2}$ 对 $a,x$ 使得 $ax\equiv 1\pmod p$，将所有这样的式子乘起来就能得到 $(p-2)!\equiv 1\pmod p$，两边同乘 $p-1$ 得 $(p-1)!\equiv 1\pmod p$，即 $(p-1)!\equiv -1\pmod p$。 #### 充分性若 $p$ 为合数。当 $p=1$ 时，$(1-1)!\equiv 0\pmod 1

当 p=4 时，(4-1)!\equiv 2\pmod 4

当 p>4 时，

若 p 不是完全平方数，构造 2\le a<b< p，则有 (p-1)!=1\times2\times\dots\times a\times\dots\times b\times\dots\times p-1=kp，有 (p-1)!\equiv 0\pmod p。
若 p 是完全平方数，构造 p=k^2，则有 (p-1)!=1\times2\times\dots\times k\times\dots\times 2k\times\dots\times p-1=kp，有 (p-1)!\equiv 0\pmod p。
推论

若 p 为质数，则 (p-1)!+1\equiv 0\pmod p。

若 p>4 且 p 为合数，则 (p-1)!\equiv 0\pmod p。

e.g. 给定 n，求 S=\sum_{p=1}^{n}\left\lfloor\dfrac{(p-1)!+1}{p}-\left\lfloor\dfrac{(p-1)!}{p}\right\rfloor\right\rfloor。

记 K=\left\lfloor\dfrac{(p-1)!+1}{p}-\left\lfloor\dfrac{(p-1)!}{p}\right\rfloor\right\rfloor

若 p 为质数，则 \dfrac{(p-1)!+1}{p} 为整数，K=1。

否则 \dfrac{(p-1)!+1}{p}=\left\lfloor\dfrac{(p-1)!}{p}\right\rfloor，K=0。

筛出 \in[1,n] 的质数即可。

欧拉定理

若 a,m 互质，则有 a^{\varphi(m)}\equiv 1\pmod m。

证明

设 k=\varphi(m)。

构造模 m 的缩系 \{r_1,r_2,\dots,r_k\}。

因为 a,m 互质，所以 \{ar_1,ar_2,\dots,ar_k\} 也是 m 的一个缩系，则有 \prod_{i=1}^k r_i\equiv\prod_{i=1}^k ar_i\equiv a^k\times\prod_{i=1}^k r_i\pmod m，约去 \prod_{i=1}^k r_i 可得 a^k\equiv 1\pmod m。

用欧拉定理证费马小定理

当 m 为质数时，\varphi(m)=m-1，则有 a^{m-1}\equiv 1\pmod m。

扩展欧拉定理

对于任意的 a,b,m，有：

a^b\equiv\begin{cases}a^b&b<\varphi(m)\\a^{b\bmod\varphi(m)+\varphi(m)}&b\ge\varphi(m)\end{cases}\pmod m

e.g. 模版。

观察到 b 很大，将 b 降幂后再快速幂即可。

int gphi(int m) {
    long long s=m;
    for(int i=2;i*i<=m;i++) {
        if(m%i==0) {
            s=s/i*(i-1);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) s=s/m*(m-1);
    return s;
}
void cele(int mod) {
    bool fl=false;
    for(int i=0;i<s.size();i++) {
        b=(b*10+(s[i]-'0'));
        if(b>mod) b%=mod,fl=true;
    }
    if(fl) b+=mod;
}
long long qpow(long long a,int b,int mod) {
    long long ans=1;
    while(b) {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans%mod;
}

连续逆元线性求

模版。

当前已知 1\sim i-1 的逆元，要求 i(i>1) 在模 p 意义下的逆元。

设 p=ki+r(0\le r<i)，则有 ki+r\equiv 0\pmod p，两边同乘 i^{-1}r^{-1} 得 kr^{-1}+i^{-1}\equiv 0\pmod p，移项得 i^{-1}\equiv -kr^{-1}\equiv -\left\lfloor\frac{p}{i}\right\rfloor\times (p \bmod i)^{-1}\pmod p。

于是就求出了 i 的逆元。

for(int i=2;i<=n;i++) {
    a[i]=((p-p/i)*a[p%i])%p;//注意可能是负数，把 p/i 变为 p-p/i 以去掉负号
    printf("%lld\n",a[i]);
}

不定方程

定义

若未知数的个数大于方程的个数，则该方程被称为不定方程。

不定方程一般有无数个解，所以题目会对未知数有一些约束条件。

裴蜀定理

一定存在 x,y 满足 ax+by=\gcd(a,b)。

该定理对不定方程是否有整数解做出了一个判定方式。

证明

设取整数 x_0,y_0 时，ax_0+by_0=m，\gcd(a,b)=k，m 为满足条件的最小正整数。

现在要证 m=k。

因为 x_0,y_0 为整数，所以有 k\mid ax_0,k\mid by_0，则 k\mid ax_0+by_0，得 k\mid m (1)。

设 a=qm+r(0\le r<m)，则有

r=a-qm=a-q(ax_0+by_0)=a-aqx_0-bqy_0=a(1-qx_0)+b(-qy_0)

因为 qx_0,qy_0 均为整数，所以可以使 x=1-qx_0,y=-qy_0,r=ax+by。

由于 r<m 且 m 是满足条件的最小正整数，所以 r=0,a=qm，因此 m\mid a，同理得 m\mid b，故 m\mid k (2)。

综合 (1)(2) 得：m=k 得证。

简单思考一下可以发现，若 ax'+by'=k\times\gcd(a,b)，则 x',y'，变为原解的 k 倍即可，故形如 ax+by=c 的不定方程只要满足 c=k\times\gcd(a,b) 就有整数解，k 为整数。

同理可得，n 个未知数的不定方程 \sum_{i=1}^{n} a_ix_i=s 满足 s=k\times\gcd(a_i) 时有整数解。

e.g. 模版。

根据上面的结论求出 \gcd(\left|A_i\right|) 即可。

for(int i=1;i<=n;i++) {
    cin>>a;
    if(a<0) a=-a;
    ans=G(ans,a);
}

扩展欧几里得算法

欧几里得算法

\gcd(a,b)=\gcd(b,a\bmod b)

没错，就是这个。

从辗转相除法到不定方程

求 ax+by=\gcd(a,b) 的整数解。

上面我们已经论证了该方程有整数解，这里使用扩展欧几里得算法求解。

\begin{aligned}\gcd(a,b)=\gcd(b,a\bmod b)&=bx_1+(a\bmod b)y_1\\&=bx_1+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)y_1\\&=ay_1+b(x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1)\\&=ax+by\end{aligned}

所以有 x=y_1,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1。

注意到 b=0 时 x=1,y=0，故递归到下界 b=0 解决即可得到一组特解。

long long exgcd(long long a,long long b,long long &x,long long &y) {
    if(b==0) {
        x=1,y=0;
        return a;
    }
    long long d,x1,y1;
    d=exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

从特解到通解

考虑同时使 ax\gets ax+k 和 by\gets by-k 来构造通解。

故有 x'=x+k\times\dfrac{b}{\gcd(a,b)},y'=y-k\times\dfrac{a}{\gcd(a,b)}。

从不定方程到同余方程

求 ax\equiv b\pmod m(0\le b<m) 的整数解。

设 ax=-ym+b，则有 ax+ym=b。根据裴蜀定理判断该方程是否有整数解，然后用扩展欧几里得计算即可。

e.g. 并非模版。

设 m=19260817。

将同余方程化为 bx+ym=a 求解即可。

Another Idea：求 b^{-1}，就有 bb^{-1}\equiv 1\pmod m，两边同乘 a 得 b\times(ab^{-1})\equiv a\pmod m，所以 x=ab^{-1}。

中国剩余定理

模版。

即要求

\begin{cases}x\equiv a_1\pmod {p_1}\\x\equiv a_2\pmod {p_2}\\\dots\\x\equiv a_n\pmod {p_n}\end{cases}

中 x 的解。其中 m 是 两两互质的整数，0\le p_i<m_i。

中国剩余定理解法

1.设 M=\prod_{i=1}^n m_i\ 2.设 c_i=\dfrac{M}{m_i}\ 3.计算 c_i 在模 m_i 意义下的逆元 c_i^{-1}\ 4.x=(\sum_{i=1}^na_ic_ic_i^{-1})\bmod M

证明

由于 (\sum_{i=1}^na_ic_ic_i^{-1})\bmod M 对于 m_i 只是减去了它的若干倍，对余数没有影响，所以只需要证 x=\sum_{i=1}^na_ic_ic_i^{-1} 使同余方程组成立。

当 i\not=j 时，因为 c_j=\dfrac{M}{m_j} 中包含项 m_i，故 c_j\equiv 0\pmod {m_i},c_jc_j^{-1}\equiv 0\pmod {m_i}
当 i=j 时，因为 c_i=\dfrac{M}{m_i} 不含 m_i 且 m 两两互质，所以 c_i\not\equiv 0\pmod {m_i},c_ic_i^{-1}\equiv 1\pmod {m_i}

故 x=(\sum_{i=1}^na_ic_ic_i^{-1})\bmod m_i=a_ic_ic_i^{-1}=a_i,x\equiv a_i\pmod {m_i}。

long long crt() {
    long long M=1,ans=0;
    for(int i=1;i<=n;i++) M*=m[i];
    for(int i=1;i<=n;i++) {
        long long c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        ans=(ans+(c*x*a[i])%M)%M;
    }
    return (ans%M+M)%M;
}

扩展中国剩余定理

模版。

你猜同余方程的内容为什么会出现在不定方程里。

相较于中国剩余定理，本题 m 不一定两两互质。

扩展中国剩余定理解法

合并同余方程求解。

将前两个同余方程化为 x=m_1p+a_1=m_2q+a_2。则有 m_1p-m_2q=a_2-a_1。

可以用裴蜀定理判断是否有解，使用扩展欧几里得算法求解。

所以有通解 p'=p+\frac{m_2}{\gcd(m_1,m_2)}，代入得 x=m_1p+\frac{m_1m_2}{\gcd(m_1,m_2)}+a_1=\operatorname{lcm}(m_1,m_2)+m_1p+a_1，将 m_1p+a_1 视作余数即可将两个同余方程合并为 x\equiv m_1p+a_1\pmod{\operatorname{lcm}(m_1,m_2)}。

合并 n-1 次即可。正确性显然。

long long mul(long long a,long long b,long long mod) {
    long long ans=0;
    while(b>0) {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
long long excrt() {
    long long m1,m2,a1,a2;
    m1=m[1],a1=a[1];
    for(int i=2;i<=n;i++) {
        m2=m[i],a2=a[i];
        long long p,q;
        long long d=exgcd(m1,m2,p,q);//注意这里 a2-a1 并非是 gcd(m1,m2)
//      if((a2-a1)%d) return -1;裴蜀定理判断是否有解，这里不用 
        long long k=m2/d,c=(((a2-a1)/d)%m2+m2)%m2;
        p=mul(p,c,k);//a2-a1 是 gcd(m1,m2) 的倍数，这里求出正确的特解
        p=(p%k+k)%k;//保证最小
        a1=m1*p+a1,m1=m1*(m2/d);
        a1%=m1;
    }
    return (a1%m1+m1)%m1;
}

BSGS

模版。

BSGS(Baby Step Gaint Step)，大步小步算法，用于求解 a,p 互质的同余方程 a^x\equiv b\pmod p。

求解方法

由扩展欧拉定理 a^x\equiv a^{x\bmod\varphi(p)}\pmod p 得 a^x 模 p 意义下的最小循环节为 \varphi(p)，由于 \varphi(p)<p，所以可以暴力枚举 x=0\sim p，时间复杂度 O(p)。

令 x=im-j，m=\left\lceil\sqrt n\right\rceil,1\le i\le m,0\le j\le m-1，显然任意的 x\in [0,p] 均可被表示出来。

则有 a^{im-j}\equiv b\pmod p,(a^m)^i\equiv ba^j\pmod p。

枚举 j，将 \operatorname{key}=ba^j\bmod p,\operatorname{val}=j 放入哈希表，若 \operatorname{key} 重复则用大的 j 替换小的。
枚举 i，查找是否有 \operatorname{key}=(a^m)^i，有则 x=im-j。

由于 i,i\le \left\lceil\sqrt p\right\rceil，所以时间复杂度为 O(\sqrt p)。正确性显然。

long long a,b,p;
map<long long,long long> mp;
long long bsgs() {
    long long m=sqrt(p);
    if(m*m!=p) m++;
    mp[b]=0;
    for(long long i=1;i<m;i++) {
        b=(b*a)%p;
        mp[b]=i;
    }
    long long k=1;
    for(int i=1;i<=m;i++) k=(k*a)%p;
    long long i,j,t=1;
    for(i=1;i<=m;i++) {
        t=(t*k)%p;
        if(mp.count(t)) return i*m-mp[t];
    }
    return -1;
}

为什么要求 a,p 互质

### 扩展 BSGS [模版](https://www.luogu.com.cn/problem/P4195)。你猜同余方程的内容为什么会出现在不定方程里。相较于 BSGS，本题 $a,p$ 不互质。 #### 求解方法将同余方程 $a^x\equiv b\pmod p$ 化为 $a\times a^{x-1}\equiv b\pmod p$，进一步变为不定方程 $a\times a^{x-1}+py=b$，将 $a,p$ 视为常数，设 $d=\gcd(a,p)$，则若 $d\nmid b$，方程无解，否则将 **同余方程** 两边同除 $d$，得 $\dfrac{a}{d}a^{x-1}\equiv \dfrac{b}{d}\pmod{\dfrac{p}{d}}$，记 $p'=\dfrac{p}{d}$，若 $\gcd(a,p')\not=1$ 则继续直到 $a\perp p'$。记 $D=\dfrac{p}{p'}$，共进行了 $k$ 次，则 $\dfrac{a^k}{D}a^{x-k}\equiv b\pmod {p'}$，由于有 $a\perp p'$，所以有 $\dfrac{a^k}{D}\perp p'$，两边同乘它的逆元后就变为了 BSGS。 ```cpp long long bsgs(int A) { long long m=sqrt(p); if(m*m!=p) m++; mp[b]=0; for(long long i=1;i<m;i++) { b=(b*a)%p; mp[b]=i; } long long k=1; for(int i=1;i<=m;i++) k=(k*a)%p; long long i,j,t=A;//注意这里 t 从 a^k/D 开始 for(i=1;i<=m;i++) { t=(t*k)%p; if(mp.count(t)) return i*m-mp[t]; } return -1; } long long exbsgs() { if(b==1||p==1) return 0; long long d,k=0,A=1; while(true) { d=gcd(a,p); if(d==1) break; if(b%d) return -1; k++,b/=d,p/=d,A=(A*(a/d))%p; if(A==b) return k; } long long ans=bsgs(A); if(ans==-1) return -1; else return ans+k;//记得算出来的是 x-k 要加 k } ```