【文章內容簡介】 x5 + 5x4 + 2x2 1 186。 0 (mod 7)，用x = 0，177。1，177。2，177。3代入知后者無解； (ⅱ) 原同余方程等價于2x4 + 2x3 + 3x 2 186。 0 (mod 5)，將x = 0，177。1，177。2 代入，知后者有解x 186。 177。1 (mod 5)。2．判定(ⅰ) 2x3 x2 + 3x 1 186。 0 (mod 5)是否有三個解；(ⅱ) x6 + 2x5 4x2 + 3 186。 0 (mod 5)是否有六個解？解：(ⅰ) 2x3 x2 + 3x 1 186。 0 (mod 5)等價于x3 3x2 + 4x 3 186。 0 (mod 5)，又x5 x = (x3 3x2 + 4x 3)(x2 + 3x + 5) + (6x2 12x + 15)，其中r(x) = 6x2 12x + 15的系數不都是5的倍數，故原方程沒有三個解； (ⅱ) 因為這是對模5的同余方程，故原方程不可能有六個解。定理5 若p是素數，n189。p 1，pa則x n 186。 a (mod p) (14)有解的充要條件是186。1 (mod p)。 (15)若有解，則解數為n。證明 必要性 若方程(14)有解x0，則px0，由Fermat定理，得到= x0p 1 186。1 (mod p)。充分性 若式(15)成立，則其中P(x)是關于x的整系數多項式。由定理4可知同余方程(14)有n個解。證畢。 設︱， ， ．證明同余式 有解的充分必要條件是，并且在有解的情況下就有個解。證明：設則但則由 可得。它有個解。︱ 令則無多于個解，而 恰有個解，必有個解。2．設n是整數，（a，m）=1，且已知同余式有一解，證明這個同余式的一切解可以表成 其中y是同余式的解。證明：設均是的解， 則， （a，m）=1 ， （，m）= (，m) = 1 則由第三章定理3．3知，必存在y，使 ， ．故原同余式的任一解可表示為而y滿足3．設(a, m) = 1，k與m是正整數，又設x0k 186。 a (mod m)，證明同余方程xk 186。 a(mod m)的一切解x都可以表示成x 186。 yx0 (mod m)，其中y滿足同余方程yk 186。 1 (mod m)。解：設x1是xk 186。 a(mod m)的任意一個解，則一次同余方程yx0 186。 x1 (mod m)有解y，再由yka 186。 ykx0k 186。 (yx0)k 186。 x1k 186。 a (mod m)得yk 186。 1 (mod m)，即x1可以表示成x 186。 yx0 (mod m)，其中y滿足同余方程yk 186。 1 (mod m)；反之，易知如此形式的x是xk 186。 a(mod m)的解。第五章 二次同余式與平方剩余167。1 一般二次同余式 在同余式中，若，試求出它的一切解來。解：若，則，上同余式即為從而，即有。易見，當為偶數時，則，上同余式有解：，共有個解當為奇數時，上同余式有解：，共有個解。證明：同余式 有解的充分必要條件是 有解，并且前一同余式的一切解可由后一同余式的解導出。證明：因，故用乘后再配方，即得仍記為，即有由以上討論即知若為的解，則為的解，必要性得證。反之，若有一解，即有：由于，故有解即有：即有：由，即有：即為的解，充分性得證。由充分性的討論即知的解可由的解導出。167。2 單質數的平方剩余與平方非剩余 求出模的平方剩余與平方非剩余。解：，由書中定理2知，模的簡化剩余系中個平方剩余分別與序列例2．試判斷下述同余方程是否是有解。 （1） （2） （3）中之一數同余，而 故模37的平方剩余為： 1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36而其它的18個數為模37的平方非剩余： 2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，352． 應用前幾章的結果證明:模的簡化剩余系中一定有平方剩余及平方非剩余存在， 證明兩個平方剩余的乘積是平方剩余。平方剩余與平方非剩余的乘積是平方非剩余。 應用、證明：模的簡化剩余系中平方剩余與平方非剩余的個數各為。證明：因為1為模的簡化剩余系中的平方剩余。若模的簡化剩余系中均為平方剩余，考慮模的絕對最小簡化剩余系：它們的平方為模下的個數： 由假設模的簡化剩余系中任一個數與上個數同余，而模的簡化剩余系中有個數，故必有兩個互相同余，矛盾。從而必有平方非剩余存在。若為平方剩余，則故從而也為平方剩余。若為平方剩余，為平方非剩余，則故從而為平方非剩余。設為模的簡化剩余系中的平方剩余；為模的簡化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。3．證明：同余式，的解是 ，其中 證明：若有解，則有解， 設其解是：，即有： ，令而 ， 為整數由此兩式即得： 兩式相乘得： 取使得： 則 故其解為 4．證明同余式 的解是 證明：首先我們證明對任意： 有下式： 因為 ，于是 因此由威爾生定理得： 其次由，可令 ，代入上式即有 故原同余式的解為 167。3 勒讓得符號1．用本節(jié)方法判斷下列同余式是否有解 其中503，563，769，1013都是質數 解：，有解。，有解。 ，有解。求出以為平方剩余的質數的一般表達式；以為平方非剩余的質數的一般表達式。解：為模平方剩余時，必有，必有，故，必有，故為模平方非剩余時，必有，必有，故，必有，故設是正整數，及都是質數，說明由此證明：。證明：當時，由本節(jié)定理1的推論知為平方剩余，應用歐拉判別條件即有由，即得出而都是形如的素數，并且，所以。167。4 前節(jié)定理的證明 求以為平方剩余的質數的一般表達式，什么質數以為平方非剩余？解：由互反律 因此當它們同為或同時為時，一為，一為時，顯然，當為偶數，而時，當是奇數，即時。再因為是奇質數，關于模我們有或，當時，當時，這樣為平方剩余時，為下方程組的解或由孫子定理，即可知或，立即當時，為平方剩余。為平方非剩余時，為下方程組的解或由孫子定理，即可知或，立即當時，為平方非剩余。因為當為偶數，或為奇數，時，即或時，為平方剩余，類似或，為平方非剩余。求以為最小平方非剩余的質數的一般表達式。解：由上題知以為平方非剩余的質數滿足：又由為模的最小平方非剩余，故從而（167。3推證）滿足的素數形如，其中只有滿足故或時，為它的最小平方非剩余。167。5 雅可比符號 判斷167。3習題1所列各同余式是否有解。略 求出下列同余式的解數：，其中是一個質數。解：，故故，即的解數為0． ，故解數為2．3． 在有解的情況下，應用定理1，求同余式，的解。在有解的情況下，應用 167。2 定理1及167。3定理1的推論，求同余式，的解。解：同余式有解，故 由知故即為原同余式的解。 由知，故故因此或若前式成立，那末 即 若則原同余式的解是 即 為原同余式的解。 若后式成立，那末 由167。3定理1的推論知，2是模p的平方剩余，即于是： 若則原同余式的解是故為原同余式的解．167。6 合數模的情形1. 解同余式 ，解：從同余式 得令代入得出從而即有故，再令代入 得出 ， 即從而 故 所以 為所給同余式的解從而所有的解為：（ⅱ），故有四解記代入，即有：解得記，代入即有：，解得：又記，代入即有，解得: 故為其一解其余三解為： 2．（?。┳C明同余式與同余式等價，（ⅱ）應用（ⅰ）舉出一個求同余式的一切解的方法。證明：（ⅰ）顯然 （ⅱ）記有解，等價于方程組有解 易見的解為的解為的解為或二者不能同時成立，否則矛盾故它有兩個解，聯立方程組即可求出一切解。第六章 原根與指標1. 設p是單質數，a是大于1的整數，證明:(i)的奇質數q是a1的因數或是形如2px+1的整數，其中x是整數(ii) 的單質因數是a+1的因數或是形如2px+1的整數，其中x是整數證明(i)設 則設a對模q的質數是 是質數 從而或p若，則，故。若，而，q1為偶數，記q1=2x，則，又假設故q=2px+1得證。(ii)設q為的奇質因數，則從而，從而a對模q的指數．故，2，p，2p之一若，則，從而 即有，不可能，故若，則，而(否則) 故若，則，而有，不可能若，則由，q－1＝2m記m＝px，則q＝2px+1，得證2. 設對模m的指數是，試證對模m的指數是證明：設對模m的指數為，則 而，股反之故，從而=得證例1 求1，2，3，4，5，6對模7的指數。根據定義1直接計算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，d7(4) = 3，d7(5) = 6，d7(6) = 2。例1中的結果可列表如下：a123456d7(a)136362這樣的表稱為指數表。這個表就是模7的指數表。下面是模10的指數表：a1379d10(a)14421．寫出模11的指數表。解：經計算得d11(1) = 1，d11(2) = 10，d11(3) = 5，d11(4) = 5，d11(5) = 5，d11(6) = 10，d11(7) = 10，d11(8) = 10，d11(9) = 5，d11(10) = 2，列表得a12345678910d11(a)110555101010522．求模14的全部原根。解：x 186。 3，5 (mod 14)是模14的全部原根。1．求模29的最小正原根。解：因j(29) = 28 = 2