第五章 同余方程
本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节 同余方程的基本概念
本节要介绍同余方程的基本概念及一次同余方程。 在本章中，总假定m是正整数。
定义1 设f(x) = anxn ? ? ? a1x ? a0是整系数多项式，称
f(x) ? 0 (mod m) (1)
是关于未知数x的模m的同余方程，简称为模m的同余方程。 若an??0 (mod m)，则称为n次同余方程。
定义2 设x0是整数，当x = x0时式(1)成立，则称x0是同余方程(1)的解。凡对于模m同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。
由定义2，同余方程(1)的解数不超过m。 定理1 下面的结论成立：
(ⅰ) 设b(x)是整系数多项式，则同余方程(1)与
f(x) ? b(x) ? b(x) (mod m)
等价；
(ⅱ) 设b是整数，(b, m) = 1，则同余方程(1)与
bf(x) ? 0 (mod m)
等价；
(ⅲ) 设m是素数，f(x) = g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程
g(x) ? 0 (mod m) 或 h(x) ? 0 (mod m)
107
的解。
证明 留做习题。
下面，我们来研究一次同余方程的解。 定理2 设a，b是整数，a??0 (mod m)。则同余方程
ax ? b (mod m) (2)
有解的充要条件是(a, m)?b。若有解，则恰有d = (a, m)个解。 证明 显然，同余方程(2)等价于不定方程
ax ? my = b， (3)
因此，第一个结论可由第四章第一节定理1得出。
若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是
m?x?x?t0?(a,m)?，t?Z。 (4) ?a?y?y?t0?(a,m)?由式(4)所确定的x都满足方程(2)。记d = (a, m)，以及 t = dq ? r，q?Z，r = 0, 1, 2, ?, d ? 1，
则
mmx = x0 ? qm ?r?x0?r(mod m)，0 ? r ? d ? 1。
dd容易验证，当r = 0, 1, 2, ?, d ? 1时，相应的解
(d?1)mm2m x0，x0?，x0?，?，x0?ddd对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。 在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。
例1 设(a, m) = 1，又设存在整数y，使得a?b ? ym，则
b?ymx ?(mod m)
a是方程(2)的解。 解 直接验算，有
ax ? b ? ym ? b (mod m)。 108
注：例1说明，求方程(2)的解可以转化为求方程
my ? ?b (mod a) (5)
的解，这有两个便利之处：第一，将一个对于大模m的同余方程转化为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设m ? r (mod a)，r < a，则又可继续转化成一个对于更小的模r的同余方程。 例2 解同余方程
325x ? 20 (mod 161) (6)
解 同余方程(6)即是
3x ? 20 (mod 161)。
解同余方程
161y ? ?20 (mod 3)， 2y ? 1 (mod 3)，
得到y ? 2 (mod 3)，因此方程(6)的解是
20?2?161x ?= 114 (mod 161)。
3例3 设a > 0，且(a, m) = 1，a1是m对模a的最小非负剩余，则同余方程
ma1x ? ?b[](mod m) (7)
a等价于同余方程(2)。
m解 设x是(2)的解，则由m =a[]? a1得到
ammma1x?(m?a[])x??ax[]??b[](mod m)，
aaa即x是同余方程(7)的解。但是由假设条件可知同余方程(2)与(7)都有且只有一个解。所以这两个同余方程等价。
注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。
例4 解同余方程6x ? 7 (mod 23)。 解 由例3，依次得到
6x ? 7 (mod 23) ? 5x ? ?7?3 ? 2 (mod 23) ? 3x ? ?2?4 ? ?8 (mod 23)
109
? 2x ? ?8(?7) ? 10 (mod 23) ? x ? 5 (mod 23)。
例5 设(a, m) = 1，并且有整数? > 0使得
a ? ? 1 (mod m)，
则同余方程(2)的解是
x ? ba ? ? 1 (mod m)。
解 直接验证即可。
注：由例5及Euler定理可知，若(a, m) = 1，则
x ? ba?(m) ? 1 (mod m)
总是同余方程(2)的解。 例6 解同余方程
81x3 ? 24x2 ? 5x ? 23 ? 0 (mod 7)。
解 原同余方程即是
?3x3 ? 3x2 ? 2x ? 2 ? 0 (mod 7)。
用x = 0，?1，?2，?3逐个代入验证，得到它的解是
x1 ? 1，x2 ? 2，x3 ? ?2 (mod 7)。
注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。 例7 解同余方程组
?3x?5y?1(mod7)。 (8) ?2x?3y?2(mod7)? 解 将(8)的前一式乘以2后一式乘以3再相减得到 19y ? ?4 (mod 7)， 5y ? ?4 (mod 7)， y ? 2 (mod 7)。
再代入(8)的前一式得到
3x ? 10 ? 1 (mod 7)， x ? 4 (mod 7)。
即同余方程组(8)的解是x ? 4，y ? 2 (mod 7)。
例8 设a1，a2是整数，m1，m2是正整数，证明：同余方程组
?x?a1(modm1) (9) ?x?a(modm)22?110
有解的充要条件是
a1 ? a2 (mod (m1, m2))。 (10)
若有解，则对模[m1, m2]是唯一的，即若x1与x2都是同余方程组(9)的解，则
x1 ? x2 (mod [m1, m2])。 (11)
解 必要性是显然的。下面证明充分性。 若式(10)成立，由定理2，同余方程
m2y ? a1 ? a2 (mod m1)
有解y ? y0 (mod m1)，记x0 = a2 ? m2y0，则
x0 ? a2 (mod m2)
并且
x0 = a2 ? m2y0 ? a2 ? a1 ? a2 ? a1 (mod m1)，
因此x0是同余方程组的解。
若x1与x2都是方程组(9)的解，则
x1 ? x2 (mod m1)，x1 ? x2 (mod m2)，
由同余的基本性质，得到式(11)。
习 题 一
1. 证明定理1。 2. 解同余方程：
(ⅰ) 31x ? 5 (mod 17)；
(ⅱ) 3215x ? 160 (mod 235)。 3. 解同余方程组：
?3x?5y?38(mod47)。 ?x?y?10(mod47)?4. 设p是素数，0 < a < p，证明：
(p?1)(p?2)???(p?a?1)(mod p)。 x?b(?1)a?1a!是同余方程ax ? b (mod p)的解。
5. 证明：同余方程a1x1 ? a2x2 ? ? ? anxn ? b (mod m)有解的充要条件是
111