初等数论第五章同余方程.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)的全部解是，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 n。第四节 素数模的同余方程在上节中，我们证明了，对于素数p，模pa的同余方程的求解可以转化为模p的同余方程的求解。本节要对素数模的同余方程做些初步研究。以下，设f(x) = anxn + L + a1x + a0是整系数多项式，p是素数，pan。定理1 设k n，若同余方程f(x) = anxn + L + a1x + a0 0 (mod p) (1)有k个不同的解x1, x1, L, xk，则对于任意的整数x，有f(x) (x - x1) (x - x2)L(x - xk)fk(x) (mod p)，其中fk(x)是一个次数为n - k的整系数多项式，并且它的xn - k项的系数是an。证明 由多项式除法，有f(x) = (x - x1)f1(x) + r1， (2)其中f1(x)是首项系数为an的n - 1次整系数多项式，r1是常数。在式(2)两边令x = x1，则由假设条件可知f(x1) = r1 0 (mod p)，因此，式(2)成为f(x) (x - x1)f1(x) (mod p)。 (3)因此，当k = 1时，定理成立。如果k 1，在上式中，令x = xi（i = 2, 3, L, k），则有0 f(xi) (xi - x1)f1(xi) (mod p)。 (4)由于x2, L, xk对于模p是两两不同余的，所以，上式给出f1(xi) 0 (mod p)，i = 2, L, k。 (5)由此及归纳法，即可证明定理。证毕。推论 若p是素数，则对于任何整数x，有x p - 1 - 1 (x - 1)(x - 2)L(x - p + 1) (mod p)。证明 由Fermat定理（第二章第四节定理2），数1, 2, L, p - 1是同余方程x p - 1 1 (mod p)的解，因此，利用定理1即可得证。定理2 同余方程(1)的解数 n。证明 假设同余方程(1)有n + 1个不同的解x xi (mod p)，1 i n + 1。由定理1，有f(x) an(x - x1)L(x - xn) (mod p)，因此0 f(xn + 1) an(xn + 1 - x1)L(xn + 1 - xn) (mod p)。 (6)由于pan，xn + 1xi (mod p)，1 i n，所以式(6)不能成立。这个矛盾说明同余方程(1)不能有n + 1个解。证毕。推论 若同余方程bnxn + L + b0 0 (mod p)的解数大于n，则pbi，0 i n。 （7)证明 若式(7)不成立，设pbd，d n，pbi， d j n。则bnxn + L + b0 bdxd + L + b0 0 (mod p)。 (8)由定理2，同余方程(8)的解数不大于d，因而不大于n，这与假设矛盾。因此，式(7)必成立。证毕。定理3 同余方程(1)或者有p个解，或者存在次数不超过p - 1的整系数多项式r(x)，使得同余方程(1)与r(x) 0 (mod p)等价。证明 由多项式除法可知，存在整系数多项式g(x)与r(x)，使得f(x) = g(x)(x p - x) + r(x)。 (9)由Fermat定理，对于任意的整数x，有x p x (mod p)，因此，如果r(x)的系数都是p的倍数，则对于任意的整数x，f(x) 0 (mod p)，即同余方程(1)有p个解。如果r(x)的系数不都是p的倍数，则r(x)的次数不超过p - 1。由式(9)看出，对于任意的整数x，f(x) r(x) (mod p)，即同余方程(1)与r(x) 0 (mod p)等价。证毕。定理4 设n p，则同余方程f(x) = xn + an - 1xn - 1 + L + a1x + a0 0 (mod p) (10)有n个解的充要条件是存在整数多项式q(x)和r(x)，r(x)的次数 n，使得x p - x = f(x)q(x) + pr(x)。 (11)证明 必要性 由多项式除法，存在整系数多项式q(x)与r1(x)，r1(x)的次数 2，(a, p) = 1的情形。此时，因为(4a, p) = 1，所以，方程(1)等价于方程4a2x2 + 4abx + 4ac 0 (mod p)，即(2ax + b)2 b2 - 4ac (mod p)。这样，研究方程(1)归结为对方程x2 n (mod p) (2)的研究。定义 给定整数p，对于任意的整数n，(n，p) = 1，若方程(2)有解，则称n是模p的二次剩余，记为nQR(p)；否则，称n是模p的二次非剩余，记为nQNR(p)。显然，若n1 n2 (mod p)，则它们同是模p的二次剩余（或二次非剩余），因此，在谈到模p的二次剩余（或二次非剩余）时，把n1和n2看作是同一个。以下，在本节中，总假定p是奇素数。定理 若(n, p) = 1，则() n是模p的二次剩余的充要条件是 1 (mod p)； (3)() 若n是模p的二次剩余，则方程(2)有两个解；() n是模p的二次非剩余的充要条件是 -1 (mod p)。 (4)证明 结论()与()由第四节定理直接推出。() 若(n, p) = 1，由第二章第四节定理，有np - 1 1 (mod p)， 0 (mod p)。 (5)因为p是奇素数，所以式(3)式与式(4)必有且仅有一个成立，利用结论()，可得到结论()。证毕。定理 模p的简化系中，二次剩余与二次非剩余的个数都是，而且，模p的每个二次剩余与且仅与数列12，22，L， (6)中的一个数同余。证明 显然，数列(6)包含了模p的全部二次剩余。为了证明定理，只需证明式(6)中的任何两个数对模p不同余。对任意的整数k，s，1 k s ，若k2 s2 (mod p)， (7)则pk + s或pk - s。这都是不可能的，所以式(7)不能成立。证毕。定义 给定奇素数p，对于整数n，定义Legendre符号为例如，由定理1，1与4是模5的二次剩余，2与3是模5的二次非剩余，于是，定理3 设p是奇素数，n是整数，则() (mod p)；() 若n n1 (mod p)，则；() ；() 对任意的整数ni，1 i k，有。证明 结论()与()容易由定义2及定理1得到。为了证明结论()，只需证明其中的第二个等式。由结论()，有(mod p)，其中同余式两端都只能取值 +1或 -1，因此，结论()的第二个等式成立。最后，由结论()，有由于上式首端与末端都是只取值 -1，0或1的整数，所以它们必相等。结论()得证。证毕。推论 设p是奇素数，则 -1QR(p)的充要条件是p 1(mod 4)；-1QNR(p)的充要条件是p 3(mod 4)。例1 判断方程x2 5 (mod 11)有没有解。解 由定理2，因为 (mod 11)，方程有解。例2 设p是奇素数，p 1 (mod 4)，则 -1 (mod p)解 由Wilson定理（第二章第二节例3），有定理2和例2说明，当素数p 1(mod 4)时，模p的所有二次剩余之积对模p同余于 -1。此外，我们还得到了方程的解。例3 设n是整数，证明n2 + 1的任何奇因数都是4m + 1（mZ）的形式。解 由于任何奇数都可表成奇素数之积，而且任意多个形如4m + 1的整数之积也具有4m + 1的形式，我们只需证明：若素数p是n2 + 1的因数，则p具有4m + 1的形式。事实上，若pn2 + 1，则n2 -1 (mod p)，即-1QR(p)。由定理3推论得出所需结论。例 形如4m + 1（kZ）的素数有无穷多个。解 用反证法。假设只有有限多个形如4k + 1的素数p1, p2, L, pk，记N = 4(p1p2Lpk)2 + 1。由例2，必有奇素数q，q 1 (mod 4)，qN，显然q pi（1 i k），这与假设矛盾，所以形如4m + 1的素数有无穷多个。例 若a 1 (mod 4)，2b，并且b没有形如4k + 3（kZ）的素因数，证明方程y2 = x3 - a3 - b2 (8)没有整数解。解 用反证法。假设有整数x，y满足方程(8)。若2x，则由式(8)得则y2 -1(mod 4)这不可能。若x 3 (mod 4)，则由式(8)得到y2 x3 - a3 - b2 33 - 13 - 0 2 (mod 4)，这是不可能的。若x 1 (mod 4)，则x2 + ax + a2 1 + a + a2 3 (mod 4)， (9)因此，必有素数p 3 (mod 4)，使得px2 + ax + a2 。 (10)由式(8)与式(10)得到y2 = x3 - a3 - b2 -b2 (mod p)， (11)即 -b2 QR(p)。但是，由假设，pb2，所以有，这与式(11)矛盾。例 设p是素数，证明：数例1, 2, L, p - 1中的模p的二次剩余之和是。解 对于整数k，1 k ，记k2 = pqk + rk，qkZ，1 rk p - 1，则qk =，并且，由定理2，有例 设p是奇素数，证明：若同余方程x4 + 1 0 (mod p) (12)有解，则p 1 (mod 8)。解 设x a (mod p)是方程(12)的解，则a4 -1 (mod p)， (13)a8 1 (mod p)。 (14)以d0表示使ad 1 (mod p) (15)成立的最小正整数d，记8 = qd0 + r，0 r d0 - 1，则由式(14)与式(15)得到1 a8 = ar (mod p)，因此，若r 0，则上式与d0的定义矛盾。所以r = 0，即d08，这样，d0的取值只可能是1，2，4或8。由式(13)可知d0 = 8。用同样方法以及Fermat定理可以证明8p - 1即p 1 (mod 8)。习 题 五1. 同余方程x2 3 (mod 13)有多少个解？2. 求出模23的所有的二次剩余和二次非剩余。3. 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。4. 设素数 p 3 (mod 4)，= 1，证明x (mod p)是同余方程x2 n (mod p)的解。5. 设p是奇素数，(n, p) = 1，a是正整数，证明同余方程x2 n (mod pa)有解的充要条件是= 1。6. 设p是奇素数，证明：模p的所有二次剩余的乘积与对模p同余