是方程的一个特解，那么所有的解可以表示为 其中n是整数。
证明 由定理2.1 可知，线性同余方程ax?b(modm)等价于二元线性丢番图
[1]
x?x0?(m)ty?y0?(a)nd ，d
方程ax?my?b。整数x是同余方程（2-1）的解，当且仅当存在y使得
ax?my?b。
根据定理2.13可知，如果d不整除b，则无解。而当d整除b时，有无穷多解：
x?x0?(m)ty?y0?(a)td， d
ax-my?b，
x0?(m)tx?x0,y?y0d且是线性同余方程的其中，是方程的特解。上述x的值是
解，有无穷多这样的解。
为了确定有多少不同余的解，我们先找出两个解，设这两个解分别为
x1?x0?(m)t1x2?x0?(m)t2d和d，再找出这两个解模m同余的条件。
x0?(m)t1?x0?(m)t2(modm)x0dd首先，若这两个解同余，那么，两边减去，有 (m)t1?(m)t2(modm)dd
m(m,m)?mdd。再由定理2.4我们可以知道t1?t2(modd) 因为d整除m，所以
x?x0?(m)td得到，其中t取遍这表明，不同余的解的一个完全集合可以通过取
x?x0?(m)td给出，其中模d的完全剩余系。一个这样的集合可以由t?0,1,2,...d?,。
同时，我们还可以得到，乘数a和模m互素的线性同余方程有唯一解。这是因为当a和m互素时，那么（a,m）整除b,由上述结论即定理2.12可知，线性同余方程ax?b(modm)恰有(a,m)?1个模m不同余的解。 2.3 中国剩余定理
在本节中，我们讨论联立的同余方程组。本节将会研究两种类型的方程组：第一种类型有两个或更多具有不同模的一元线性同余方程组；第二种类型的同余
6
方程变元数多于一，且方程数多于一，但是方程的模相同。
首先，我们考虑仅有一个未知数但有不同模的同余方程组，我们先给出关于一元线性同余方程组的解的主要定理：中国剩余定理。
定理2.14（中国剩余定理） 设有r个两两互素的正整数m1,m2,...,mr。那么同余方程组
x?a1(modm1)
x?a2(modm2) . . 有模
M?m1m2...mrx?ar(momdr
)的唯一解。
那么，中国剩余定理是如何解决关于一元线性同余方程组的解的问题，我们首先通过阐述古代的中国难题来说明中国剩余定理的主要用途。
在公元3世纪晚期的《孙子算经》中，有这样一个问题：求一个数，它能被3除余1，被5除余2，被7除余3。我们可以列出下面的同余方程组
x?1(mod3)x?2(mod5) x?3(mod 7)根据中国剩余定理，我们有
M?3?5?7?105， M1?105/3?35，M2?105/5?21，M3?105/7?15,，为确定
y1,我们需要解同余方程
35y1?1(mod3)或者与其等价的，立即得到
2y1?1(mod3)。得到
y1?2(mod3)。解同余方程
21y2?1(mod5)y2?1(mod5)。最后，解
15y3?1(mod7)y3?1(mod7)得。因此，
?1?3?15?1?15?7 x?1?35?2?2?2152 (m可以验证，满足x?52(mod105)的x是同余方程组的解，这只需注意到
52?1(mod3)，52?2(mod5)，52?3(mod7)。
7
abr2?12?12?1。其模的最小正剩余是 引理2.1 如果a和b是正整数，则
中，r是a模b的最小正剩余。
同时，中国剩余定理提供了实施大整数的计算机算术运算的方法。存储很大的整数并做它们之间的算术运算需要特殊的技巧。中国剩余定理告诉我们给定两个互素的模m1,m2,...,mr，一个小于M?m1m2...mr的正整数n由它的模mj最小正剩余唯一确定，其中
j?1,2,...r假设一个计算机的字长仅为100，但是我们想做
大小为106的整数的算术运算。首先，找到小于100的两两互素的正整数，是它
m1?99，m2?98，m3?97m?956
们的积超过10；例如，可以取和4。我们将小于 106的整数转换为4元组，每个分量分别是它模 m1，m2， m3，m4的最小正剩余。然后，例如做整数的加法，我们仅仅需要把他们模m1，m2，m3，m4的最小正剩余相加，这利用到之前得出的结论：
x?y?xi?yi(modmi)x?xi(modmi)，
y?yi(modmi)则
。然后利用中国剩余定理将所得的四个最小正剩余的和的
集合转换为一个整数。 2.4 求解多项式同余方程
a1a2akm?pp...p12k， 若m有素因子分解则求解形如f(x)?0(modm)等价于求解aiaif(x)?0(modp)pi?1,2,...,ki同余方程组， 。一旦解出k个模的同余方程，
就可以利用中国剩余定理求出模m的解。
4例 因为80?2?5，所以求解同余方程
32x?7x?4?0(mod 80)
化为求解
32x?7x?4?0(mod 16)
和
32x?7x?4?0(mod5)。
模16的解释整数x?12(mod16)。（因为若x为解，则必为偶数;容易验证x是奇数的情形不是解）。模5的解释整数x?1(mod5)，我们利用中国剩余定理求
8
x?12(mod16)和x?1(mod5)的联立解，通过运算我们得到x?76(mod80)。这就
32x?7x?4?0(mod80)的解。 是
我们知道，一旦知道了多项式模p同余方程的所有解，就有相对简单的方法
kp来解多项式的模同余方程。
我们会知道，模P的解可以用来求模p的解，模p的解可以用来求模p的解，
2p等等。我们先举例说明从模P的解可以用来求模的解的基本思路。
223例 通过对x?0,1,2,3和4直接验证，可见
32x?7x?4?0(mo d5)
的解是x?1(mod5)。如何求模25的解？我们可以从0到24这25个值依次验证。我们有更加系统给的方法。因为
32x?7x?4?0(mod 25)
的每一个解都是模5的解，而且每个模5的解都满足x?1(mod5)，那么x?1?5t，t是整数。用1?5t代替x可以求出t的值，继而我们得到
?t53?) 2(17?(1t?5?)40(m od25)将其化简得到t的线性同余方程65t?5?15t?5?0(mod25)消去因子5，得到 3t?1?0(mod 5解为t?3(mod5)这表明模25的解是x?1?5t?1?5?3?16(mod25)，我们可以验证出这的确是解。 2.5 线性同余方程组
线性同余方程组即未知数个数与方程个数是同一大于1的整数，并且所有方程的模都相同。
例 线性同余方程组
4x?3y?9(mod13 5x?2y?7(mod的所有整数x和y。尝试求x和y，将第13)一个方程乘以2，第二个方程乘以3, 我们得到
9
8x?6y?18(mod13 15x?6y?21(mod 13)再用第二个方程减去第一个方程，得到 7x?3(mod13
因为2是7的模13逆，所以我们将上面的同余方程两边同时乘以2，得到 2?7x?2?3(mod 1即
x?6(mod1 3同样的，我们将（原来的）第一个方程乘以5，将第二个方程乘以4，我们又会得到如下方程组
20x?1y5?45(mod1 20x?8y?28(mod 13)用第一个方程减去第二个方程，得到
7y?17(mod 13
为求y，上面的同余方程两边同时乘以2，这里7模13的一个逆，得 2?7y?2?17(mod 1所以
y?8(mod1 3这就证明了，任何解（x,y）都满足
x?6(mod13)，y?8(mod13)
将以上求得的关于x和y这两个同余方程代入到原来的同余方程组，可以得知他们确实是解：
4x?3y?4??6?3?8?48 5x?2y?5??6?2?8?469(mod7(m od13)因此，我们得到 同余方程组的解释使得
x?6(mod13y?8(mod13)的所有整数对（x,y），。
我们给出一个关于含有两个二元方程的同余方程组的一般结论。
10