. . . .第五章 同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。第一节 同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。在本章中，总假定m是正整数。定义1 设f(x) = anxn + L + a1x + a0是整系数多项式，称f(x) 0 (mod m) (1)是关于未知数x的模m的同余方程，简称为模m的同余方程。若an0 (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)的解。证明 留做习题。下面，我们来研究一次同余方程的解。定理2 设a，b是整数，a0 (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)的全部解是，tZ。 (4)由式(4)所确定的x都满足方程(2)。记d = (a, m)，以及t = dq + r，qZ，r = 0, 1, 2, L, d - 1，则x = x0 + qm +(mod m)，0 r d - 1。容易验证，当r = 0, 1, 2, L, d - 1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。例1 设(a, m) = 1，又设存在整数y，使得ab + ym，则x (mod m)是方程(2)的解。解 直接验算，有ax b + ym b (mod m)。注：例1说明，求方程(2)的解可以转化为求方程my -b (mod a) (5)的解，这有两个便利之处：第一，将一个对于大模m的同余方程转化为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设m r (mod a)，r 0，且(a, m) = 1，a1是m对模a的最小非负剩余，则同余方程a1x -b(mod m) (7)等价于同余方程(2)。解 设x是(2)的解，则由m =+ a1得到(mod m)，即x是同余方程(7)的解。但是由假设条件可知同余方程(2)与(7)都有且只有一个解。所以这两个同余方程等价。注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。例4 解同余方程6x 7 (mod 23)。解 由例3，依次得到6x 7 (mod 23) 5x -73 2 (mod 23) 3x -24 -8 (mod 23) 2x -8(-7) 10 (mod 23) x 5 (mod 23)。例5 设(a, m) = 1，并且有整数d 0使得a d 1 (mod m)，则同余方程(2)的解是x ba d - 1 (mod m)。解 直接验证即可。注：由例5及Euler定理可知，若(a, m) = 1，则x baj(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 解同余方程组。 (8)解 将(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是正整数，证明：同余方程组 (9)有解的充要条件是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. 解同余方程组：。4. 设p是素数，0 a p，证明：(mod p)。是同余方程ax b (mod p)的解。5. 证明：同余方程a1x1 + a2x2 + L + anxn b (mod m)有解的充要条件是(a1, a2, L, an, m) = db。若有解，则恰有dmn -1个解，mod m。6. 解同余方程：2x + 7y 5 (mod 12)。第二节 孙子定理本节要讨论同余方程组 。 (1)在第一节的例题中，我们已讨论了k = 2的情形。下面考察一般情形。定理1(孙子定理) 设m1, m2, L, mk是正整数，(mi, mj) = 1，1 i, j k，i j。 (2)记m = m1m2Lmk ，Mi =，1 i k，则存在整数Mi（1 i k），使得MiMi 1 (mod mi)， (3)MiMi 0 (mod mi)，1 j k，i j， (4)并且(mod m) (5)是同余方程组(1)对模m的唯一解，即若有x使方程组(1)成立，则x x0 (mod m)。 (6)证明 由式(2)，有(Mi, mi) = 1，因此利用辗转相除法可以求出Mi与yi ，使得MiMi + yimi = 1，即Mi满足式(3)和式(4)。由式(3)与式(4)，对于1 i k，有x0 aiMiMi ai (mod mi)，1 i k。若x也使式(1)成立，则x x0 (mod mi)，1 i k，因此x x0 (mod m1, m2, L, mk)。但是，由式(2)可知m1, m2, L, mk = m，这就证明了式(6)。证毕。定理2 在定理1的条件下，若式(1)中的a1, a2, L, ak分别通过模m1, m2, L, mk的完全剩余系，则式(5)中的x0通过模m1m2Lmk的完全剩余系。证明 这是第二章第二节习题6的特例。证毕。定理3 同余方程组(1)有解的充要条件是ai aj (mod (mi, mj)，1 i, j n。 (7)证明 必要性是显然的。下面证明充分性。当n = 2时，由第一节例8可知充分性成立。假设充分性当n = k时成立。假设式(7)当n = k + 1时成立。我们来考虑同余方程组x ai (mod mi)，1 i k + 1。由第一节例8，存在bk，使得x bk (mod mk，mk +1)满足同余方程组x ak (mod mk)，x ak + 1 (mod mk + 1)。在同余方程组中，由式(7)有ai aj (mod (mi, mj)，1 i, j k - 1，因此，若能证明ai bk (mod (mi, mk, mk +1)，1 i k - 1。 (8)则由归纳假设就可以证明充分性。由bk的定义，有ak bk (mod mk)，ak + 1 bk (mod mk + 1) (9)而且，由于假设式(7)当n = k + 1时成立，所以，对于1 i k - 1有ai ak (mod (mi, mk)，ai ak + 1 (mod (mi, mk + 1)，由此及式(9)得到，对于1 i k - 1，有ai bk (mod (mi, mk)，ai bk (mod (mi, mk + 1)。因此ai bk (mod (mi, mk), (mi, mk + 1)。由上式及第一章第六节例2，就得到式(8)。证毕。定理4 设m = m1m2Lmk ，其中