同余&逆元&CRT

int_R · 2022-10-05 18:56:53 · 个人记录

同余&逆元&CRT

前记

upd 2022/10/9 14:36:06 : 修改了一些错误。

upd 2023/4/14 17:50:12 ：修改了 CRT 部分并增加了 EXCRT。

第一篇学习笔记

之前搞了好几天，后来发现忘得差不多了，又重新温习，顺便做个笔记；涉及众多式子，如果有错请指出

1.同余式

如果两个数 a 和 b 除以 m 后的余数相同，我们称 a 与 b 对模 m 同余，记作

同余式就是如上这个式子，如果换成比较简单的形式就是

同时他还有个基本性质

显然的，若 a \equiv b \pmod m，当且仅当 m \mid (a-b)，换言之若 a \not\equiv b \pmod m,则 m \nmid (a-b)

这里 a \mid b 表示 a 整除 b ，即 b 能被 a 整除

同余关系还具有

自反性：a \equiv a \pmod m

对称性：a \equiv b \pmod m，则 b \equiv a \pmod m

传递性：a \equiv b \pmod m，且 b \equiv c \pmod m，则 a \equiv c \pmod m

这些性质都可以根据变形后的式子轻易得出。

2.裴蜀定理

2.1裴蜀定理

在了解了同余式的定义后，我们来看一个与之相关的定理

裴蜀定理得名于法国数学家艾蒂安·裴蜀，亦称贝祖定理。

1.裴蜀定理是指方程 ax + by = m 有解，当且仅当 m 是 \gcd(a,b) 的倍数时，方程有整数解；

2.同时，一定存在整数 x,y，使 ax+by=\gcd(a,b) 成立；

3.特别的，只有 a 和 b 互质时,ax + by = 1 才有整数解。

极不严谨的证明：

方程两边同时除以 \gcd (a,b)

因为 \gcd(a,b) \mid a 且 \gcd(a,b) \mid b，所以 \gcd(a,b) \mid ax 且 \gcd(a,b) \mid by，则 \gcd(a,b) \mid m

通俗来说就是方程左边一定为整数，所以方程右边也一定为整数，所以 m 一定是 \gcd(a,b) 的倍数

更严谨的证明方法请 bdfs。

2.2 同余式与裴蜀定理的关系

那么为什么说同余式与裴蜀定理有关呢,因为

由于我们要求的方程是与 x 有关的方程， y 只是辅助答案且取值为任意整数，所以我们可以写成

对于这个方程我们便可用扩展欧几里得来求解

3.欧几里得&扩展欧几里得

3.1 欧几里得算法

我们自然是要先来看看欧几里得算法的

古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

欧几里得算法又称辗转相除法，一般用来求两个数的最大公约数，即

证明：

假设 a>b

设 r=a\%b,d=\gcd(a,b)

则 a 可以表示成 kb+r ( k 为正整数）

则 r 就等于 a-kb

我们知道 d\mid a,d\mid b，则 d\mid r

因此 d 也是 b 和 a\%b 的最大公因数

int gcd(int a,int b){return (b)?gcd(b,a%b):a;}

#include<algorithm>
using namespace std;
int a,b;
int main(){int c=__gcd(a,b);}

3.2 扩展欧几里得

扩展欧几里得算法是欧几里得算法的扩展（废话），即我们在辗转相除的过程中，求出 ax + by =\gcd(a,b) 的一组特解，设 \gcd(a,b) 为 d

具体的来说我们在进行辗转相除时

设当前的两个数为 a,b（这里不是给出的 a,b，而是辗转相除过程中的 a,b ）

则下一轮要递归时的两个数为 b,a\%b

假设我们已经求出了 bx_0+(a\%b)y_0 = d，我们现在就是要利用已得出的 x_0,y_0 来推导出 ax+by=d

因为 a\%b = a - b \lfloor a/b \rfloor，则前式可以变为

整理得

所以

那么我们的边界条件呢？

我们在辗转相除时最后当 b=0 时，我们返回的是 a，即 d

也就是说相当于 a+0=d

所以初始时 x=1,y=0，（其实 y 可以为任何数）

设求出来的特解为 x,y，通解即为

另外，扩展欧几里得还可以用来求逆元

//用来求不定方程 ax+by=c 的解
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;return d;
}

4.逆元

在数论中，如果 ab \equiv 1 \pmod p ，我们就说 a 和 b 在模 p 意义下互为乘法逆元，记作 a=inv(b) 。

实际意义即如果要在模 p 意义下除以一个数，就相当于乘上这个数在模 p 意义下的逆元

通常使用扩展欧几里得，费马小定理，和线性递推法来求乘法逆元

5.求逆元

5.1 扩展欧几里得法

我们设 b 为 a 在模 p 意义下的逆元,则

就相当于求

利用扩展欧几里得法求解即可

//用来求a在%p意义下的乘法逆元x
int x,y,a,p;
void exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return ;}
    exgcd(b,a%b,y,x),y-=(a/b)*x;return ;
}
int main()
{
  exgcd(a,p,x,y);
  x=(x%p+p)%p;
}

5.2 费马小定理

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。

费马小定理为：若 p 是质数，且 \gcd(a,p) = 1，则有

至于证明，我不会

费马小定理的证明

从逆元的定义推导，可得 a \cdot inv(a) \equiv 1 \equiv a^{p-1} \pmod p，于是有

利用快速幂计算 a^{p-2} 即可

//仅适用于p为质数
int a,b,p,ans=1;
int main()
{
    b=p-2;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
}

5.3 线性递推法

同时求逆元还用一种线性递推法

证明：

设 p=aq+r ,即 q= \lfloor p/a \rfloor,r=p \% a

在模 p 意义下，有 aq+r \equiv 0 \pmod p

整理得 a=-r \cdot inv(q) \pmod p

则 inv(a)=-q \cdot inv(r) \pmod p

即 inv(a) = - \lfloor p/a \rfloor \cdot inv(p\ mod\ a) \pmod p

//仅适用于p是质数
ans[1]=1;
for(int i=2;i<=n;i++)
{
    ans[i]=(-p/i*ans[p%i]);
    ans[i]=(ans[i]%p+p)%p;
}

6.CRT & EXCRT

孙子定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题。

给定 n 组非负整数 a_i, b_i，求解关于 x 的方程组的最小非负整数解。

6.1 中国剩余定理（CRT）

中国剩余定理有一个前提是模数 b_i 两两互质。

如果我们将每个方程分开看:

如果已经满足了 x_1 \equiv b_1 \pmod {a_1} ，那么只有当 a_1 \mid x_2 时，x_1+x_2 \equiv b_1 \pmod {a_1}；

同理当 a_1 \mid x_2,a_1 \mid x_3 时, x_1+x_2+x_3 \equiv b_1 \pmod {a_1}。

所以设 p=\prod\limits_{i=1}^n a_i,r_i=\prod\limits_{j=1,j\not=i}^{n} a_j=\dfrac{p}{a_i},m_i=\dfrac{x_i}{r_i}，我们要求得一个解 x=\sum\limits_{i=1}^{n} a_i，只需要解出：

由于模数两两互质，所以设 w_i=\dfrac{m_i}{b_i}，则 r_i\cdot w_i\equiv 1\pmod {a_i}。

此时求 w_i 即相当于求逆元，解得 w_i ,则 m_i=w_i\cdot b_i,x_i = m_i\cdot r_i。

综上得方程组的解为（这里的逆元为模 a_i 意义下的）：

for(int i=1;i<=n;i++) cin>>a[i]>>b[i],x*=a[i];
for(int i=1;i<=n;i++)
{
    int r=x/a[i];
    ans+=(b[i]*r*inv(r,a[i]))%x;
}

6.2 扩展中国剩余定理（EXCRT）

当不保证模数两两互质时，此时 r_i 与 a_i 并不互质，所以不会有模 a_i 意义下的逆元，所以要换一种思路，每次合并两个同余方程。

假设现在要合并 \begin{cases} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2}\end{cases}，我们要先找到一个解 x。

变换一下 x=k_1\cdot a_1+b_1=k_2\cdot a_2+b_2，移项得 k_1\cdot a_1-k_2\cdot a_2=b_2-b_1，此时相当于不定方程，用扩展欧几里得法求解 k_1,k_2，此时得到最小整数解 x_0。

显然我们将两个同余方程合并为 x\equiv x_0\pmod {\mathrm{lca(a_1,a_2)}} 即可，最后合并成一个同余方程，答案即得。

for(register signed i=2;i<=n;++i)
{
    int x,y,d;d=exgcd(x,y,a[i-1],a[i]);
    x*=(b[i]-b[i-1])/d;
    a[i]=a[i-1]*a[i]/d;
    b[i]=((x*a[i-1]+b[i-1])%a[i]+a[i])%a[i];
}
long long ans=b[n];cout<<ans<<'\n';return 0;

6.3 有解条件

我们发现当保证模数两两互质时，使用 CRT 不会出现无解的情况，但是当模数不是两两互质，使用 EXCRT 时，需要求解一个不定方程，根据裴属定理我们可以知道当 \gcd(a_1,a_2) \nmid (b_2-b_1) 时，方程无解，此时整体也无解。

所以模数两两互质是有解的充分不必要条件。

参考资料：

同余式-百度百科

同余方程详解-羊博士粉丝团代理团长

裴蜀定理-百度百科

扩展欧几里得算法-百度百科

算法学习笔记(8)：拓展欧几里得-Pecco

乘法逆元-百度百科

算法学习笔记(9)：逆元-Pecco

费马小定理-百度百科

费马小定理（易懂）-四年rain

孙子定理-百度百科

算法学习笔记(10): 中国剩余定理-Pecco

扩展中国剩余定理-阮行止