【正文】 明式(4)當(dāng)n = k + 1也成立。； 解：；167。證明：顯然對的不同取值，共有個(gè)值，故只需證這樣的個(gè)值，關(guān)于模的兩兩互不同余。 若是個(gè)兩兩互質(zhì)的正整數(shù)，分別通過模的完全剩余類，則 通過模的完全剩余系，其中，證明：（數(shù)學(xué)歸納法）（1） 根據(jù)本節(jié)定理3，知時(shí)，結(jié)論成立。現(xiàn)增加使 ，令，則易知，再令，當(dāng)過模的完全剩余系，過模的完全剩余系時(shí)，據(jù)本節(jié)定理3，必過模的完全剩余系，即對結(jié)論成立。 （ii）說明應(yīng)用個(gè)特別的砝碼，在天平上可以量出1到H中的任意一個(gè)斤數(shù)。（ii）特制個(gè)砝碼分別重斤，把要稱的物體及取1的砝碼放在天平的右盤，取1的砝碼放在左盤，則從（i）的結(jié)論知，當(dāng)取適當(dāng)?shù)闹禃r(shí)，可使之值等于你所要稱的物體的斤數(shù)。證明：（數(shù)學(xué)歸納法）（1）時(shí)，分別過模的完全剩余系時(shí)，共有個(gè)值，且若，且，即時(shí)結(jié)論成立；（2）設(shè)當(dāng)分別過模的完全剩余系時(shí)，過模的完全剩余系。當(dāng)分別過模的完全剩余系時(shí)，2有個(gè)值，且據(jù)歸納假設(shè)，若； ，…，…。3．簡化剩余系與歐拉函數(shù)1．證明定理2：若是與互質(zhì)的整數(shù)，并且兩對模不同余，則是模的一個(gè)簡化剩余系。2．若是大于1的正整數(shù)，是整數(shù)，通過的簡化剩余系，則，其中表示展布在所通過的一切值上的和式。若＞2，則必是偶數(shù)，又由，得，且易見，故所以左邊每一項(xiàng)都存在另一項(xiàng)，使得，右邊共有對，此即。3．（i）證明，p質(zhì)數(shù)。證明：（i）因?yàn)?，所? = =(ii)設(shè)是a的標(biāo)準(zhǔn)分解式，則， = =a4．若是k個(gè)兩兩互質(zhì)的正整數(shù)， 分別通過模的簡化剩余系，則 通過模的簡化剩余系，其中。顯見，則又由定理4知，通過模的簡化剩余系，注意到：所以，通過模m的簡化剩余系。解：，據(jù)歐拉定理，易知　　　　　　　　　　　　（１）又故　　則?。桑ǎ保┘吹茫梢陨嫌?jì)算，知?。?、證明下列事實(shí)但不許用定理１推論：若是質(zhì)數(shù)，是整數(shù)，則。證明　對應(yīng)用數(shù)學(xué)歸納法：當(dāng)時(shí)，按二項(xiàng)式展開即得設(shè)時(shí)，結(jié)論成立，即當(dāng)時(shí)，結(jié)論成立。進(jìn)一步，設(shè)，則　固對任一整數(shù)，若，則由上述已證性質(zhì)得：存在，使故=（）依此類推可得．若，則 ，定理成立。證明：必要性，若結(jié)論成立，則由定理2知（b，10）=1，令t=則據(jù)歐拉定理得；充分性，若有正數(shù)t，滿足令t為使上式成立的最小正整數(shù)，且=且。第四章 同余式 1 基本概念及一次同余式例 解同余式 解：（12，45）= 同余多項(xiàng)式有3個(gè)解 而原同余式為 4 與也一樣所以原同余式的3個(gè)解是 （ｔ＝０、１、２）即，　 求下列各同余式的解 256x179 1215x5601296x1125337是素?cái)?shù)， ，原同余式有唯一解。 由144x125得原同余式的解是2．求聯(lián)立同余式的解。3．(i)設(shè)是正整數(shù)，．證明 是同余式 的解(ii)設(shè)是質(zhì)數(shù)，證明是同余式的解．證明: (i) ， 有唯一解．而據(jù)歐拉定理，得 ， 即 是的解．(ii) 即有唯一解又 個(gè)連續(xù)整數(shù)之積必被所整除，故可令 則即即 是的解．設(shè)p是素?cái)?shù)，0 a p，證明：(mod p)。 b (mod p)的解。 b (mod p)解唯一，故只須將(mod p)代入ax 186。4．設(shè)是正整數(shù)，是實(shí)數(shù)，證明同余式有解．證明: 因 故同余式 必有解，(i) 若 ，則結(jié)論成立。若又令 則 重復(fù)上述討論：即若 則結(jié)論成立， 若又令 `````` 例解同余方程組解：互質(zhì)，故原方程組對模有唯一解即根據(jù)孫子定理方程組的解是注意到 故有限步后，必有 其中即結(jié)論成立。（ii） 二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問本數(shù)。解：（i）依題意得則據(jù)孫子定理，上述方程組有唯一解由故原方程組的解是(ii)依題意得（i）設(shè) 是三個(gè)正整數(shù)，證明：． （ii）設(shè) 證明：同余式組 （1）有解的充分與必要條件是在有解的情況下，適合（1）的一切整數(shù)可由下式求出：其中是適合的一個(gè)整數(shù)。證明： 即 設(shè)有解，即故此得，必要性成立；反之，設(shè)即則由167。進(jìn)一步，若有解，則即是的公倍數(shù)，當(dāng)然也是的倍數(shù)，故若是的一個(gè)解，則的任一解必滿足。從而由知必有，必要性成立。首先，推，用歸納法易證：又由知時(shí)，充分性也成立；現(xiàn)設(shè)同余式組 有解，即。后一結(jié)論由上述過程亦成立。3 高次同余式的解數(shù)及解法 解同余式。4．質(zhì)數(shù)模的同余式補(bǔ)充例子：1．解同余方程：(ⅰ) 3x11 + 2x8 + 5x4 1 186。 0 (mod 5)。 0 (mod 7)，用x = 0，177。2，177。 0 (mod 5)，將x = 0，177。2 代入，知后者有解x 186。1 (mod 5)。 0 (mod 5)是否有三個(gè)解；(ⅱ) x6 + 2x5 4x2 + 3 186。 0 (mod 5)等價(jià)于x3 3x2 + 4x 3 186。定理5 若p是素?cái)?shù)，n189。 a (mod p) (14)有解的充要條件是186。 (15)若有解，則解數(shù)為n。1 (mod p)。由定理4可知同余方程(14)有n個(gè)解。 設(shè)︱， ， ．證明同余式 有解的充分必要條件是，并且在有解的情況下就有個(gè)解。它有個(gè)解。2．設(shè)n是整數(shù)，（a，m）=1，且已知同余式有一解，證明這個(gè)同余式的一切解可以表成 其中y是同余式的解。 a (mod m)，證明同余方程xk 186。 yx0 (mod m)，其中y滿足同余方程yk 186。解：設(shè)x1是xk 186。 x1 (mod m)有解y，再由yka 186。 (yx0)k 186。 a (mod m)得yk 186。 yx0 (mod m)，其中y滿足同余方程yk 186。 a(mod m)的解。1 一般二次同余式 在同余式中，若，試求出它的一切解來。易見，當(dāng)為偶數(shù)時(shí)，則，上同余式有解：，共有個(gè)解當(dāng)為奇數(shù)時(shí)，上同余式有解：，共有個(gè)解。證明：因，故用乘后再配方，即得仍記為，即有由以上討論即知若為的解，則為的解，必要性得證。由充分性的討論即知的解可由的解導(dǎo)出。2 單質(zhì)數(shù)的平方剩余與平方非剩余 求出模的平方剩余與平方非剩余。 （1） （2） （3）中之一數(shù)同余，而 故模37的平方剩余為： 1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36而其它的18個(gè)數(shù)為模37的平方非剩余： 2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，352． 應(yīng)用前幾章的結(jié)果證明:模的簡化剩余系中一定有平方剩余及平方非剩余存在， 證明兩個(gè)平方剩余的乘積是平方剩余。 應(yīng)用、證明：模的簡化剩余系中平方剩余與平方非剩余的個(gè)數(shù)各為。若模的簡化剩余系中均為平方剩余，考慮模的絕對最小簡化剩余系：它們的平方為模下的個(gè)數(shù)： 由假設(shè)模的簡化剩余系中任一個(gè)數(shù)與上個(gè)數(shù)同余，而模的簡化剩余系中有個(gè)數(shù)，故必有兩個(gè)互相同余，矛盾。若為平方剩余，則故從而也為平方剩余。設(shè)為模的簡化剩余系中的平方剩余；為模的簡化剩余系中的平方非剩余。故反之，由為平方剩余知故，得證。3 勒讓得符號1．用本節(jié)方法判斷下列同余式是否有解 其中503，563，769，1013都是質(zhì)數(shù) 解：，有解。 ，有解。解：為模平方剩余時(shí)，必有，必有，故，必有，故為模平方非剩余時(shí)，必有，必有，故，必有，故設(shè)是正整數(shù)，及都是質(zhì)數(shù)，說明由此證明：。167。再因?yàn)槭瞧尜|(zhì)數(shù)，關(guān)于模我們有或，當(dāng)時(shí)，當(dāng)時(shí)，這樣為平方剩余時(shí)，為下方程組的解或由孫子定理，即可知或，立即當(dāng)時(shí)，為平方剩余。因?yàn)楫?dāng)為偶數(shù)，或?yàn)槠鏀?shù)，時(shí)，即或時(shí)，為平方剩余，類似或，為平方非剩余。解：由上題知以為平方非剩余的質(zhì)數(shù)滿足：又由為模的最小平方非剩余，故從而（167。167。3習(xí)題1所列各同余式是否有解。解：，故故，即的解數(shù)為0． ，故解數(shù)為2．3． 在有解的情況下，應(yīng)用定理1，求同余式，的解。2 定理1及167。解：同余式有解，故 由知故即為原同余式的解。 若后式成立，那末 由167。6 合數(shù)模的情形1. 解同余式 ，解：從同余式 得令代入得出從而即有故，再令代入 得出 ， 即從而 故 所以 為所給同余式的解從而所有的解為：（ⅱ），故有四解記代入，即有：解得記，代入即有：，解得：又記，代入即有，解得: 故為其一解其余三解為： 2．（?。┳C明同余式與同余式等價(jià)，（ⅱ）應(yīng)用（?。┡e出一個(gè)求同余式的一切解的方法。第六章 原根與指標(biāo)1. 設(shè)p是單質(zhì)數(shù)，a是大于1的整數(shù)，證明:(i)的奇質(zhì)數(shù)q是a1的因數(shù)或是形如2px+1的整數(shù)，其中x是整數(shù)(ii) 的單質(zhì)因數(shù)是a+1的因數(shù)或是形如2px+1的整數(shù)，其中x是整數(shù)證明(i)設(shè) 則設(shè)a對模q的質(zhì)數(shù)是 是質(zhì)數(shù) 從而或p若，則，故。(ii)設(shè)q為的奇質(zhì)因數(shù)，則從而，從而a對模q的指數(shù)．故，2，p，2p之一若，則，從而 即有，不可能，故若，則，而(否則) 故若，則，而有，不可能若，則由，q－1＝2m記m＝px，則q＝2px+1，得證2. 設(shè)對模m的指數(shù)是，試證對模m的指數(shù)是證明：設(shè)對模m的指數(shù)為，則 而，股反之故，從而=得證例1 求1，2，3，4，5，6對模7的指數(shù)。例1中的結(jié)果可列表如下：a123456d7(a)136362這樣的表稱為指數(shù)表。下面是模10的指數(shù)表：a1379d10(a)14421．寫出模11的指數(shù)表。解：x 186。1．求模29的最小正原根。2．分別求模293和模2293的原根。3．解同余方程：x12 186。解：易得3是模17的原根，3i（i = 0, 1, 2, L, 15）