《初等數(shù)論(閔嗣鶴、嚴(yán)士健)》習(xí)題解答2012完整版[1]

1、第一章 整數(shù)的可除性§1 整除的概念·帶余除法1證明定理3定理3 假設(shè)都是得倍數(shù)，是任意n個(gè)整數(shù)，那么是得倍數(shù)證明： 都是的倍數(shù)。 存在個(gè)整數(shù)使 又是任意個(gè)整數(shù)即是的整數(shù)2證明 證明 又，是連續(xù)的三個(gè)整數(shù)故 從而可知 3假設(shè)是形如x，y是任意整數(shù)，a，b是兩不全為零的整數(shù)的數(shù)中最小整數(shù)，那么證： 不全為在整數(shù)集合中存在正整數(shù)，因而有形如的最小整數(shù)，由帶余除法有那么，由是中的最小整數(shù)知 為任意整數(shù) 又有， 故4假設(shè)a，b是任意二整數(shù)，且，證明：存在兩個(gè)整數(shù)s，t使得成立，并且當(dāng)b是奇數(shù)時(shí)，s，t是唯一存在的當(dāng)b是偶數(shù)時(shí)結(jié)果如何？證：作序列那么必在此序列的某兩項(xiàng)之間即存在一個(gè)整

2、數(shù)，使成立當(dāng)為偶數(shù)時(shí)，假設(shè)那么令，那么有 假設(shè) 那么令，那么同樣有當(dāng)為奇數(shù)時(shí)，假設(shè)那么令，那么有假設(shè) ，那么令，那么同樣有，綜上所述，存在性得證下證唯一性當(dāng)為奇數(shù)時(shí)，設(shè)那么而 矛盾 故當(dāng)為偶數(shù)時(shí)，不唯一，舉例如下：此時(shí)為整數(shù)§2 最大公因數(shù)與輾轉(zhuǎn)相除法推論4.1 a，b的公因數(shù)與a，b的因數(shù)相同證：設(shè)是a，b的任一公因數(shù)，|a，|b由帶余除法|， |，, |,即是的因數(shù)。反過(guò)來(lái)|且|，假設(shè)那么，所以的因數(shù)都是的公因數(shù)，從而的公因數(shù)與的因數(shù)相同。2證明：見(jiàn)本書P2，P3第3題證明。3應(yīng)用§1習(xí)題4證明任意兩整數(shù)的最大公因數(shù)存在，并說(shuō)明其求法，試用你的所說(shuō)的求法及輾轉(zhuǎn)相除法實(shí)際

3、算出76501，9719解：有§1習(xí)題4知：使。，使如此類推知： 且而b是一個(gè)有限數(shù)，使，存在其求法為：4證明本節(jié)1式中的證：由P3§1習(xí)題4知在1式中有 ，而 ， ，即§3 整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1證明兩整數(shù)a，b互質(zhì)的充分與必要條件是：存在兩個(gè)整數(shù)s，t滿足條件證明 必要性。假設(shè)，那么由推論知存在兩個(gè)整數(shù)s，t滿足：，充分性。假設(shè)存在整數(shù)s，t使as+bt=1，那么a，b不全為0。又因?yàn)?，所?即。又，2證明定理3定理3 證：設(shè)，那么又設(shè)那么。反之假設(shè)，那么，從而，即=3設(shè) 1是一個(gè)整數(shù)系數(shù)多項(xiàng)式且，都不是零，那么1的根只能是以的因數(shù)作分子以為分母的既約

4、分?jǐn)?shù)，并由此推出不是有理數(shù)證：設(shè)1的任一有理根為，。那么 2由，所以q整除上式的右端，所以，又，所以；又由2有因?yàn)閜整除上式的右端，所以 ，所以故1的有理根為，且。假設(shè)為有理數(shù)，次方程為整系數(shù)方程，那么由上述結(jié)論，可知其有有理根只能是，這與為其有理根矛盾。故為無(wú)理數(shù)。另證，設(shè)為有理數(shù)=，那么但由知，矛盾，故不是有理數(shù)。§4 質(zhì)數(shù)·算術(shù)根本定理1試造不超過(guò)100的質(zhì)數(shù)表解：用Eratosthenes篩選法1算出a210內(nèi)的質(zhì)數(shù)為：2，3，5，73劃掉2，3，5，7的倍數(shù)，剩下的是100內(nèi)的素?cái)?shù)將不超過(guò)100的正整數(shù)排列如下： 1 2 3 4 5 6 7 8 9 1011 12

5、 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100解：因?yàn)?|848，所以，又8|856，所以8|B，又4|32，所以4|C，又9|3+

6、2+3+4+3+3，所以9|D，又9|3+5+9+3+7，所以9|E，又所以；同理有。3證明推論3.3并推廣到n個(gè)正整數(shù)的情形推論3.3 設(shè)a，b是任意兩個(gè)正整數(shù)，且，那么，其中，證：， ，. ，又顯然 ，同理可得，推廣設(shè),(其中為質(zhì)數(shù)為任意n個(gè)正整數(shù))， 那么4應(yīng)用推論3.3證明§3的定理4ii證：設(shè)，其中p1, p2, L, pk是互不相同的素?cái)?shù)，ai，bi1 £ i £ k都是非負(fù)整數(shù)，有由此知(a, b)a, b =ab；從而有假設(shè)是質(zhì)數(shù)n>1，那么n是2的方冪證：反證法設(shè)為奇數(shù)，那么 ， 為合數(shù)矛盾，故一定為的方冪§5 函數(shù)x,x及其在數(shù)

7、論中的一個(gè)應(yīng)用1求30！的標(biāo)準(zhǔn)分解式解：30內(nèi)的素?cái)?shù)為2，3，5，7，11，13，17，19，23，29， 2設(shè)n是任一正整數(shù)，a是實(shí)數(shù)，證明：(i) (ii) 證：(i)設(shè).那么由性質(zhì)II知,所以 ,所以，所以，又在與+之間只有唯一整數(shù)，所以 (ii) 證法一設(shè),那么當(dāng)時(shí), ;當(dāng)時(shí),;證法二令,是以為周期的函數(shù)。又當(dāng)，即。評(píng)注：證一充分表達(dá)了 常規(guī)方法的特點(diǎn)，而證二那么表現(xiàn)了較高的技巧。3設(shè)，是任意二實(shí)數(shù)，證明：(i) 或(ii) 證明：i由高斯函數(shù)x的定義有。那么 當(dāng) 當(dāng) 故 ii設(shè)，那么有 下面分兩個(gè)區(qū)間討論：假設(shè)，那么，所以，所以假設(shè)，那么，所以。所以ii證法2由于，對(duì)稱，不妨設(shè)4.

8、(i) 設(shè)函數(shù)在閉區(qū)間上是連續(xù)的，并且非負(fù)，證明:和式表示平面區(qū)域，內(nèi)的整點(diǎn)整數(shù)坐標(biāo)的點(diǎn)的個(gè)數(shù).(ii) 設(shè)p，q是兩個(gè)互質(zhì)的單正整數(shù)，證明：(iii) 設(shè)，T 是區(qū)域 內(nèi)的整點(diǎn)數(shù)，證明：(iv) 設(shè)，T 是區(qū)域， 內(nèi)的整點(diǎn)數(shù)，證明：證明：(略) 5. 設(shè)任一正整數(shù)，且，p 是質(zhì)數(shù)，證明：在的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)p的指數(shù)是其中.證明：在的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)p的指數(shù)有限，即，所以而第二章 不定方程§21 習(xí)題1、解以下不定方程 解： 原方程等價(jià)于： 顯然它有一個(gè)整數(shù)解 ， 故一般解為 原方程等價(jià)于： 顯然它有一個(gè)整數(shù)解 故一般解為 2、把100分成兩份，使一份可被整除，一份可被整除。

9、解：依題意 即求 的正整數(shù)解，解得 一般解是： 但除 外無(wú)其他正整數(shù)解，故有且只有 3、證明：二元一次不定方程 的非負(fù)整數(shù)解為 或 證明：當(dāng)時(shí)，原方程沒(méi)有整數(shù)解，而 故命題正確 當(dāng)時(shí)，原方程有且只有一個(gè)非負(fù)整數(shù)解 而 因?yàn)?所以 原方程有整數(shù)解 其中，由于，故中一正一負(fù)，可設(shè) 原方程的一般解是： 要求，僅當(dāng) 是整數(shù)時(shí)，才能取 ，否那么 故這個(gè)不等式的整數(shù)解個(gè)數(shù) 是 ：當(dāng)是整數(shù)時(shí) 因而 當(dāng) 不是整數(shù)時(shí) 因而 所以 證明2：二元一次不定方程ax + by = N的一切整數(shù)解為，tÎZ，于是由x ³ 0，y ³ 0得，但區(qū)間的長(zhǎng)度是，故此區(qū)間內(nèi)的整數(shù)個(gè)數(shù)為+ 1。：4、

10、證明：二元一次不定方程 ，當(dāng) 時(shí)有非負(fù)整數(shù)解， 那么不然。證明：先證后一點(diǎn)，當(dāng) 時(shí)，原方程有非負(fù)整數(shù)解 那么，這是不可能的。次證，當(dāng)N>ab-a-b時(shí)，因(a，b)=1，故原方程有整數(shù)解x，y，一般解是要求x-bt0，y會(huì)證明存在滿足這個(gè)不等式的整數(shù)可取使于是對(duì)于這個(gè)有：而這就證明了當(dāng)時(shí)，原方程有非負(fù)整數(shù)解1證明定理2推論。推論 單位圓周上座標(biāo)都是有理數(shù)的點(diǎn)稱為有理點(diǎn)，可以寫成的形式，其中a與b是不全為零的整數(shù)。證明：設(shè)有理數(shù)m ¹ 0滿足方程x2 + y2 = 1，即l2 + n2 = m2，于是得l = ±2abd，n = ±(a2 - b2)d，m =

11、 ±(a2 + b2)d或l = ±(a2 - b2)d，m = ±2abd，m = ±(a2 + b2)d，由此得(x, y) =。反之，代入方程x2 + y2 = 1即知這樣的點(diǎn)在單位圓周上。2求出不定方程的一切正整數(shù)解的公式。解：設(shè)不定方程有解那么(1)3/z-x或3/z+x因?yàn)榛?/z+x以下不妨設(shè)， 設(shè) 與矛盾!這樣而， ， 即 假設(shè)由引理可設(shè)從而 ， 為證得為整數(shù)， 必須有a ， b均為奇數(shù)，且假設(shè)設(shè)，其中為一奇一偶，且有4解不定方程：x2 + 3y2 = z2，x > 0，y > 0，z > 0，(x, y ) = 1。解

12、：設(shè)(z - x, z + x) = d，易知d = 1或2。由(z - x)(z + x) = 3y2得z - x = 3da2，z + x = db2，y = dab或z - x = db2，z + x = 3da2，y = dab，a > 0，b > 0，(a, b ) = 1。() 當(dāng)d = 1：，a > 0，b > 0，(a, b ) = 1，3b，a, b同為奇數(shù)； () 當(dāng)d = 2：x = |b2 - 3a2|，y = 2ab，z = b2 + 3a2，a > 0，b > 0，(a, b ) = 1，3b，a, b一奇一偶。反之，易驗(yàn)證()或

13、()是原不定方程的解，且x > 0，y > 0，z > 0，(x, y) = 1。3證明不等式方程的一切正整數(shù)解可以寫成公式: ，其中 證明:由定理1知道原方程的解是， 且c， d為一奇一偶，其中， 且a， b為一奇一偶所以，是原方程的正整數(shù)解，原方程正整數(shù)的解有: ，6求方程x2 + y2 = z4的滿足(x, y ) = 1，2½x的正整數(shù)解。解：設(shè)x，y，z是x2 + y2 = z4的滿足(x, y) = 1，2½x的正整數(shù)解，那么x = 2ab，y = a2 - b2，z2 = a2 + b2，a > b > 0，(a, b) = 1，

14、a, b一奇一偶， 再由z2 = a2 + b2得a = 2uv，b = u2 - v2， z = u2 + v2 或 a = u2 - v2，b = 2uv， z = u2 + v2， u > v > 0，(u, v) = 1，u, v一奇一偶，于是得x = 4uv(u2 - v2)，y = |u4 + v4 - 6u2v2|，z = u2 + v2，u > v > 0，(u, v) = 1，u, v一奇一偶。反之，易驗(yàn)證它是原不定方程的整數(shù)解，且x > 0，y > 0，z > 0，(x, y) = 1，2½x。其中正負(fù)號(hào)可任意選取第三章

15、同余1同余的概念及其根本性質(zhì)1、 證明i假設(shè)(modm)xy(modm)、i=1，2，、，k那么(modm)特別地，假設(shè)modm，i=0，1，那么modm(ii)假設(shè)ab(modm)，kiii假設(shè)ab(modm)，d是a，b及m的任一正公因數(shù)，那么(iv)假設(shè)ab(modm)， 那么ab(modd)證明 ：i據(jù)性質(zhì)戊，由得進(jìn)一步，那么最后據(jù)性質(zhì)丁，可得：modm(ii) 據(jù)定理1，ab(modm)又據(jù)定理1，即得iii據(jù)定理1， ab(modm) 即a-b=ms(sz)，即仍據(jù)定理1，立得(iv) 據(jù)定理1， ab(modm)又故2、設(shè)正整數(shù)試證11整除的充分且必要條件是11整除證明 ：由上題

16、(i)的特殊情形立得3找出整數(shù)能被37，101整除有判別條件來(lái)。解：故正整數(shù)立得故設(shè)正整數(shù)，立得4、證明證明： 即5、假設(shè)是任一單數(shù)，那么，證明：數(shù)學(xué)歸納法設(shè) 1時(shí)， 結(jié)論成立。 2設(shè)時(shí)，結(jié)論成立，即： ，而 故時(shí)，結(jié)論也成立；時(shí)，結(jié)論也成立。證明：假設(shè)2a，n是正整數(shù)，那么º 1 (mod 2n + 2)。 (4)設(shè)a = 2k + 1，當(dāng)n = 1時(shí)，有a2 = (2k + 1)2 = 4k(k + 1) + 1 º 1 (mod 23)，即式(4)成立。設(shè)式(4)對(duì)于n = k成立，那么有º 1 (mod 2k + 2) Þ= 1 + q2k +

17、2，其中qÎZ，所以= (1 + q2k + 2)2 = 1 + q ¢2k + 3 º 1 (mod 2k + 3)，其中q ¢是某個(gè)整數(shù)。這說(shuō)明式(4)當(dāng)n = k + 1也成立。由歸納法知式(4)對(duì)所有正整數(shù)n成立。； 解：；§2 剩余類及完全剩余系1、 證明，是模的一個(gè)完全剩余類。證明：顯然對(duì)的不同取值，共有個(gè)值，故只需證這樣的個(gè)值，關(guān)于模的兩兩互不同余。假設(shè)，即或時(shí)， 結(jié)論成立。2、 假設(shè)是個(gè)兩兩互質(zhì)的正整數(shù)，分別通過(guò)模的完全剩余類，那么 通過(guò)模的完全剩余系，其中，證明：數(shù)學(xué)歸納法（1） 根據(jù)本節(jié)定理3，知時(shí)，結(jié)論成立。（2） 設(shè)對(duì)整

18、數(shù)，結(jié)論成立，即假設(shè)兩兩互質(zhì)，令，當(dāng)分別通過(guò)模的完全剩余系時(shí)，必過(guò)模的完全剩余系，其中。現(xiàn)增加使 ，令，那么易知，再令，當(dāng)過(guò)模的完全剩余系，過(guò)模的完全剩余系時(shí)，據(jù)本節(jié)定理3，必過(guò)模的完全剩余系，即對(duì)結(jié)論成立。3、i證明整數(shù)中每一個(gè)整數(shù)有而且只有一種方法表示成的形狀，其中；反之，中每一數(shù)都。 ii說(shuō)明應(yīng)用個(gè)特別的砝碼，在天平上可以量出1到H中的任意一個(gè)斤數(shù)。證明：i當(dāng)時(shí)，過(guò)模的絕對(duì)最小完全剩余系，也就是表示中的個(gè)整數(shù)，事實(shí)上，當(dāng)時(shí)，共有個(gè)值，且兩兩互不相等，否那么此即又的最大值是最小值是所以，結(jié)論成立。ii特制個(gè)砝碼分別重斤，把要稱的物體及取-1的砝碼放在天平的右盤，取1的砝碼放在左盤，那么從i

19、的結(jié)論知，當(dāng)取適當(dāng)?shù)闹禃r(shí)，可使之值等于你所要稱的物體的斤數(shù)。4、假設(shè)是K個(gè)兩兩互質(zhì)的正整數(shù)，分別過(guò)模的完全剩余系，那么通過(guò)模的完全剩余系。證明：數(shù)學(xué)歸納法1時(shí)，分別過(guò)模的完全剩余系時(shí)，共有個(gè)值，且假設(shè)，且，即時(shí)結(jié)論成立；2設(shè)當(dāng)分別過(guò)模的完全剩余系時(shí)，過(guò)模的完全剩余系。因?yàn)?，由本?jié)定理2得，亦過(guò)模的完全剩余系。當(dāng)分別過(guò)模的完全剩余系時(shí)，2有個(gè)值，且據(jù)歸納假設(shè)，假設(shè)； ，。所以過(guò)模的完全剩余系。3簡(jiǎn)化剩余系與歐拉函數(shù)1證明定理2：假設(shè)是與互質(zhì)的整數(shù)，并且兩對(duì)模不同余，那么是模的一個(gè)簡(jiǎn)化剩余系。證明： 兩對(duì)模不同余，所以它們分別取自模的不同剩余類，又恰是個(gè)與互質(zhì)的整數(shù)，即它們恰取自與?；ベ|(zhì)的全部剩余

20、類。2假設(shè)是大于1的正整數(shù)，是整數(shù)，通過(guò)的簡(jiǎn)化剩余系，那么，其中表示展布在所通過(guò)的一切值上的和式。證明：由定理3知，通過(guò)的簡(jiǎn)化剩余系：，其中0且，而。假設(shè)2，那么必是偶數(shù)，又由，得，且易見(jiàn)，故所以左邊每一項(xiàng)都存在另一項(xiàng)，使得，右邊共有對(duì)，此即。特別地，當(dāng)m=2時(shí)，。3i證明，p質(zhì)數(shù)。(ii) 證明，其中展布在a的一切正整數(shù)上的和式。證明：i因?yàn)椋?= =(ii)設(shè)是a的標(biāo)準(zhǔn)分解式，那么， = =a4假設(shè)是k個(gè)兩兩互質(zhì)的正整數(shù)， 分別通過(guò)模的簡(jiǎn)化剩余系，那么 通過(guò)模的簡(jiǎn)化剩余系，其中。證明：數(shù)學(xué)歸納法（1） 由定理4知k=2時(shí)，結(jié)論成立；（2） 設(shè)k-1時(shí)結(jié)論成立，即，分別過(guò)模時(shí)，過(guò)模的簡(jiǎn)化

21、剩余系。顯見(jiàn)，那么又由定理4知，通過(guò)模的簡(jiǎn)化剩余系，注意到：所以，通過(guò)模m的簡(jiǎn)化剩余系。歐拉定理費(fèi)馬定理及其對(duì)循環(huán)小數(shù)的應(yīng)用、如果今天是星期一，問(wèn)從今天起再過(guò)天是星期幾？解：假設(shè)被除的非負(fù)最小剩余是，那么這一天就是星期當(dāng)時(shí)是星期日，由費(fèi)馬定理得，又即這一天是星期五、求被除的余數(shù)。解：，據(jù)歐拉定理，易知又故那么由即得由以上計(jì)算，知、證明以下事實(shí)但不許用定理推論：假設(shè)是質(zhì)數(shù)，是整數(shù)，那么。由證明定理推論，然后再由定理推論證明定理。證明對(duì)應(yīng)用數(shù)學(xué)歸納法：當(dāng)時(shí)，按二項(xiàng)式展開(kāi)即得設(shè)時(shí)，結(jié)論成立，即當(dāng)時(shí)，結(jié)論成立。在的結(jié)論中，令，即得：即定理推論成立。進(jìn)一步，設(shè)，那么固對(duì)任一整數(shù)，假設(shè)，那么由上述已證性質(zhì)

22、得：存在，使故=依此類推可得假設(shè)，那么 ，定理成立。4、證明：有理數(shù)表成純循環(huán)小數(shù)的充分與必要條件是有一正數(shù)t使得同余式成立，并且使上式成立的最小正整數(shù)t就是循環(huán)節(jié)的長(zhǎng)度。證明：必要性，假設(shè)結(jié)論成立，那么由定理2知b，10=1，令t=那么據(jù)歐拉定理得；充分性，假設(shè)有正數(shù)t，滿足令t為使上式成立的最小正整數(shù)，且=且。以下參照課本51頁(yè)的證明可得：=即可表成循環(huán)小數(shù)，但循環(huán)節(jié)的長(zhǎng)度就是t。第四章 同余式 1 根本概念及一次同余式例 解同余式 解：12，45= 同余多項(xiàng)式有3個(gè)解 而原同余式為 4 與也一樣所以原同余式的3個(gè)解是 、即，1、 求以下各同余式的解 256x179 1215x560129

23、6x1125337是素?cái)?shù)， ，原同余式有唯一解。先解同余式256x1由輾轉(zhuǎn)相除法，得上述同余式的解是原同余式的解是1215，2755=5，故先解 243x112 同的方法的得其解是原同余式的解是(1296，1935)=9，故原同余式有9個(gè)解。 由144x125得原同余式的解是2求聯(lián)立同余式的解。解：據(jù)同余式的有關(guān)性質(zhì)，為所求的解。3(i)設(shè)是正整數(shù)，證明 是同余式 的解(ii)設(shè)是質(zhì)數(shù)，證明是同余式的解證明: (i) ， 有唯一解而據(jù)歐拉定理，得 ， 即 是的解(ii) 即有唯一解又 個(gè)連續(xù)整數(shù)之積必被所整除，故可令 那么即即 是的解設(shè)p是素?cái)?shù)，0 < a < p，證明：(mod

24、p)。是同余方程ax º b (mod p)的解。解：首先易知是整數(shù)，又由(a, p) = 1知方程ax º b (mod p)解唯一，故只須將(mod p)代入ax º b (mod p)驗(yàn)證它是同余方程的解即可。4設(shè)是正整數(shù)，是實(shí)數(shù)，證明同余式有解證明: 因 故同余式 必有解，(i) 假設(shè) ，那么結(jié)論成立;(ii) 假設(shè)，令，那么又假設(shè) 那么由 ，結(jié)論成立假設(shè) 令 那么 又假設(shè) 那么由即 故 結(jié)論成立。假設(shè)又令 那么 重復(fù)上述討論：即假設(shè) 那么結(jié)論成立， 假設(shè)又令 例解同余方程組解：互質(zhì)，故原方程組對(duì)模有唯一解即根據(jù)孫子定理方程組的解是注意到 故有限步后，必有

25、 其中即結(jié)論成立。孫子定理試解以下各題：（i） 十一數(shù)余三，七二數(shù)余二，十三數(shù)余一，問(wèn)本數(shù)。（ii） 二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問(wèn)本數(shù)。 楊輝：續(xù)古摘奇算法1275。解：i依題意得那么據(jù)孫子定理，上述方程組有唯一解由故原方程組的解是(ii)依題意得2、i設(shè) 是三個(gè)正整數(shù)，證明： ii設(shè) 證明：同余式組 1有解的充分與必要條件是在有解的情況下，適合1的一切整數(shù)可由下式求出：其中是適合的一個(gè)整數(shù)。應(yīng)用證明同余式組 有解的充分與必要條件是，并且有解的情況下，適合的一切整數(shù)可由下式求出：其中是適合的一個(gè)整數(shù)。證明： 即 設(shè)有解，即故此得，必要性成立；反之，設(shè)即那么由§1定理，知

26、方程必有解，設(shè)其解為，即令那么易見(jiàn)：且即有解，充分性得證。進(jìn)一步，假設(shè)有解，那么即是的公倍數(shù)，當(dāng)然也是的倍數(shù)，故假設(shè)是的一個(gè)解，那么的任一解必滿足。假設(shè)同余式組有解，那么 也有解。從而由知必有，必要性成立。下證充分性。首先，推，用歸納法易證：又由知時(shí)，充分性也成立；現(xiàn)設(shè)同余式組 有解，即。設(shè)；又由條件知，而，從而，所以，即，又由，那么同余式組，必有解 顯然，即就是同余式組的解，據(jù)歸納性原理，結(jié)論成立。后一結(jié)論由上述過(guò)程亦成立。§3 高次同余式的解數(shù)及解法1、 解同余式。解：原同余式等價(jià)于 據(jù)孫子定理，可得故原同余式共有6個(gè)解是：2、 解同余式解： 故原同余式等價(jià)于1） 先解即 得再解

27、即 設(shè) 而由孫子定理設(shè)即原四條式有4個(gè)解是§4質(zhì)數(shù)模的同余式補(bǔ)充例子：1解同余方程：() 3x11 + 2x8 + 5x4 - 1 º 0 (mod 7)；() 4x20 + 3x12 + 2x7 + 3x - 2 º 0 (mod 5)。解：() 原同余方程等價(jià)于3x5 + 5x4 + 2x2 - 1 º 0 (mod 7)，用x = 0，±1，±2，±3代入知后者無(wú)解； () 原同余方程等價(jià)于2x4 + 2x3 + 3x - 2 º 0 (mod 5)，將x = 0，±1，±2 代入，知后者

28、有解x º ±1 (mod 5)。2判定() 2x3 - x2 + 3x - 1 º 0 (mod 5)是否有三個(gè)解；() x6 + 2x5 - 4x2 + 3 º 0 (mod 5)是否有六個(gè)解？解：() 2x3 - x2 + 3x - 1 º 0 (mod 5)等價(jià)于x3 - 3x2 + 4x - 3 º 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系數(shù)不都是5的倍數(shù)，故原方程沒(méi)有三個(gè)

29、解； () 因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解。定理5 假設(shè)p是素?cái)?shù)，n½p - 1，pa那么x n º a (mod p) (14)有解的充要條件是º1 (mod p)。 (15)假設(shè)有解，那么解數(shù)為n。證明 必要性 假設(shè)方程(14)有解x0，那么px0，由Fermat定理，得到= x0p - 1 º1 (mod p)。充分性 假設(shè)式(15)成立，那么其中P(x)是關(guān)于x的整系數(shù)多項(xiàng)式。由定理4可知同余方程(14)有n個(gè)解。證畢。1、 設(shè)， ， 證明同余式 有解的充分必要條件是，并且在有解的情況下就有個(gè)解。證明：設(shè)那么但那么由 可得。它有

30、個(gè)解。 令那么無(wú)多于個(gè)解，而 恰有個(gè)解，必有個(gè)解。2設(shè)n是整數(shù)，a，m=1，且同余式有一解，證明這個(gè)同余式的一切解可以表成 其中y是同余式的解。證明：設(shè)均是的解， 那么， a，m=1 ， ，m= (，m) = 1 那么由第三章定理33知，必存在y，使 ， 故原同余式的任一解可表示為而y滿足3設(shè)(a, m) = 1，k與m是正整數(shù)，又設(shè)x0k º a (mod m)，證明同余方程xk º a(mod m)的一切解x都可以表示成x º yx0 (mod m)，其中y滿足同余方程yk º 1 (mod m)。解：設(shè)x1是xk º a(mod m)的任

31、意一個(gè)解，那么一次同余方程yx0 º x1 (mod m)有解y，再由yka º ykx0k º (yx0)k º x1k º a (mod m)得yk º 1 (mod m)，即x1可以表示成x º yx0 (mod m)，其中y滿足同余方程yk º 1 (mod m)；反之，易知如此形式的x是xk º a(mod m)的解。第五章 二次同余式與平方剩余§1 一般二次同余式1、 在同余式中，假設(shè)，試求出它的一切解來(lái)。解：假設(shè)，那么，上同余式即為從而，即有。易見(jiàn)，當(dāng)為偶數(shù)時(shí)，那么，上同余式有解：

32、，共有個(gè)解當(dāng)為奇數(shù)時(shí)，上同余式有解：，共有個(gè)解。2、證明：同余式 有解的充分必要條件是 有解，并且前一同余式的一切解可由后一同余式的解導(dǎo)出。證明：因，故用乘后再配方，即得仍記為，即有由以上討論即知假設(shè)為的解，那么為的解，必要性得證。反之，假設(shè)有一解，即有：由于，故有解即有：即有：由，即有：即為的解，充分性得證。由充分性的討論即知的解可由的解導(dǎo)出。§2 單質(zhì)數(shù)的平方剩余與平方非剩余1、 求出模的平方剩余與平方非剩余。解：，由書中定理2知，模的簡(jiǎn)化剩余系中個(gè)平方剩余分別與序列例2試判斷下述同余方程是否是有解。 1 2 3中之一數(shù)同余，而 故模37的平方剩余為： 1，3，4，7，9，10，

33、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é)果證明:模的簡(jiǎn)化剩余系中一定有平方剩余及平方非剩余存在， 證明兩個(gè)平方剩余的乘積是平方剩余;平方剩余與平方非剩余的乘積是平方非剩余。 應(yīng)用、證明：模的簡(jiǎn)化剩余系中平方剩余與平方非剩余的個(gè)數(shù)各為。證明：因?yàn)?為模的簡(jiǎn)化剩余系中的平方剩余。假設(shè)模的簡(jiǎn)化剩余系中均為平方剩余，考慮模的絕對(duì)最小簡(jiǎn)化剩余系：它們的平方為模下的個(gè)數(shù)： 由假設(shè)模的簡(jiǎn)化剩余系中任一個(gè)數(shù)與上個(gè)數(shù)同余，而模的簡(jiǎn)化剩

34、余系中有個(gè)數(shù)，故必有兩個(gè)互相同余，矛盾。從而必有平方非剩余存在。假設(shè)為平方剩余，那么故從而也為平方剩余。假設(shè)為平方剩余，為平方非剩余，那么故從而為平方非剩余。設(shè)為模的簡(jiǎn)化剩余系中的平方剩余；為模的簡(jiǎn)化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。3證明：同余式，的解是 ，其中 證明：假設(shè)有解，那么有解， 設(shè)其解是：，即有： ，令而 ， 為整數(shù)由此兩式即得： 兩式相乘得： 取使得： 那么 故其解為 4證明同余式 的解是 證明：首先我們證明對(duì)任意： 有下式： 因?yàn)?，于是 因此由威爾生定理得： 其次由，可令 ，代入上式即有 故原同余式的解為 §3

35、 勒讓得符號(hào)1用本節(jié)方法判斷以下同余式是否有解 其中503，563，769，1013都是質(zhì)數(shù) 解：，有解。，有解。 ，有解。2、求出以為平方剩余的質(zhì)數(shù)的一般表達(dá)式；以為平方非剩余的質(zhì)數(shù)的一般表達(dá)式。解：為模平方剩余時(shí)，必有，必有，故，必有，故為模平方非剩余時(shí)，必有，必有，故，必有，故3、設(shè)是正整數(shù)，及都是質(zhì)數(shù)，說(shuō)明由此證明：。證明：當(dāng)時(shí)，由本節(jié)定理1的推論知為平方剩余，應(yīng)用歐拉判別條件即有由，即得出而都是形如的素?cái)?shù)，并且，所以。§4 前節(jié)定理的證明1、 求以為平方剩余的質(zhì)數(shù)的一般表達(dá)式，什么質(zhì)數(shù)以為平方非剩余？解：由互反律 因此當(dāng)它們同為或同時(shí)為時(shí)，一為，一為時(shí)，顯然，當(dāng)為偶數(shù)，而時(shí)

36、，當(dāng)是奇數(shù)，即時(shí)，。再因?yàn)槭瞧尜|(zhì)數(shù)，關(guān)于模我們有或，當(dāng)時(shí)，當(dāng)時(shí)，這樣為平方剩余時(shí)，為下方程組的解或由孫子定理，即可知或，立即當(dāng)時(shí)，為平方剩余。為平方非剩余時(shí)，為下方程組的解或由孫子定理，即可知或，立即當(dāng)時(shí)，為平方非剩余。因?yàn)楫?dāng)為偶數(shù)，或?yàn)槠鏀?shù)，時(shí)，即或時(shí)，為平方剩余，類似或，為平方非剩余。2、求以為最小平方非剩余的質(zhì)數(shù)的一般表達(dá)式。解：由上題知以為平方非剩余的質(zhì)數(shù)滿足：又由為模的最小平方非剩余，故從而§3推證滿足的素?cái)?shù)形如，其中只有滿足故或時(shí)，為它的最小平方非剩余。§5 雅可比符號(hào)1、 判斷§3習(xí)題1所列各同余式是否有解。略2、 求出以下同余式的解數(shù)：，其中是一個(gè)

37、質(zhì)數(shù)。解：，故故，即的解數(shù)為0 ，故解數(shù)為23 在有解的情況下，應(yīng)用定理1，求同余式，的解。在有解的情況下，應(yīng)用 §2 定理1及§3定理1的推論，求同余式，的解。解：同余式有解，故 由知故即為原同余式的解。 由知，故故因此或假設(shè)前式成立，那末 即 假設(shè)那么原同余式的解是 即 為原同余式的解。 假設(shè)后式成立，那末 由§3定理1的推論知，2是模p的平方剩余，即于是： 假設(shè)那么原同余式的解是故為原同余式的解§6 合數(shù)模的情形1. 解同余式 ，解：從同余式 得令代入得出從而即有故，再令代入 得出 ， 即從而 故 所以 為所給同余式的解從而所有的解為：，故有四解記

38、代入，即有：解得記，代入即有：，解得：又記，代入即有，解得: 故為其一解其余三解為： 2證明同余式與同余式等價(jià)，應(yīng)用舉出一個(gè)求同余式的一切解的方法。證明：顯然 記有解，等價(jià)于方程組有解易見(jiàn)的解為的解為的解為或二者不能同時(shí)成立，否那么矛盾故它有兩個(gè)解，聯(lián)立方程組即可求出一切解。第六章 原根與指標(biāo)1. 設(shè)p是單質(zhì)數(shù)，a是大于1的整數(shù)，證明:(i)的奇質(zhì)數(shù)q是a-1的因數(shù)或是形如2px+1的整數(shù)，其中x是整數(shù)(ii) 的單質(zhì)因數(shù)是a+1的因數(shù)或是形如2px+1的整數(shù)，其中x是整數(shù)證明(i)設(shè) 那么設(shè)a對(duì)模q的質(zhì)數(shù)是 是質(zhì)數(shù) 從而或p假設(shè)，那么，故;假設(shè)，而，q-1為偶數(shù)，記q-1=2x，那么，又假設(shè)

39、故q=2px+1得證。(ii)設(shè)q為的奇質(zhì)因數(shù)，那么從而，從而a對(duì)模q的指數(shù)故，2，p，2p之一假設(shè)，那么，從而 即有，不可能，故假設(shè)，那么，而(否那么) 故假設(shè)，那么，而有，不可能假設(shè)，那么由，q12m記mpx，那么q2px+1，得證2. 設(shè)對(duì)模m的指數(shù)是，試證對(duì)模m的指數(shù)是證明：設(shè)對(duì)模m的指數(shù)為，那么 而，股反之故，從而=得證例1 求1，2，3，4，5，6對(duì)模7的指數(shù)。根據(jù)定義1直接計(jì)算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，d7(4) = 3，d7(5) = 6，d7(6) = 2。例1中的結(jié)果可列表如下：a123456d7(a)136362這樣的表稱為指數(shù)表。

40、這個(gè)表就是模7的指數(shù)表。下面是模10的指數(shù)表：a1379d10(a)14421寫出模11的指數(shù)表。解：經(jīng)計(jì)算得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 º 3，5 (mod 14)是模14的全部原根。1求模29的最小正原根。解：因j(29) = 28 = 22×7，由知2是模29的最小正原根

41、。2分別求模293和模2×293的原根。解：由2是模29的原根及229 - 1 = 228 = 2281 (mod 292)知2是模293的原根；由2是模293的原根及2是偶數(shù)知2 + 293是模2×293的原根。3解同余方程：x12 º 16 (mod 17)。解：易得3是模17的原根，3ii = 0, 1, 2, L, 15構(gòu)成模17的簡(jiǎn)化剩余系，列表為i 0 1 2 3 4 5 6 73i (mod 17) 1 3 9 10 13 5 15 11i 8 9 10 11 12 13 14 153i (mod 17) 16 14 8 7 4 12 2 6由上表知

42、38 º 16 (mod 17)，設(shè)x º 5 y (mod 17)，那么12y º 8 (mod 16)，由此解得y1 º 2，y2 º 6，y3 º 10，y4 º 14 (mod 16)，查上表得x1 º 9，x2 º 15，x3 º 8，x4 º 2 (mod 17)。3 指標(biāo)及n次剩余1設(shè) 是的一切不同的質(zhì)因數(shù)，證明g是模m的一個(gè)原根的充要條件是g對(duì)模m的次非剩余。 證明：必要性，設(shè)g為模m的一個(gè)原根 由2 Th5 知 假設(shè)g為模m的次剩余，那么存在，使得 又由歐拉定理 故

43、，矛盾！充分性，假設(shè)g不為模m的一個(gè)原根，由2 Th5 知存在，使得： 設(shè)為模m的一個(gè)原根，那么對(duì)上式兩邊關(guān)于取指標(biāo)： 記 ，那么由指標(biāo)的定義即有： 故 即為同余式 的解從而g為次剩余，矛盾。2證明10是模17及模257質(zhì)數(shù)的原根，并由此證明把化成循環(huán)小數(shù)時(shí)，循環(huán)節(jié)的長(zhǎng)度分別是16及256證明：，它的有且只有質(zhì)因子2，而 從而10不是模17的平方剩余，由上題知10是模17的原根。，由且僅有質(zhì)因子2，而故同上理10也是模257的原根。由3§4的證明可知，的循環(huán)節(jié)的長(zhǎng)度，t，這是10關(guān)于模17，模257的指數(shù)，從而 t=16，256 證畢3試?yán)弥笜?biāo)表解同余式解：同余式等價(jià)于：查表知，故

44、： 由于，故上式由 5個(gè)解，解之得：查表知：原同余式的5個(gè)解為： 4設(shè)模mm>2的原根是存在的，試證對(duì)模m的任一原根來(lái)說(shuō)，的指標(biāo)總是證明：模m的原根存在，故m=4，或 設(shè)為模m的一個(gè)原根，那么 從而 假設(shè)m=4，那么模m有且只有一個(gè)原根3， ， 故的指標(biāo)為假設(shè)，為奇質(zhì)數(shù)，那么由知或但二者不能同時(shí)成立，否那么，矛盾!假設(shè)又由*知 mod m，與的指數(shù)為矛盾。從而，從而 mod m故-1的指標(biāo)為。 假設(shè)，為的原根，那么為奇數(shù) 類似于的討論，我們有，從而 從而 mod m故-1的指標(biāo)為。5、設(shè)，是模的兩個(gè)原根，試證： mod ； mod 。證明：由指標(biāo)的定義知： mod m兩邊對(duì)原根取指標(biāo)：

45、mod 故 mod 由指標(biāo)的定義知： mod m兩邊對(duì)原根取指標(biāo)： mod 故 mod 。 證畢第九章數(shù)論函數(shù)§1 可乘函數(shù)1設(shè)是一個(gè)可乘函數(shù)，證明也是一個(gè)可乘函數(shù)由此說(shuō)明是可乘函數(shù)證明：首先我們證明：設(shè)，假設(shè)跑過(guò)的全部因子，跑過(guò)的全部因子，那么跑過(guò)的全部因子，事實(shí)上，因?yàn)?，故，且?dāng)，時(shí)，由于，得，反之任給，由于，設(shè)，顯然因此故為一個(gè)可乘函數(shù)(此為65頁(yè))假設(shè)，它為可乘函數(shù)，且假設(shè)，它為可乘函數(shù)，且故為可乘函數(shù)2設(shè)是一個(gè)定義在一切正態(tài)數(shù)的函數(shù)，并且是一個(gè)可乘函數(shù)，證明是可乘函數(shù)證明：反證，假設(shè)不是可乘函數(shù)，那么存在一對(duì)正態(tài)數(shù)，使得，于是我們可以選擇這樣一對(duì)，使得最小假設(shè)，那么，即，又，為可乘函數(shù)，故有矛盾！假設(shè)，那么對(duì)所有正態(tài)數(shù)對(duì)，有 于是有： = =因?yàn)?，故此與 為可乘函數(shù)矛盾！3證明：證明：首先易證，假設(shè)d為的正約數(shù)，那么a的完全剩余系中與的最大公約數(shù)是d的個(gè)數(shù)為。其次，假設(shè)為的所有正約數(shù)。那么也是的所有正約數(shù)，于是 最后，在的完