【正文】 3x 2 186。 1 (mod 5)。1，177。 (16)將x 186。 x (mod 5)，因此，原同余方程等價于2x2 + x 3 186。 0 (mod 5)。由于x7 x = ( x3 2x 3)(x4 + 2x2 + 3x + 4) + 12x2 + 16x + 12，所以，由定理4可知，原方程的解數(shù)小于3。 0 (mod 7)即x3 2x 3 186。解 因為24 186。例1 判定同余方程2x3 + 3x + 1 186。由定理4可知同余方程(14)有n個解。1 (mod p)。 (15)若有解，則解數(shù)為n。 a (mod p) (14)有解的充要條件是186。定理5 若p是素數(shù)，n189。a0 (mod p)等價。an 1xn 1 + L + an162。 1 (mod p)，于是，同余方程(1)與同余方程an162。使得anan162。注：若pan，由輾轉相除法可求出an162。 n，再利用定理2，得到l = n。以l表示同余方程(10)的解數(shù)，則由第一節(jié)定理1，有l(wèi) + p n 179。 0 (mod p)的解數(shù) 163。 f(x)q(x) (mod p)， (13)即同余方程f(x)q(x) 186。充分性 若式(11)成立，由Fermat定理，對于任何整數(shù)x，有0 186。由此及定理2推論，可知r1(x)的系數(shù)都能被p整除，即r1(x) = pr(x)，其中r(x)是整系數(shù)多項式。 i 163。 n），則由式(12)和Fermat定理，得到r1(xi) 186。 xi (mod p)（1 163。 (11)證明 必要性 由多項式除法，存在整系數(shù)多項式q(x)與r1(x)，r1(x)的次數(shù) n，使得x p x = f(x)q(x) + r1(x)。 p，則同余方程f(x) = xn + an 1xn 1 + L + a1x + a0 186。證畢。 r(x) (mod p)，即同余方程(1)與r(x) 186。如果r(x)的系數(shù)不都是p的倍數(shù)，則r(x)的次數(shù)不超過p 1。 x (mod p)，因此，如果r(x)的系數(shù)都是p的倍數(shù)，則對于任意的整數(shù)x，f(x) 186。證明 由多項式除法可知，存在整系數(shù)多項式g(x)與r(x)，使得f(x) = g(x)(x p x) + r(x)。定理3 同余方程(1)或者有p個解，或者存在次數(shù)不超過p 1的整系數(shù)多項式r(x)，使得同余方程(1)與r(x) 186。因此，式(7)必成立。 0 (mod p)。則bnxn + L + b0 186。bi， d j 163。 （7)證明 若式(7)不成立，設pbd，d 163。 i 163。 0 (mod p)的解數(shù)大于n，則p189。證畢。 n，所以式(6)不能成立。 (6)由于pan，xn + 1xi (mod p)，1 163。 f(xn + 1) 186。由定理1，有f(x) 186。 i 163。證明 假設同余方程(1)有n + 1個不同的解x 186。定理2 同余方程(1)的解數(shù)163。證明 由Fermat定理（第二章第四節(jié)定理2），數(shù)1, 2, L, p 1是同余方程x p 1 186。推論 若p是素數(shù)，則對于任何整數(shù)x，有x p 1 1 186。 (5)由此及歸納法，即可證明定理。 (4)由于x2, L, xk對于模p是兩兩不同余的，所以，上式給出f1(xi) 186。 f(xi) 186。 (3)因此，當k = 1時，定理成立。 0 (mod p)，因此，式(2)成為f(x) 186。證明 由多項式除法，有f(x) = (x x1)f1(x) + r1， (2)其中f1(x)是首項系數(shù)為an的n 1次整系數(shù)多項式，r1是常數(shù)。 0 (mod p) (1)有k個不同的解x1, x1, L, xk，則對于任意的整數(shù)x，有f(x) 186。定理1 設k 163。本節(jié)要對素數(shù)模的同余方程做些初步研究。 1 (mod m)的解數(shù)T n。 0 (mod 75)。 1 (mod 54)。3. 將例4中略去的部分補足。習 題 三1. 證明定理的推論。（略）。 3 + 71 + 722 = 108 (mod 73)。 2 (mod 7)，x2 = 2。 2 (mod 73)，3x2 186。再由式(19)，有(3 + 71 + 72x2)2 186。 1 (mod 7)，x1 186。 2 (mod 72)，9 + 42x1 186。于是x0 = 3或4。 2 (mod 7)，所以x0 186。 2 (mod 73)， (19)因此(x0 + 7x1 + 72x2)2 186。 i 163。 xi 163。 2 (mod 73)。 1，1 + 2k 1，1，1 + 2k 1 (mod 2k)。Z，所以，方程(17)的解是x1 = 2k 1u + 1，x2 = 2k 1v 1， u, v206。 0，y2 186。 0 (mod 2k 2)。 0 (mod 2k)，的解必是奇數(shù)，設x = 2y + 1，則同余方程(1)成為(2y + 2)2y 186。若k 179。若k = 2，則方程(17)的解是x 186。 (17)解 若k = 1，則方程(17)的解是x 186。 1 (mod 2k)，k206。（略，請讀者補足）。(ⅱ) 從同余方程(12)的另一個解 x 186。將上式與(16)聯(lián)合，得到同余方程(11)的一個解x = 4 + 25t1 = 4 + 25(2 + 5t2) 186。 0 (mod 5)，t1 186。 0 (mod 53)，50 + 725t1 186。Z。 1 (mod 5)。 0 (mod 25)，9t 186。 0 (mod 52)， (14)得到2(1 + 5t)2 + 13(1 + 5t) 34 186。 1，2 (mod 5)。 (11)解 容易驗證，同余方程2x2 + 13x 34 186。例2 解同余方程2x2 + 13x 34 186。 108 92 186。 108 91 186。 105 92 186。 105 91 186。 102 92 186。 102 91 186。 10a1 9a2 (mod 45)。 = 2，M2162。 a2 (mod 5)， a2 = 1，2。因此，原同余方程的解是下面六個同余方程組的解：x 186。用x = 0，1，2，3，4去驗證，得到(8)的解是x 186。 2，5，8 (mod 9)。 0 (mod 9)， (9)容易看出，這是一個對于任何整數(shù)t都成立的同余式，所以，方程(9)的解是t 186。 2 (mod 3)。容易驗證，同余方程x3 + 3x 14 186。 0 (mod 5)。解 原同余方程等價于同余方程組x3 + 3x 14 186。例1 解同余方程x3 + 3x 14 186。 1，同余方程(1)與(6)的解數(shù)相同。(x) 186。 xa (mod pa)是同余方程(1)的解。(a)0 (mod p)，則存在xa，xa 186。推論 使用定理的記號，(ⅰ) 若x 186。 0 (mod p2)的解，再利用定理，又可以求出方程f(x) 186。 0 (mod p)。即，我們無法從同余方程(2)的解x1出發(fā)去求得同余方程(1)的解。 0 (mod p)并且 f(x1)0 (mod pa)的情形進行討論。在定理中，沒有對f 162。 p 1，都是同余方程(1)的解。 x1 + pa 1i (mod pa)，0 163。 p 1。 i (mod p)，0 163。 0 (mod p)，并且f(x1) 186。(ⅱ) 若f 162。Z），于是x 186。(x)0 (mod p)，則關于t的同余方程(5)有唯一解t 186。 (5)下面考慮兩種情形。(x1) 186。(x1) 186。證明 我們來說明，如何確定式(3)中的t，使x1 + pa 1t滿足同余方程(1)，即要使an(x1+pa 1t)n+an 1(x1+pa 1t)n 1+L+a1(x1+pa 1t)+a0 186。 0 (mod p)，并且f(x1) 186。(ⅱ) 若f 162。(ⅰ) 若f 162。以f 162。于是，現(xiàn)在的問題是，對于方程(2)的每個解x1，是否必有方程(1)的解x0與之對應？若有，如何去確定它？定理 設p是素數(shù)，a 179。 x1 (mod p a 1)，x0 = x1 + p a 1t0，此處，t0是某個適當?shù)恼麛?shù)。 0 (mod p a) (1)的解，則它必是方程f(x) 186。本節(jié)要對模pa的同余方程做進一步討論。 0 (mod 105)。5. 證明：對于任意給定的n個不同的素數(shù)p1, p2, …, pn，必存在連續(xù)n個整數(shù)，使得它們中的第k個數(shù)能被pk整除。習 題 二1. 解同余方程組：2. 解同余方程組：3. 有一隊士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3人。 40(1) 15(1) + 361 186。 401 15(1) + 361 186。 40(1) 151 + 361 186。 401 151 + 361 186。 40a1 15a2 + 36a3 (mod 60)。 = 1，M3162。利用孫子定理，取m1 = 3，m2 = 4，m3 = 5，m = 60，M1 = 20，M2 = 15，M3 = 12，M1162。 a2 (mod 4)，x 186。 1 (mod 5)，這樣，同余方程(15)的解x可由下面的方程組決定：x 186。 1，x2(2) 186。 1，x2(1) 186。 0 (mod 5)。 0 (mod 3) (16)5x2 + 6x + 49 186。 0 (mod 60)。Z。 135(1) + 2211 + 3151 186。 = 1，M3162。在孫子定理中，取m1 = 3，m2 = 5，m3 = 7，m = 357 = 105，M1 = 35，M2 = 21，M3 = 15，M1162。 2 (mod 5)，n 186。解 n是同余方程組n 186。由定理4及算術基本定理，解一般模的同余方程可以轉化為解模為素數(shù)冪的同余方程。由孫子定理，對于選定的每一組{}，同余方程組(14)對模m有唯一解，而且，由定理2，當每個通過(13)式中的值時，所得到的T1T2…Tk個同余方程組(14)的解對于模m都是兩兩不同余的。 i 163。 k。 0 (mod mi)，1 163。 0 (mod mi) (11)的解的個數(shù)，則T = T1T2…Tk 。 k）分別表示同余方程f(x) 186。定理4 設m = m1m2Lmk ，其中m1, m2, L, mk 是兩兩互素的正整