同余方程详解

大家好，欢迎来到IT知识分享网。

同余概述

定义： 同余给定正整数$m$，若用$m$去除两个整数$a$和$b$，所得的余数相同，称a和b对模$m$同余，记作$a\equiv b(modm)$,并称该式为同余式，否则，称$a$和$b$对模$m$不同余。
定理：

1. $a\equiv b(modm)$，当且仅当$m|(a-b)$
2. $a\equiv b(modm)$，当且仅当存在正整数$k$，使得$a=b+km$
3. 同余关系是等价关系，即
   (1）自反性：$a\equiv a(modm)$
   (2）对称性：$a\equiv b(modm)$，则 $b\equiv a(modm)$
   (3）传递性：$a\equiv b(modm),b\equiv c(modm)$，则 $a\equiv c(modm)$
   
   
   

定义：由与同余关系是等价关系，对于所有整数会被分为$m$的集合，这些集合称为模$m$剩余类(同余类)。每个集合中的任意两个数都是模$m$同余的。
定义：一个整数集合，且满足对于任意的整数在此集合中存在一个元素与该整数模$m$同余，该整数$0，1，2，...，m-1$的集合是模$m$的完全剩余系。
定理：若$a$，$b$，$c$，$d$是整数，$m$是正整数，且$a\equiv b(modm),c\equiv d(modm)$，则：
4. $a+b\equiv b+c(modm)$
5. $a-b\equiv b-c(modm)$
6. $ac\equiv bc(modm)$
7. $ac\equiv bc(modm),c\ne 0$，则$a\equiv b(mod\frac{m}{gcd(m,c)})$
8. $ax+cy=bx+dy(modm)$，其中$x，y$为任意整数，即同余式可以相加
9. $ac\equiv bd(modm)$，即同余式可以相乘
10. $a^n\equiv b^n$，$n>0$
11. $f(a)\equiv f(b)(modm)$，其中$f(x)$为任一整数多项式

定理：若a，b，c，d为整数，m为正整数，则：

1. 若$a\equiv b(modm)$，且$d|m$，则$a\equiv b(modd)$
2. 若$a\equiv b(modm)$，则$(a,m)=(b,m)$，其中$(a,m)$为$a$和$m$的最大公约数
3. $a\equiv b(mod{m}_i)(1\le i\le n)$，同时成立，当且仅当$a\equiv b(mod[m_1,m_2,...,m_n])$

证明上式1， 若$a\equiv b(modm)$ ，则$ax\equiv bx(modm)$，令$xd=m$，两边同除$x$，$a\equiv b(mod\frac{m}{gcd(m,x)})$，$gcd(m,x)=x$，即$a\equiv b(modd)$
证明上式2，若$d$为$a$和$m$的公约数，且$m|(a-b)，d|a，d|m$，所以$d|b$，对于所有$d$上式都成立,反之亦然成立，即$a$与$m$和$b$与$m$的公约数集相同，所以$(a,m)=(b,m)$

一元线性同余方程

定义：$a，b$是整数，$m$是正整数，形如$ax\equiv b(modm)$，且$x$是未知整数的同余式称为一元线性同余方程.
定理：$a，b$是整数，$m$是正整数，$(a,m)=d$.如果$d|b$，则方程恰有$d$个模$m$的不同余的解，否则方程无解。
证明：方程有解时，$(ax-b)=ym$，$y$为整数，即$ax-ym=b$，由裴蜀定理可知，对任何整数$a、b$和它们的最大公约数$d$，关于未知数$x$和$y$的线性不定方程（称为裴蜀等式）：若$a,b$是整数,且$gcd(a,b)=d$，那么对于任意的整数$x,y$,都有$ax+by$一定是$d$的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立。因为y为整数，不是定值，所以把上式化为$\frac{a}{d}x-\frac{m}{d}y=\frac{b}{d}$，随着$y$值变化，$x$存在$d$个不同余的解。所以如果$(a,m)=d$，$d|b$，那么方程恰有$d$个不同余解 ，$d$个解分别关于$\frac{m}{d}$同余，分别为$x，x+\frac{m}{d}，x+2\ast \frac{m}{d}，...，x+(d-1)\ast \frac{m}{d}$

求解一元线性同余方程时可以使用扩展欧几里得算法.

void exgcd(int a,int b,int&d,int&x,int&y)//扩展欧几里得算法 { 
    if(b==0) { 
    x=1,y=0; d=a; return; } else { 
    int r=exgcd(b,a%b,x,y); //r=GCD(a,b)=GCD(b, a%b) int t=x; x=y; y=t-a/b*y ; return; } } 

int f(int a,int b,int m)//计算同余方程所有解 { 
    int x,y,d; exgcd(a,m,d,x,y); if(b%d) return -1;//无解 x=x*(b/d)%m; for(int i=1;i<=d;i++) ans[i]=(x+(i-1)*m/d)%m; } 

一元线性同余方程组

任意的一元线性同余方程组都可以化为$x\equiv b(modm)$，而一元线性同余方程组就是多个这样的式子联合求解。
例如：$x\equiv b_1(mod{m}_1)$ 与$x\equiv b_2(mod{m}_2)$，这两个方程就构成了一个同余方程组。
令$m=[m_1,m_2]$,此时方程组有解的充分必要条件是$(m_1,m_2)|b_1-b_2$,此时方程仅有一个非负整数解。
证明：讲两式写为$x=b_1+m_1{y}_1,x=b_2+m_2{y}_2$，联立可得$b_1+m_1{y}_1=b_2+m_2{y}_2$，即$m_1{y}_1-m_2{y}_2=b_1-b_2$，由裴蜀定理可知成立。此时方程的解即为$(b_1+m_1{y}_1)\%m$或$(b_2+m_2{y}_2)\%m$
上面式子$m_1{y}_1-m_2{y}_2=b_1-b_2$可由扩展欧几里得求解$y_1$和$y_2$.
对于多个方程的方程组，这样两两求解合并即可求出最后的解。

int solve() { 
    int n,m1,b1,m2,b2,x,y,d,flag=1; cin>>n>>m1>>b1; for(int i=1;i<n;i++) { 
    cin>>m2>>b2; int c=b2-b1; exgcd(m1,m2,d,x,y); if(c%d!=0) flag=0; x=(x*c/d)%(m2/d);//求小于m2/d的解 b1=m1*x+b1; m1=m1*(m2/d);//合并后m应为m1和m2的最小公倍数 } if(flag) return b1; else return -1; } 

中国剩余定理

int m[maxx]; int intChina(int n) { 
    int M=1,Mi,x0,y0,d,ans=0; for(int i=1;i<=n;i++) M*=m[i]; for(int i=1;i<=n;i++) { 
    Mi=M/m[i]; exgcd(Mi,m[i],d,x0,y0) ans=(ans+Mi*x0*a[i])%M; } return ans; } 

由中国剩余定理可得的两个定理

1. 若$a，b$是正整数，那么有$(2^a-1,2^b-1)=2^{(}a,b)-1$.
2. 正整数$2a-1，2b-1$是互质的，当且仅当a与b是互质的。

#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxx=1e6+7,M=21252; void exgcd(int a,int b,int&d,int&x,int&y) { 
    if(b==0) { 
    x=1,y=0; d=a; return; } else { 
    exgcd(b,a%b,d,x,y); int t=x; x=y; y=t-a/b*y ; return; } } int m[maxx],a[maxx]; int intChina(int n) { 
    int Mi,x0,y0,d,ans=0; for(int i=1;i<=n;i++) { 
    Mi=M/m[i]; exgcd(Mi,m[i],d,x0,y0); ans=(ans+Mi*x0*a[i])%M; } return ans; } int main() { 
    ios::sync_with_stdio(0); int p,e,i,d,s=1; m[1]=23,m[2]=28,m[3]=33; while(cin>>p>>e>>i>>d&&p!=-1) { 
    a[1]=p; a[2]=e; a[3]=i; int ans=intChina(3); while(ans<=d) ans+=M; cout<<"Case "<<s++<<": the next triple peak occurs in "<<ans-d<<" days."<<endl; } }