文章目录
前言1同余初步1-1认识同余1-2同余的性质1-3认识不定方程1-4斐蜀定理与求解不定方程1-5乘法逆元
2同余方程与中国剩余定理CRT2-1认识同余方程2-2中国剩余定理
前言
我个人认为同余在计算机编程中有着巨大的作用，无论是在算法竞赛，科研，日常工作都起着重大的作用。本篇文章旨在帮助读者快速的理解与学习同余，语言较为通俗易懂。为了浅显易懂，本篇文章去除了冗杂的证明，但仍保留了一些重要的证明。希望读者可以理解与熟练使用同余方面知识。
1同余初步
1-1认识同余
我们小学学除法时就学过，被除数除以除数等于商加余数，就比如17除以5等于3余2，3是商，2是余数，我们在小学写作：
17
÷
5
=
3......2
17\div5=3......2
17÷5=3......2那么在我们把被除数，除数，余数的关系叫做取模，也就是被除数取模除数等于商，记作
被除数
m
o
d
除数
=
余数
被除数 mod 除数=余数
被除数mod除数=余数在大多数编程语言中，mod写作%，所以上面的式子可以写成
被除数
%
除数
=
余数
被除数\%除数=余数
被除数%除数=余数举个例子，就比如
a
÷
b
=
c
.
.
.
.
.
.
d
a\div b=c......d
a÷b=c......d，我们就写作
a
m
o
d
b
=
d
a\,mod\, b=d
amodb=d。
模的性质有很多，显而易见的有：
1.
(
a
+
b
)
m
o
d
m
=
(
a
m
o
d
m
+
b
m
o
d
m
)
m
o
d
m
1.\,(a+b)\,mod\,m=(a\,mod\,m+b\,mod\,m)\,mod\,m
1.(a+b)modm=(amodm+bmodm)modm
2.
(
a
−
b
)
m
o
d
m
=
(
a
m
o
d
m
−
b
m
o
d
m
)
m
o
d
m
2.\,(a-b)\,mod\,m=(a\,mod\,m-b\,mod\,m)\,mod\,m
2.(a−b)modm=(amodm−bmodm)modm
1.
(
a
×
b
)
m
o
d
m
=
(
a
m
o
d
m
×
b
m
o
d
m
)
m
o
d
m
1.\,(a\times b)\,mod\,m=(a\,mod\,m\times b\,mod\,m)\,mod\,m
1.(a×b)modm=(amodm×bmodm)modm以上式子的证明较为简单，大家可以自己尝试，这里不再过多赘述。
大家由以上公式可能会推出模的除法
(
a
÷
b
)
m
o
d
m
=
(
a
m
o
d
m
÷
b
m
o
d
m
)
m
o
d
m
(a\div b)\,mod\,m=(a\,mod\,m\div b\,mod\,m)\,mod\,m
(a÷b)modm=(amodm÷bmodm)modm，但是模的除法并不是这样的，有关于除法的内容，我们将在1-5乘法逆元中继续探讨。
那么，我们在日常计算中会遇到这种情况:
23
÷
10
=
2......3
23\div10=2......3
23÷10=2......3,
43
÷
10
=
4......3
43\div10=4......3
43÷10=4......3像这种被除数不一样，除数和商一样的情况，我们叫做同余，同余的定义如下：
若
x
m
o
d
z
=
y
m
o
d
z
，则称
x
,
y
模
z
同余，记作
x
≡
y
(
m
o
d
z
)
若x\,mod\,z=y\,mod\,z，则称x,y模z同余，记作x\equiv y(mod\, z)
若xmodz=ymodz，则称x,y模z同余，记作x≡y(modz)有的时候，我们也会把
被除数
m
o
d
除数
=
余数
被除数mod除数=余数
被除数mod除数=余数 写作
被除数
≡
余数（
m
o
d
除数）
被除数\equiv余数（mod\,除数）
被除数≡余数（mod除数）
了解了同余的定义，我们来接着看同余的性质。
1-2同余的性质
同余有很多性质，这里我们来看主要的几条：
1.
x
≡
x
(
m
o
d
m
)
。
1.x\equiv x(mod\,m)。
1.x≡x(modm)。
2.
若
x
≡
y
(
m
o
d
m
)
并且
y
≡
z
，那么
x
≡
z
(
m
o
d
m
)
2.若x\equiv y(mod\, m)并且y\equiv z，那么x\equiv z(mod\,m)
2.若x≡y(modm)并且y≡z，那么x≡z(modm)
3.
若
x
≡
y
(
m
o
d
m
)
,
则
x
+
z
≡
y
+
z
(
m
o
d
m
)
3.若x\equiv y(mod\,m),则x+z\equiv y+z\,(mod\,m)
3.若x≡y(modm),则x+z≡y+z(modm)
4.
若
x
≡
y
(
m
o
d
m
)
,
则
x
×
z
≡
y
×
z
(
m
o
d
m
)
4.若x\equiv y(mod\,m),则x\times z\equiv y\times z\,(mod\,m)
4.若x≡y(modm),则x×z≡y×z(modm)
5.
若
x
≡
y
(
m
o
d
m
)
,
则
x
z
≡
y
z
(
m
o
d
m
)
5.若x\equiv y(mod\,m),则x^z\equiv y^z\,(mod\,m)
5.若x≡y(modm),则xz≡yz(modm) 这里不加证明的，我们引出一个重要性质：
6.
x
≡
y
(
m
o
d
m
)
的充要条件是
m
∣
(
x
−
y
)
6.x\equiv y(mod\, m)的充要条件是m|(x-y)
6.x≡y(modm)的充要条件是m∣(x−y)
1-3认识不定方程
认识不定方程之前，我们先明确一个点，数论中的方程，永远是在整数域中进行的，所以说我们这里的不定方程，也是在整数域中进行的（有的博文中将不定方程叫做丢番图方程，实际上丢番图方程的解可以不在整数域，丢番图方程也可以没有解，但不定方程至少要有2个整数解，且整数解必须在整数域中）。
不定方程，一般涉及多个未知数，解永远是在整数域中，且一般有多个解。这里给出二元不定方程的一般形式：
a
x
+
b
y
=
c
(
a
,
b
,
c
为常数
)
ax+by=c(a,b,c为常数)
ax+by=c(a,b,c为常数)我们学习同余，一般来说，只用考虑解二元不定方程就可以了
1-4斐蜀定理与求解不定方程
书接上回，我们如何来解不定方程呢？艾蒂安.斐蜀提出了斐蜀定理:
对于
a
x
+
b
y
=
c
，方程有解当且仅当
c
是
g
c
d
(
a
,
b
)
的倍数，且一定有一组
(
x
0
,
y
0
)
，使得
a
x
0
+
b
y
0
=
g
c
d
(
a
,
b
)
，
对于ax+by=c，方程有解当且仅当c是gcd(a,b)的倍数，且一定有一组(x_0,y_0)，使得ax_0+by_0=gcd(a,b)，
对于ax+by=c，方程有解当且仅当c是gcd(a,b)的倍数，且一定有一组(x0,y0)，使得ax0+by0=gcd(a,b)，
所以说我们一般会求出gcd(a,b),将d赋成gcd(a,b),然后求解
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
ax+by=gcd(a,b)的解，将解乘以
d
g
c
d
(
a
,
b
)
\frac{d}{gcd(a,b)}
gcd(a,b)d就是原方程的解。 同时，我们发现可以通过斐蜀定理来缩小c的大小以来减小问题规模，存在一定的递归性质，但是
(
x
,
y
)
(x,y)
(x,y)与
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0)之间又有什么关系呢？又该如何求出
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
ax+by=gcd(a,b)的解呢？
这里提出一种算法——扩展欧几里得算法(exgcd),它就是专门用来求解不定方程的。还不会普通欧几里得算法（又叫辗转相除法）的可以看笔者的这篇博文，我们来直接看一下扩展欧几里得算法是如何实现的：
A.首先，我们来看，对于ax+by=z，当b=0时，a，b的最大公约数就是a。而这个方程的解是
x
=
d
a
x=\frac{d}{a}
x=ad,y是任意整数。
B.其次我们假设bx+(a mod b)y=d的一组解为
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0).
现在，我们就需要考虑
(
x
,
y
)
(x,y)
(x,y)与
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0)之间有什么关系了。以此来建立递归关系。如下：
1.对于
b
x
0
+
(
a
m
o
d
b
)
y
0
=
d
bx_0+(a\,mod\,b)y_0=d
bx0+(amodb)y0=d,将
(
a
m
o
d
b
)
(a\,mod\,b)
(amodb)可以表示为
a
−
⌊
a
b
⌋
×
b
a-\lfloor \frac{a}{b}\rfloor\times b
a−⌊ba⌋×b。，则有：
b
x
0
+
(
a
−
⌊
a
b
⌋
×
b
)
×
y
0
=
d
bx_0+(a-\lfloor \frac{a}{b}\rfloor\times b)\times y_0=d
bx0+(a−⌊ba⌋×b)×y0=d 2.整理，得：
b
x
0
+
a
y
0
+
⌊
a
b
⌋
×
b
×
y
0
=
d
bx_0+ay_0+\lfloor\frac{a}{b}\rfloor\times b\times y_0=d
bx0+ay0+⌊ba⌋×b×y0=d 3.将
b
x
0
−
⌊
a
b
⌋
×
b
×
y
0
bx_0-\lfloor\frac{a}{b}\rfloor\times b\times y_0
bx0−⌊ba⌋×b×y0中的b提出，得
b
(
x
0
−
⌊
a
b
⌋
×
y
0
)
b(x_0-\lfloor\frac{a}{b}\rfloor\times y_0)
b(x0−⌊ba⌋×y0),则有：
a
y
0
+
b
(
x
0
−
⌊
a
b
⌋
×
y
0
)
=
d
ay_0+b(x_0-\lfloor\frac{a}{b}\rfloor\times y_0)=d
ay0+b(x0−⌊ba⌋×y0)=d 4.与原式比较，发现上式中的
y
0
y_0
y0等于原式中的
x
x
x,上式中的
(
x
0
−
⌊
a
b
⌋
×
y
0
)
(x_0-\lfloor\frac{a}{b}\rfloor\times y_0)
(x0−⌊ba⌋×y0)等于原式中的
y
y
y。那么我们推出递归式为
(
x
,
y
)
=
(
y
0
,
x
0
−
⌊
a
b
⌋
×
y
0
)
(x,y)=(y_0,x_0-\lfloor\frac{a}{b}\rfloor\times y_0)
(x,y)=(y0,x0−⌊ba⌋×y0)，而递归边界就是上述的A，B两条。
那么我们就可以得出扩展欧几里得算法的代码(c++版)：
void exgcd(int a,int b,int &x,int &y,int &d) {
if(!b){
x=1;
y=0;
d=a;
return ;
}else{
exgcd(b,a%b,y,x,d);
y-=(a/b)*x;
}
}
或者：
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 ret=exgcd(b,a%b,y,x);
y-=a/b*x;
return ret;
}
1-5乘法逆元
在正常运算中，我们有以下式子：
3
×
x
=
1
3\times x=1
3×x=1我们可以很轻易的求出
x
=
1
3
x=\frac{1}{3}
x=31； 我们现在给这个式子加上一个有关于模的条件:
(
3
×
x
)
m
o
d
m
=
1
(3\times x)\,mod\,m=1
(3×x)modm=1这个时候x就不止有一个解了，可以证明出x有无限个解。而上述的式子可以被我们写为同余式：
3
×
x
≡
1
(
m
o
d
m
)
3\times x\equiv 1(mod\,m)
3×x≡1(modm)
也就是说，在实数意义下，我们可以找到一个数x，使得
a
×
x
=
1
(
a
≠
0
)
a\times x=1(a\neq0)
a×x=1(a=0),在模的意义下，我们可以找到无数个x，使得
a
×
x
≡
1
(
m
o
d
m
)
a\times x\equiv 1(mod\, m)
a×x≡1(modm).我们则称x为a在模m意义下的乘法逆元，记作
a
−
1
(
m
o
d
m
)
a^{-1}(mod\,m)
a−1(modm)。
比如说
(
3
×
7
)
m
o
d
10
=
1
(3\times7)\,mod\,10=1
(3×7)mod10=1即
3
×
7
≡
1
(
m
o
d
10
)
3\times 7\equiv1(mod\,10)
3×7≡1(mod10)，我们就说7是3在模10意义下的乘法逆元。
了解了乘法逆元的定义，我们再来看一下怎么求乘法逆元。 一般来说，求乘法逆元有两种办法：
1.扩展欧几里得算法 对于
a
×
x
≡
1
(
m
o
d
m
)
a\times x\equiv 1(mod\,m)
a×x≡1(modm),我们发现一定存在一个整数y，使得
a
x
+
m
y
=
1
ax+my=1
ax+my=1,这不就是一个不定方程的一般形式嘛，我们直接用扩展欧几里得算法求解（还不了解扩展欧几里得的可以先阅读1-4斐蜀定理与求解不定方程）。如下：
int gettheinv(int a,int m){
int x,y;
exgcd(a,x,m,y,1);//具体代码见1-4
return x;
}
2.费马小定理（仅适用于m是质数的情况） 费马小定理的证明较为复杂，且要涉及欧拉函数，这里直接给出费马小定理：
若
m
是一个质数，且
a
不是
m
的倍数，则
a
m
−
1
≡
1
(
m
o
d
p
)
若m是一个质数，且a不是m的倍数，则a^{m-1}\equiv 1(mod\,p)
若m是一个质数，且a不是m的倍数，则am−1≡1(modp)那么对于m是质数的情况，就有
a
×
a
m
−
2
≡
1
(
m
o
d
m
)
a\times a^{m-2}\equiv 1(mod\,m)
a×am−2≡1(modm)显而易见的,
a
m
−
2
a^{m-2}
am−2就是a在模m意义下的乘法逆元，则有代码如下：
int gettheinv(int a,int m){
return qpow(a,m-2,m);//使用了快速幂
}
2同余方程与中国剩余定理CRT
2-1认识同余方程
我们接触过形形色色的方程，同余方程，其实就是将几个含有同一未知数的同余式联合起来，模数两两不同，例如：有x个人入住宾馆，每3个人一间房，则会多出2个人，每4个人一间房，则会多出3个人，每5个人一间房，则会多出1个人，求这些人可能的人数中最小的人数为多少？
为什么要说“可能的人数中最小的人数”呢？因为同余方程在有解的前提下一定有无数个解，我们可以证明出对于同余方程一个解
x
x
x,一定存在两个整数
a
,
b
a,b
a,b，使得x=a+b且
a
+
k
×
b
（
k
为常数）
a+k\times b（k为常数）
a+k×b（k为常数）也一定为同余方程的一个解。在这里读者可能还不好理解，我们接着往下看。
对于以上问题，我们可以列方程为：
{
x
≡
2
(
m
o
d
3
)
x
≡
3
(
m
o
d
4
)
x
≡
1
(
m
o
d
5
)
\begin{cases} x\equiv 2(mod\,3)\\ x\equiv 3(mod\,4)\\ x\equiv 1(mod\,5)\\ \end{cases}\\
⎩
⎨
⎧x≡2(mod3)x≡3(mod4)x≡1(mod5) 我们回顾一下1-2同余的性质中所讲的第3，4，5条性质，发现同余式具有同加性，同乘性，同幂性。那么对于上述同余方程中的三个同余式，每一个同余式都有一个包含无限个数的解集，而同余方程的解，也就是这三个解集中的交集。所以说对于有解的同余方程，他的解有无数个。
2-2中国剩余定理
然后我们就可以考虑怎么去解这个方程，我们自然而然就可以想到暴力枚举每一种可能，这个时候我们就要提出一个新的定理了——中国剩余定理（又称孙子定理），他就是专门来求解同余方程的，我们先假设有一组同余方程如下：
{
x
≡
a
1
(
m
o
d
m
1
)
x
≡
a
2
(
m
o
d
m
2
)
x
≡
a
3
(
m
o
d
m
3
)
(
现实中可能不仅有三组，还有更多
)
\begin{cases} x\equiv a_1(mod\,m_1)\\ x\equiv a_2(mod\,m_2)\\ x\equiv a_3(mod\,m_3)\\ \end{cases}\\ (现实中可能不仅有三组，还有更多)
⎩
⎨
⎧x≡a1(modm1)x≡a2(modm2)x≡a3(modm3)(现实中可能不仅有三组，还有更多)
不过，中国剩余定理是有局限性的，它只能处理模数(即
m
1
,
m
2
,
m
3
.
.
.
m
n
m_1,m_2,m_3...m_n
m1,m2,m3...mn)两两互质的情况，对于模数两两不互质的情况，可以用扩展中国剩余定理来解，有兴趣的读者可以学习完本博客后上网自行查阅，接下来，我们来看一下中国剩余定理是如何来解同余方程的： 1.求出
m
1
,
m
2
,
m
3
.
.
.
m
n
的积（也就是最小公倍数）为
M
，即
m_1,m_2,m_3...m_n的积（也就是最小公倍数）为M，即
m1,m2,m3...mn的积（也就是最小公倍数）为M，即
M
=
∏
i
=
1
n
m
i
M=\prod_{i=1}^{n} m_i
M=∏i=1nmi
M
=
3
×
4
×
5
=
60
M=3\times 4\times 5=60
M=3×4×5=60 2，设
v
i
(
i
∈
[
1
,
n
]
)
=
M
m
i
v_i(i\in[1,n])=\frac{M}{m_i}
vi(i∈[1,n])=miM
{
v
1
=
60
3
=
20
v
2
=
60
4
=
15
v
3
=
60
5
=
12
\begin{cases} v_1=\frac{60}{3}=20\\ v_2=\frac{60}{4}=15\\ v_3=\frac{60}{5}=12\ \end{cases}\\
⎩
⎨
⎧v1=360=20v2=460=15v3=560=12
仔细观察上述式子，我们发现，因为M是所有
m
i
m_i
mi的最小公倍数且
m
i
m_i
mi互质，那么我们用M除以每一个
m
i
m_i
mi求得的
v
i
v_i
vi，由整数唯一分解定理得
v
i
v_i
vi不能被
m
i
m_i
mi整除，却可以被其他任意一个
m
m
m整除，例如20不能被3整除，却可以被4，5整除，15不能被4整除，却可以被3，5整除。请读者记住这一步的目的 3.设
v
i
v_i
vi模
m
i
m_i
mi的乘法逆元为
t
i
t_i
ti.
{
t
i
=
2
,
20
×
1
≡
1
(
m
o
d
3
)
t
i
=
3
,
15
×
1
≡
1
(
m
o
d
4
)
t
i
=
3
,
12
×
3
≡
1
(
m
o
d
5
)
\begin{cases} t_i=2,20\times 1\equiv 1(mod\,3)\\ t_i=3,15\times 1\equiv 1(mod\,4)\\ t_i=3,12\times 3\equiv 1(mod\,5)\\ \end{cases}\\
⎩
⎨
⎧ti=2,20×1≡1(mod3)ti=3,15×1≡1(mod4)ti=3,12×3≡1(mod5) 则有
x
=
(
a
1
×
v
1
×
t
1
+
a
2
×
v
2
×
t
2
+
a
3
×
v
3
×
t
3
+
.
.
.
+
a
n
×
v
n
×
t
n
)
−
M
×
k
(
k
∈
N
+
)
x=(a_1\times v_1\times t_1+a_2\times v_2\times t_2+a_3\times v_3\times t_3+...+a_n\times v_n\times t_n)-M\times k(k\in N+)
x=(a1×v1×t1+a2×v2×t2+a3×v3×t3+...+an×vn×tn)−M×k(k∈N+)
这一步的原理是： 已知
v
i
×
t
i
≡
i
(
m
o
d
m
i
)
v_i\times t_i \equiv i(mod\,m_i)
vi×ti≡i(modmi) 给上述同余式两边同时乘以
a
i
a_i
ai，得：
a
i
×
v
i
×
t
i
≡
a
i
(
m
o
d
m
i
)
a_i\times v_i\times t_i\equiv a_i(mod\,m_i)
ai×vi×ti≡ai(modmi)
所以说
a
i
×
v
i
×
t
i
a_i\times v_i\times t_i
ai×vi×ti就是满足同余方程中第
i
i
i个同余式的一个解，而为什么把它们（分别满足各个同余式的解）加起来就一定是满足所有同余式的解呢？
这里不加证明的，给出一个定理：
几个数相加，如果只存在一个加数不能被数a整除，那么它们的和就不能被整数a整除，且和与加数模a同余
这个定理的证明可以通过数学归纳法和欧几里得算法得出。
那么对于每一组
a
i
×
v
i
×
t
i
a_i\times v_i\times t_i
ai×vi×ti他都不能被
m
i
m_i
mi整除，但却可以被其他的
m
m
m整除（因为
v
i
v_i
vi可以被其他的
m
m
m整除），所以说每一组
a
i
×
v
i
×
t
i
a_i\times v_i\times t_i
ai×vi×ti相加就满足上述定理，所以说相加起来的和就满足所有的同余式，它的和就是一组答案。
对于以上例子则有:
x
=
(
2
×
20
×
2
+
3
×
15
×
3
+
1
×
12
×
3
)
−
60
×
k
x=(2\times20\times2+3\times15\times3+1\times12\times3)-60\times k
x=(2×20×2+3×15×3+1×12×3)−60×k 例题： 洛谷P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪（仅作引用，侵权立删）
//CRT
/*
ans=_b_1(mod a_1)
ans=_b_2(mod a_2)
......
ans=_b_n(mod a_n)
*/
#include
using namespace std;
int n;
long long mo[15],b[15];
long long mm=1,M,m[15],t[15];
long long ans;
long long y;
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=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>mo[i]>>b[i];
mm*=mo[i];
}
for(int i=1;i<=n;i++){
m[i]=mm/mo[i];
exgcd(m[i],mo[i],t[i],y);
t[i]=(mo[i]+t[i]%mo[i])%mo[i];
for(int j=1;j<=b[i];j++){
ans=(ans+m[i]*t[i])%mm;
}
}
cout< return 0; } 练习：洛谷P3868，洛谷P1516