初等數(shù)論_第五章__同余方程.doc

第五章 同余方程本章主要介紹同余方程的基礎(chǔ)知識，并介紹幾類特殊的同余方程的解法。第一節(jié) 同余方程的基本概念本節(jié)要介紹同余方程的基本概念及一次同余方程。在本章中，總假定m是正整數(shù)。定義1 設(shè)f(x) = anxn + L + a1x + a0是整系數(shù)多項式，稱f(x) 0 (mod m) (1)是關(guān)于未知數(shù)x的模m的同余方程，簡稱為模m的同余方程。若an0 (mod m)，則稱為n次同余方程。定義2 設(shè)x0是整數(shù)，當x = x0時式(1)成立，則稱x0是同余方程(1)的解。凡對于模m同余的解，被視為同一個解。同余方程(1)的解數(shù)是指它的關(guān)于模m互不同余的所有解的個數(shù)，也即在模m的一個完全剩余系中的解的個數(shù)。由定義2，同余方程(1)的解數(shù)不超過m。定理1 下面的結(jié)論成立：() 設(shè)b(x)是整系數(shù)多項式，則同余方程(1)與f(x) + b(x) b(x) (mod m)等價；() 設(shè)b是整數(shù)，(b, m) = 1，則同余方程(1)與bf(x) 0 (mod m)等價；() 設(shè)m是素數(shù)，f(x) = g(x)h(x)，g(x)與h(x)都是整系數(shù)多項式，又設(shè)x0是同余方程(1)的解，則x0必是同余方程g(x) 0 (mod m) 或 h(x) 0 (mod m)的解。證明 留做習(xí)題。下面，我們來研究一次同余方程的解。定理2 設(shè)a，b是整數(shù)，a0 (mod m)。則同余方程ax b (mod m) (2)有解的充要條件是(a, m)b。若有解，則恰有d = (a, m)個解。證明 顯然，同余方程(2)等價于不定方程ax + my = b， (3)因此，第一個結(jié)論可由第四章第一節(jié)定理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時，相應(yīng)的解對于模m是兩兩不同余的，所以同余方程(2)恰有d個解。證畢。在定理的證明中，同時給出了解方程(2)的方法，但是，對于具體的方程(2)，常?？刹捎貌煌姆椒ㄈソ狻＠? 設(shè)(a, m) = 1，又設(shè)存在整數(shù)y，使得ab + ym，則x (mod m)是方程(2)的解。解 直接驗算，有ax b + ym b (mod m)。注：例1說明，求方程(2)的解可以轉(zhuǎn)化為求方程my -b (mod a) (5)的解，這有兩個便利之處：第一，將一個對于大模m的同余方程轉(zhuǎn)化為一個對于小模a的同余方程，因此有可能通過對模a的完全剩余系進行逐個驗證，以求出方程(5)和(2)的解；第二，設(shè)m r (mod a)，r 0，且(a, m) = 1，a1是m對模a的最小非負剩余，則同余方程a1x -b(mod m) (7)等價于同余方程(2)。解 設(shè)x是(2)的解，則由m =+ a1得到(mod m)，即x是同余方程(7)的解。但是由假設(shè)條件可知同余方程(2)與(7)都有且只有一個解。所以這兩個同余方程等價。注：用本例的方法，可以將同余方程(2)轉(zhuǎn)化成未知數(shù)的系數(shù)更小一些的同余方程，從而易于求解。例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 設(shè)(a, m) = 1，并且有整數(shù)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 設(shè)a1，a2是整數(shù)，m1，m2是正整數(shù)，證明：同余方程組 (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)，由同余的基本性質(zhì)，得到式(11)。習(xí) 題 一1. 證明定理1。2. 解同余方程：() 31x 5 (mod 17)；() 3215x 160 (mod 235)。3. 解同余方程組：。4. 設(shè)p是素數(shù)，0 a n。第四節(jié) 素數(shù)模的同余方程在上節(jié)中，我們證明了，對于素數(shù)p，模pa的同余方程的求解可以轉(zhuǎn)化為模p的同余方程的求解。本節(jié)要對素數(shù)模的同余方程做些初步研究。以下，設(shè)f(x) = anxn + L + a1x + a0是整系數(shù)多項式，p是素數(shù)，pan。定理1 設(shè)k n，若同余方程f(x) = anxn + L + a1x + a0 0 (mod p) (1)有k個不同的解x1, x1, L, xk，則對于任意的整數(shù)x，有f(x) (x - x1) (x - x2)L(x - xk)fk(x) (mod p)，其中fk(x)是一個次數(shù)為n - k的整系數(shù)多項式，并且它的xn - k項的系數(shù)是an。證明 由多項式除法，有f(x) = (x - x1)f1(x) + r1， (2)其中f1(x)是首項系數(shù)為an的n - 1次整系數(shù)多項式，r1是常數(shù)。在式(2)兩邊令x = x1，則由假設(shè)條件可知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是素數(shù)，則對于任何整數(shù)x，有x p - 1 - 1 (x - 1)(x - 2)L(x - p + 1) (mod p)。證明 由Fermat定理（第二章第四節(jié)定理2），數(shù)1, 2, L, p - 1是同余方程x p - 1 1 (mod p)的解，因此，利用定理1即可得證。定理2 同余方程(1)的解數(shù) n。證明 假設(shè)同余方程(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)的解數(shù)大于n，則pbi，0 i n。 （7)證明 若式(7)不成立，設(shè)pbd，d n，pbi， d j n。則bnxn + L + b0 bdxd + L + b0 0 (mod p)。 (8)由定理2，同余方程(8)的解數(shù)不大于d，因而不大于n，這與假設(shè)矛盾。因此，式(7)必成立。證畢。定理3 同余方程(1)或者有p個解，或者存在次數(shù)不超過p - 1的整系數(shù)多項式r(x)，使得同余方程(1)與r(x) 0 (mod p)等價。證明 由多項式除法可知，存在整系數(shù)多項式g(x)與r(x)，使得f(x) = g(x)(x p - x) + r(x)。 (9)由Fermat定理，對于任意的整數(shù)x，有x p x (mod p)，因此，如果r(x)的系數(shù)都是p的倍數(shù)，則對于任意的整數(shù)x，f(x) 0 (mod p)，即同余方程(1)有p個解。如果r(x)的系數(shù)不都是p的倍數(shù)，則r(x)的次數(shù)不超過p - 1。由式(9)看出，對于任意的整數(shù)x，f(x) r(x) (mod p)，即同余方程(1)與r(x) 0 (mod p)等價。證畢。定理4 設(shè)n p，則同余方程f(x) = xn + an - 1xn - 1 + L + a1x + a0 0 (mod p) (10)有n個解的充要條件是存在整數(shù)多項式q(x)和r(x)，r(x)的次數(shù) n，使得x p - x = f(x)q(x) + pr(x)。 (11)證明 必要性 由多項式除法，存在整系數(shù)多項式q(x)與r1(x)，r1(x)的次數(shù) 2，(a, p) = 1的情形。此時，因為(4a, p) = 1，所以，方程(1)等價于方程4a2x2 + 4abx + 4ac 0 (mod p)，即(2ax + b)2 b2 - 4ac (mod p)。這樣，研究方程(1)歸結(jié)為對方程x2 n (mod p) (2)的研究。定義 給定整數(shù)p，對于任意的整數(shù)n，(n，p) = 1，若方程(2)有解，則稱n是模p的二次剩余，記為nQR(p)；否則，稱n是模p的二次非剩余，記為nQNR(p)。顯然，若n1 n2 (mod p)，則它們同是模p的二次剩余（或二次非剩余），因此，在談到模p的二次剩余（或二次非剩余）時，把n1和n2看作是同一個。以下，在本節(jié)中，總假定p是奇素數(shù)。定理 若(n, p) = 1，則() n是模p的二次剩余的充要條件是 1 (mod p)； (3)() 若n是模p的二次剩余，則方程(2)有兩個解；() n是模p的二次非剩余的充要條件是 -1 (mod p)。 (4)證明 結(jié)論()與()由第四節(jié)定理直接推出。() 若(n, p) = 1，由第二章第四節(jié)定理，有np - 1 1 (mod p)， 0 (mod p)。 (5)因為p是奇素數(shù)，所以式(3)式與式(4)必有且僅有一個成立，利用結(jié)論()，可得到結(jié)論()。證畢。定理 模p的簡化系中，二次剩余與二次非剩余的個數(shù)都是，而且，模p的每個二次剩余與且僅與數(shù)列12，22，L， (6)中的一個數(shù)同余。證明 顯然，數(shù)列(6)包含了模p的全部二次剩余。為了證明定理，只需證明式(6)中的任何兩個數(shù)對模p不同余。對任意的整數(shù)k，s，1 k s ，若k2 s2 (mod p)， (7)則pk + s或pk - s。這都是不可能的，所以式(7)不能成立。證畢。定義 給定奇素數(shù)p，對于整數(shù)n，定義Legendre符號為例如，由定理1，1與4是模5的二次剩余，2與3是模5的二次非剩余，于是，定理3 設(shè)p是奇素數(shù)，n是整數(shù)，則() (mod p)；() 若n n1 (mod p)，則；() ；() 對任意的整數(shù)ni，1 i k，有。證明 結(jié)論()與()容易由定義2及定理1得到。為了證明結(jié)論()，只需證明其中的第二個等式。由結(jié)論()，有(mod p)，其中同余式兩端都只能取值 +1或 -1，因此，結(jié)論()的第二個等式成立。最后，由結(jié)論()，有由于上式首端與末端都是只取值 -1，0或1的整數(shù)，所以它們必相等。結(jié)論()得證。證畢。推論 設(shè)p是奇素數(shù)，則 -1QR(p)的充要條件是p 1(mod 4)；-1QNR(p)的充要條件是p 3(mod 4)。例1 判斷方程x2 5 (mod 11)有沒有解。解 由定理2，因為 (mod 11)，方程有解。例2 設(shè)p是奇素數(shù)，p 1 (mod 4)，則 -1 (mod p)解 由Wilson定理（第二章第二節(jié)例3），有定理2和例2說明，當素數(shù)p 1(mod 4)時，模p的所有二次剩余之積對模p同余于 -1。此外，我們還得到了方程的解。例3 設(shè)n是整數(shù)，證明n2 + 1的任何奇因數(shù)都是4m + 1（mZ）的形式。解 由于任何奇數(shù)都可表成奇素數(shù)之積，而且任意多個形如4m + 1的整數(shù)之積也具有4m + 1的形式，我們只需證明：若素數(shù)p是n2 + 1的因數(shù)，則p具有4m + 1的形式。事實上，若pn2 + 1，則n2 -1 (mod p)，即-1QR(p)。由定理3推論得出所需結(jié)論。例 形如4m + 1（kZ）的素數(shù)有無窮多個。解 用反證法。假設(shè)只有有限多個形如4k + 1的素數(shù)p1, p2, L, pk，記N = 4(p1p2Lpk)2 + 1。由例2，必有奇素數(shù)q，q 1 (mod 4)，qN，顯然q pi（1 i k），這與假設(shè)矛盾，所以形如4m + 1的素數(shù)有無窮多個。例 若a 1 (mod 4)，2b，并且b沒有形如4k + 3（kZ）的素因數(shù)，證明方程y2 = x3 - a3 - b2 (8)沒有整數(shù)解。解 用反證法。假設(shè)有整數(shù)x，y滿足方程(8)。若2x，則由式(8)得則y2 -1(mod 4)這不可能。若x 3 (mod 4)，則由式(8)得到y(tǒng)2 x3 - a3 - b2 33 - 13 - 0 2 (mod 4)，這是不可能的。若x 1 (mod 4)，則x2 + ax + a2 1 + a + a2 3 (mod 4)， (9)因此，必有素數(shù)p 3 (mod 4)，使得px2 + ax + a2 。 (10)由式(8)與式(10)得到y(tǒng)2 = x3 - a3 - b2 -b2 (mod p)， (11)即 -b2 QR(p)。但是，由假設(shè)，pb2，所以有，這與式(11)矛盾。例 設(shè)p是素數(shù)，證明：數(shù)例1, 2, L, p - 1中的模p的二次剩余之和是。解 對于整數(shù)k，1 k ，記k2 = pqk + rk，qkZ，1 rk p - 1，則qk =，并且，由定理2，有例 設(shè)p是奇素數(shù)，證明：若同余方程x4 + 1 0 (mod p) (12)有解，則p 1 (mod 8)。解 設(shè)x a (mod p)是方程(12)的解，則a4 -1 (mod p)， (13)a8 1 (mod p)。 (14)以d0表示使ad 1 (mod p) (15)成立的最小正整數(shù)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)。習(xí) 題 五1. 同余方程x2 3 (mod 13)有多少個解？2. 求出模23的所有的二次剩余和二次非剩余。3. 設(shè)p是奇素數(shù)，證明：模p的兩個二次剩余的乘積是二次剩余；兩個二次非剩余的乘積是二次剩余；一個二次剩余和一個二次非剩余的乘積是二次非剩余。4. 設(shè)素數(shù) p 3 (mod 4)，= 1，證明x (mod p)是同余方程x2 n (mod p)的解。5. 設(shè)p是奇素數(shù)，(n, p) = 1，a是正整數(shù)，證明同余方程x2 n (mod pa)有解的充要條件是= 1。6. 設(shè)p是奇素數(shù)，證明：模p的所有二次剩余的乘積與對模p同余。第六節(jié) 二次互反律本節(jié)要對Legendre符號和二次剩余做進一步的研究