【文章內(nèi)容簡介】 式(15)與式(13)聯(lián)合，得到方程(14)的解x = 1 + 5(1 + 5t1) = 4 + 25t1，t1206。Z。 (16)將式(16)中的x代入同余方程(11)，得到 2(4 + 25t1)2 + 13(4 + 25t1) 34 186。 0 (mod 53)，50 + 725t1 186。 0 (mod 53)，2 + 29t1 186。 0 (mod 5)，t1 186。 2 (mod 5)。將上式與(16)聯(lián)合，得到同余方程(11)的一個解x = 4 + 25t1 = 4 + 25(2 + 5t2) 186。 54 (mod 53)。(ⅱ) 從同余方程(12)的另一個解 x 186。 2 (mod 5)出發(fā)利用上述方法，可以求出同余方程(11)的另一個解。（略，請讀者補(bǔ)足）。例3 解同余方程x2 186。 1 (mod 2k)，k206。N。 (17)解 若k = 1，則方程(17)的解是x 186。 1 (mod 2)。若k = 2，則方程(17)的解是x 186。 1，1 (mod 4)。若k 179。 3，則同余方程(17)，即x2 1 = (x + 1)(x 1) 186。 0 (mod 2k)，的解必是奇數(shù)，設(shè)x = 2y + 1，則同余方程(1)成為(2y + 2)2y 186。 0 (mod 2k)，y(y + 1) 186。 0 (mod 2k 2)。 (18)同余方程(18)的解是y1 186。 0，y2 186。 1 (mod 2k 2)，即y1 = 2k 2u， y2 = 1 + 2k 2v，u, v206。Z，所以，方程(17)的解是x1 = 2k 1u + 1，x2 = 2k 1v 1， u, v206。Z，即x 186。 1，1 + 2k 1，1，1 + 2k 1 (mod 2k)。例4 解同余方程 x2 186。 2 (mod 73)。解 設(shè)x是這個同余方程的解，則它可以表示成x = x0 + 7x1 + 72x2，0 163。 xi 163。 6，0 163。 i 163。 2，代入原方程，得到(x0 + 7x1 + 72x2)2 186。 2 (mod 73)， (19)因此(x0 + 7x1 + 72x2)2 186。 2 (mod 7)，x02 186。 2 (mod 7)，所以x0 186。 3或4 (mod 7)。于是x0 = 3或4。(ⅰ) 若x0 = 3，由式(19)，有(3 + 7x1 + 72x2)2 186。 2 (mod 72)，9 + 42x1 186。 2 (mod 72)，6x1 186。 1 (mod 7)，x1 186。 1 (mod 7)，x1 = 1。再由式(19)，有(3 + 71 + 72x2)2 186。 2 (mod 73)，(10 + 49x2)2 186。 2 (mod 73)，3x2 186。 1 (mod 7)，x2 186。 2 (mod 7)，x2 = 2。這樣，求得原同余方程的一個解是x 186。 3 + 71 + 722 = 108 (mod 73)。(ⅱ) 若x0 = 4，用同樣的方法求出另一個解。（略）。注：例4中的方法是利用數(shù)的b進(jìn)制表示，這一方法可以處理模bk的同余方程，而不必要求b是素數(shù)。習(xí) 題 三1. 證明定理的推論。2. 將例2中略去的部分補(bǔ)足。3. 將例4中略去的部分補(bǔ)足。4. 解同余方程x2 186。 1 (mod 54)。5. 解同余方程f(x) = 3x2 + 4x 15 186。 0 (mod 75)。6. 證明：對于任意給定的正整數(shù)n，必存在m，使得同余方程x2 186。 1 (mod m)的解數(shù)T 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 163。 n，若同余方程f(x) = anxn + L + a1x + a0 186。 0 (mod p) (1)有k個不同的解x1, x1, L, xk，則對于任意的整數(shù)x，有f(x) 186。 (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 186。 0 (mod p)，因此，式(2)成為f(x) 186。 (x x1)f1(x) (mod p)。 (3)因此，當(dāng)k = 1時，定理成立。如果k 1，在上式中，令x = xi（i = 2, 3, L, k），則有0 186。 f(xi) 186。 (xi x1)f1(xi) (mod p)。 (4)由于x2, L, xk對于模p是兩兩不同余的，所以，上式給出f1(xi) 186。 0 (mod p)，i = 2, L, k。 (5)由此及歸納法，即可證明定理。證畢。推論 若p是素數(shù)，則對于任何整數(shù)x，有x p 1 1 186。 (x 1)(x 2)L(x p + 1) (mod p)。證明 由Fermat定理（第二章第四節(jié)定理2），數(shù)1, 2, L, p 1是同余方程x p 1 186。 1 (mod p)的解，因此，利用定理1即可得證。定理2 同余方程(1)的解數(shù)163。 n。證明 假設(shè)同余方程(1)有n + 1個不同的解x 186。 xi (mod p)，1 163。 i 163。 n + 1。由定理1，有f(x) 186。 an(x x1)L(x xn) (mod p)，因此0 186。 f(xn + 1) 186。 an(xn + 1 x1)L(xn + 1 xn) (mod p)。 (6)由于pan，xn + 1xi (mod p)，1 163。 i 163。 n，所以式(6)不能成立。這個矛盾說明同余方程(1)不能有n + 1個解。證畢。推論 若同余方程bnxn + L + b0 186。 0 (mod p)的解數(shù)大于n，則p189。bi，0 163。 i 163。 n。 （7)證明 若式(7)不成立，設(shè)pbd，d 163。 n，p189。bi， d j 163。 n。則bnxn + L + b0 186。 bdxd + L + b0 186。 0 (mod p)。 (8)由定理2，同余方程(8)的解數(shù)不大于d，因而不大于n，這與假設(shè)矛盾。因此，式(7)必成立。證畢。定理3 同余方程(1)或者有p個解，或者存在次數(shù)不超過p 1的整系數(shù)多項式r(x)，使得同余方程(1)與r(x) 186。 0 (mod p)等價。證明 由多項式除法可知，存在整系數(shù)多項式g(x)與r(x)，使得f(x) = g(x)(x p x) + r(x)。 (9)由Fermat定理，對于任意的整數(shù)x，有x p 186。 x (mod p)，因此，如果r(x)的系數(shù)都是p的倍數(shù)，則對于任意的整數(shù)x，f(x) 186。 0 (mod p)，即同余方程(1)有p個解。如果r(x)的系數(shù)不都是p的倍數(shù)，則r(x)的次數(shù)不超過p 1。由式(9)看出，對于任意的整數(shù)x，f(x) 186。 r(x) (mod p)，即同余方程(1)與r(x) 186。 0 (mod p)等價。證畢。定理4 設(shè)n 163。 p，則同余方程f(x) = xn + an 1xn 1 + L + a1x + a0 186。 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ù) n，使得x p x = f(x)q(x) + r1(x)。 (12)若同余方程(10)有n個解x 186。 xi (mod p)（1 163。 i 163。 n），則由式(12)和Fermat定理，得到r1(xi) 186。 0 (mod p)，1 163。 i 163。 n。由此及定理2推論，可知r1(x)的系數(shù)都能被p整除，即r1(x) = pr(x)，其中r(x)是整系數(shù)多項式。這證明了式(11)。充分性 若式(11)成立，由Fermat定理，對于任何整數(shù)x，有0 186。 x p x 186。 f(x)q(x) (mod p)， (13)即同余方程f(x)q(x) 186。 0 (mod p)有p個解，但是，q(x)是p n次多項式，所以由定理2，方程q(x) 186。 0 (mod p)的解數(shù) 163。 p n。以l表示同余方程(10)的解數(shù)，則由第一節(jié)定理1，有l(wèi) + p n 179。 p，l 179。 n，再利用定理2，得到l = n。 證畢。注：若pan，由輾轉(zhuǎn)相除法可求出an162。，pan162。使得anan162。 186。 1 (mod p)，于是，同余方程(1)與同余方程an162。f(x) = xn + an162。an 1xn 1 + L + an162。a1x + an162。a0 (mod p)等價。因此，定理4是有普遍性的。定理5 若p是素數(shù)，n189。p 1，pa則x n 186。 a (mod p) (14)有解的充要條件是186。1 (mod p)。 (15)若有解，則解數(shù)為n。證明 必要性 若方程(14)有解x0，則px0，由Fermat定理，得到= x0p 1 186。1 (mod p)。充分性 若式(15)成立，則其中P(x)是關(guān)于x的整系數(shù)多項式。由定理4可知同余方程(14)有n個解。證畢。例1 判定同余方程2x3 + 3x + 1 186。 0 (mod 7)是否有三個解。解 因為24 186。 1 (mod 7)，所以，原方程與42x3 + 43x + 4 186。 0 (mod 7)即x3 2x 3 186。 0 (mod 7)等價。由于x7 x = ( x3 2x 3)(x4 + 2x2 + 3x + 4) + 12x2 + 16x + 12，所以，由定理4可知，原方程的解數(shù)小于3。例2 解同余方程3x14 + 4x10 + 6x 18 186。 0 (mod 5)。解 由Fermat定理，x5 186。 x (mod 5)，因此，原同余方程等價于2x2 + x 3 186。 0 (mod 5)。 (16)將x 186。 0，177。1，177。2 (mod 5)分別代入方程(1