(完整word版)初等数论-第五章--同余方程.doc

第五章 同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法第一节 同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程在本章中，总假定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)的全部解是，tÎZ (4)由式(4)所确定的x都满足方程(2)记d = (a, m)，以及t = dq + r，qÎZ，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，使得a½b + 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 < 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)的解是x º= 114 (mod 161)例3 设a > 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 º -7×3 º 2 (mod 23) Û 3x º -2×4 º -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. 证明定理12. 解同余方程：(ⅰ) 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) = d½b若有解，则恰有d×mn -1个解，mod m6. 解同余方程：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 ，其中m1, m2, L, mk 是两两互素的正整数，f(x)是整系数多项式，以T与Ti（1 £ i。