【文章內(nèi)容簡介】 i）設(shè) 是三個正整數(shù)，證明：． （ii）設(shè) 證明：同余式組 （1）有解的充分與必要條件是在有解的情況下，適合（1）的一切整數(shù)可由下式求出：其中是適合的一個整數(shù)。應(yīng)用證明同余式組 有解的充分與必要條件是，并且有解的情況下，適合的一切整數(shù)可由下式求出：其中是適合的一個整數(shù)。證明： 即 設(shè)有解，即故此得，必要性成立；反之，設(shè)即則由167。1定理，知方程必有解，設(shè)其解為，即令則易見：且即有解，充分性得證。進一步，若有解，則即是的公倍數(shù)，當(dāng)然也是的倍數(shù)，故若是的一個解，則的任一解必滿足。若同余式組有解，則 也有解。從而由知必有，必要性成立。下證充分性。首先，推，用歸納法易證：又由知時，充分性也成立；現(xiàn)設(shè)同余式組 有解，即。設(shè)；又由條件知，而，從而，所以，即，又由，則同余式組，必有解 （※）顯然，即（※）就是同余式組的解，據(jù)歸納性原理，結(jié)論成立。后一結(jié)論由上述過程亦成立。167。3 高次同余式的解數(shù)及解法 解同余式。解：原同余式等價于 據(jù)孫子定理，可得故原同余式共有6個解是： 解同余式解： 故原同余式等價于1） 先解即 得②再解即 設(shè) 而由孫子定理設(shè)即原四條式有4個解是167。4．質(zhì)數(shù)模的同余式補充例子：1．解同余方程：(ⅰ) 3x11 + 2x8 + 5x4 1 186。 0 (mod 7)；(ⅱ) 4x20 + 3x12 + 2x7 + 3x 2 186。 0 (mod 5)。解：(ⅰ) 原同余方程等價于3x5 + 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的系數(shù)不都是5的倍數(shù)，故原方程沒有三個解； (ⅱ) 因為這是對模5的同余方程，故原方程不可能有六個解。定理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個解。證畢。 設(shè)︱， ， ．證明同余式 有解的充分必要條件是，并且在有解的情況下就有個解。證明：設(shè)則但則由 可得。它有個解。︱ 令則無多于個解，而 恰有個解，必有個解。2．設(shè)n是整數(shù)，（a，m）=1，且已知同余式有一解，證明這個同余式的一切解可以表成 其中y是同余式的解。證明：設(shè)均是的解， 則， （a，m）=1 ， （，m）= (，m) = 1 則由第三章定理3．3知，必存在y，使 ， ．故原同余式的任一解可表示為而y滿足3．設(shè)(a, m) = 1，k與m是正整數(shù)，又設(shè)x0k 186。 a (mod m)，證明同余方程xk 186。 a(mod m)的一切解x都可以表示成x 186。 yx0 (mod m)，其中y滿足同余方程yk 186。 1 (mod m)。解：設(shè)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)的解。初等數(shù)論試卷一、 單項選擇題：（1分/題20題=20分）１．設(shè)為實數(shù)，為的整數(shù)部分，則(　　)Ａ．；　?。拢?；Ｃ．；　?。模玻铝忻}中不正確的是(　　)Ａ．整數(shù)的公因數(shù)中最大的稱為最大公因數(shù)；Ｂ．整數(shù)的公倍數(shù)中最小的稱為最小公倍數(shù)Ｃ．整數(shù)與它的絕對值有相同的倍數(shù)Ｄ．整數(shù)與它的絕對值有相同的約數(shù)３．設(shè)二元一次不定方程（其中是整數(shù)，且不全為零）有一整數(shù)解，則此方程的一切解可表為(　　)Ａ．Ｂ．Ｃ．Ｄ．４．下列各組數(shù)中不構(gòu)成勾股數(shù)的是(　　)Ａ．５，１２，１３；　?。拢罚玻?，２５；Ｃ．３，４，５；　　　?。模?，１６，１７５．下列推導(dǎo)中不正確的是(　　)Ａ．Ｂ．Ｃ．Ｄ．６．模１０的一個簡化剩余系是(　　) Ａ．　　　　　　　?。拢茫　。模罚某浞直匾獥l件是(　　) Ａ．　　?。拢茫　　。模福O(shè)，同余式的所有解為(　　)Ａ．或　　　　?。拢颍茫颉　。模疅o解．設(shè)f(x)=其中為f(x)的一個解，則:( )A．B．C． D．10．則同余式：（ ）A．有時大于p但不大于n。 B．可超過pC．等于p D．等于n 11．若2為模p的平方剩余，則p只能為下列質(zhì)數(shù)中的 :( )A．3 B．11 C．13 D．23 12．若雅可比符號，則 ( )A．B．。C．。D．．13．( ) A． 4 B． 3 C． 2 D． 114． 模12的所有可能的指數(shù)為。( ) A．1，2，4 B．1，2，4，6，12 C．1，2，3，4，6，12 D．無法確定15． 若模m的單根存在，下列數(shù)中，m可能等于: ( ) A． 2 B． 3 C． 4 D． 12 16．對于模5，下列式子成立的是: ( ) A． B． C． D． 17．下列函數(shù)中不是可乘函數(shù)的是: ( ) A．茂陛鳥斯(mobius)函數(shù)w(a) 。B． 歐拉函數(shù)；C．不超過x的質(zhì)數(shù)的個數(shù)；D．除數(shù)函數(shù)；18． 若對模的指數(shù)是，0，0，則對模的指數(shù)是( )A． B． C． D．無法確定19．，均為可乘函數(shù)，則( )A．為可乘函數(shù)； B．為可乘函數(shù)C．為可乘函數(shù)； D．為可乘函數(shù)20．設(shè)為茂陛烏斯函數(shù)，則有( )不成立A． B． C． D．二．填空題：（每小題1分，共10分）21． 3在45中的最高次n＝ ____________________；22． 多元一次不定方程：，其中 ， ，…，N均為整數(shù)，有整數(shù)解的充分必要條件是___________________；23．有理數(shù)，，能表成純循環(huán)小數(shù)的充分必要條件是_______________________；24． 設(shè)為一次同余式，的一個解，則它的所有解為_________________________；25． 威爾生（wilson）定理：________________________________________；26． 勒讓德符號=________________________________________；27． 若，則是模的平方剩余的充分必要條件是_____________(歐拉判別條件)；28． 在模的簡化剩余系中，原根的個數(shù)是_______________________；29． 設(shè)，為模的一個原根，則模的一個原根為_____________；30． _________________________________。三．簡答題：（5分／題4題＝20分）31．命題“任意奇數(shù)的平方減1是8的倍數(shù)”對嗎？說明理由。32．“若，通過模的簡化剩余系，則也通過模的簡化剩余系”這命題是否正確？正確請證明，不正確請舉反例。33．求模17的簡化剩余系中平方剩余與平方非剩余。34．設(shè)為的標(biāo)準分解式，記為的正因數(shù)的和，為的正因數(shù)的個數(shù)，則＝？ ＝？ 為什么？四．計算題。（7分／題4題＝28分）35． 求不定方程6x+93y=75的一切整數(shù)解。36． 解同余方程組37．解同余式≡11(mod125)38．求模13的所有原根。五、證明題：（7分/題2題=14分）3試證： ，（x，y）=1 y是偶數(shù)的整數(shù)解可寫成： 這里，并且一為奇數(shù)，一為偶數(shù)。設(shè)a為正整數(shù)，試證： 其中表示展布在a的一切正因數(shù)上的和式。六、應(yīng)用題：（8分）4求30！中末尾0的個數(shù)。參考答案：一．單項選擇：ABCDD；DACCB；DCAAD；BCBAB。 二．填空題：21．21；22．；23．；24．；25．！+1為素數(shù)；26．1；27．；28．；29．與