《《初等數(shù)論》（閔嗣鶴、嚴士?。┑谌嬲n后習題解答》由會員分享，可在線閱讀，更多相關(guān)《《初等數(shù)論》（閔嗣鶴、嚴士?。┑谌嬲n后習題解答（63頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第一章 整數(shù)的可除性 §1 整除的概念·帶余除法 1．證明定理3 定理3 假設(shè)都是得倍數(shù)，是任意n個整數(shù)，那么是得倍數(shù)． 證明： 都是的倍數(shù)。 存在個整數(shù)使 又是任意個整數(shù) 即是的整數(shù) 2．證明 證明 又，是連續(xù)的三個整數(shù) 故 從而可知 3．假設(shè)是形如〔x，y是任意整數(shù)，a，b是兩不全為零的整數(shù)〕的數(shù)中最小整數(shù)，那么． 證： 不全為 在整數(shù)集合中存在正整數(shù)，因而有形如的最小整數(shù) ，由帶余除法有 那么，由是中的最小整數(shù)知 〔為任意整數(shù)〕 又有， 故 4．假設(shè)a，b是任意二整數(shù)

2、，且，證明：存在兩個整數(shù)s，t使得 成立，并且當b是奇數(shù)時，s，t是唯一存在的．當b是偶數(shù)時結(jié)果如何？ 證：作序列那么必在此序列的某兩項之間 即存在一個整數(shù)，使成立 當為偶數(shù)時，假設(shè)那么令，那么有 假設(shè) 那么令，那么同樣有 當為奇數(shù)時，假設(shè)那么令，那么有 假設(shè) ，那么令，那么同樣有，綜上所述，存在性得證． 下證唯一性 當為奇數(shù)時，設(shè)那么 而 矛盾 故 當為偶數(shù)時，不唯一，舉例如下：此時為整數(shù) §2 最大公因數(shù)與輾轉(zhuǎn)相除法 推論4.1 a，b的公因數(shù)與〔a，b〕的因數(shù)相同． 證：設(shè)是a，b的任一公因數(shù)，|a，|b 由帶余除法 |，

3、|，┄, |, 即是的因數(shù)。 反過來|且|，假設(shè)那么，所以的因數(shù)都是的公因數(shù)，從而的公因數(shù)與的因數(shù)相同。 2．證明：見本書P2，P3第3題證明。 3．應(yīng)用§1習題4證明任意兩整數(shù)的最大公因數(shù)存在，并說明其求法，試用你的所說的求法及輾轉(zhuǎn)相除法實際算出〔76501，9719〕． 解：有§1習題4知： 使。， ，使如此類推知： 且 而b是一個有限數(shù)，使 ，存在其求法為： 4．證明本節(jié)〔1〕式中的 證：由P3§1習題4知在〔1〕式中有 ，而 ， ，即 §3 整除的進一步性質(zhì)及最小公倍數(shù) 1．證明兩整數(shù)a，b互質(zhì)的充分與

4、必要條件是：存在兩個整數(shù)s，t滿足條件． 證明 必要性。假設(shè)，那么由推論知存在兩個整數(shù)s，t滿足：， 充分性。假設(shè)存在整數(shù)s，t使as+bt=1，那么a，b不全為0。 又因為，所以 即。 又， 2．證明定理3 定理3 證：設(shè)，那么 ∴又設(shè) 那么。反之假設(shè)，那么， 從而，即= 3．設(shè) 〔1〕 是一個整數(shù)系數(shù)多項式且，都不是零，那么〔1〕的根只能是以的因數(shù)作分子以為分母的既約分數(shù)，并由此推出不是有理數(shù)． 證：設(shè)〔1〕的任一有理根為，。那么 〔2〕 由， 所以q整除上式的右端，所以，又， 所以； 又由〔2〕有

5、 因為p整除上式的右端，所以 ，，所以 故〔1〕的有理根為，且。 假設(shè)為有理數(shù)，，次方程為整系數(shù)方程，那么由上述結(jié)論，可知其有有理根只能是 ，這與為其有理根矛盾。故為無理數(shù)。 另證，設(shè)為有理數(shù)=，那么 但由知，矛盾，故不是有理數(shù)。 §4 質(zhì)數(shù)·算術(shù)根本定理 1．試造不超過100的質(zhì)數(shù)表 解：用Eratosthenes篩選法 〔1〕算出a 〔2〕10內(nèi)的質(zhì)數(shù)為：2，3，5，7 〔3〕劃掉2，3，5，7的倍數(shù)，剩下的是100內(nèi)的素數(shù) 將不超過100的正整數(shù)排列如下： 1 2 3 4 5 6 7 8 9 10 11 12 13

6、 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

7、 89 90 91 92 93 94 95 96 97 98 99 100 解：因為8|848，所以， 又8|856，所以8|B，， 又4|32，所以4|C， 又9|〔3+2+3+4+3+3〕，所以9|D，， 又9|〔3+5+9+3+7〕，所以9|E， 又 所以； 同理有。 3．證明推論3.3并推廣到n個正整數(shù)的情形． 推論3.3 設(shè)a，b是任意兩個正整數(shù)，且 ，，， ，，， 那么，， 其中，， 證：， ∴ ∴ ，. ∴ ，又顯然 ∴ ，同理可得， 推廣 設(shè),, (其中為質(zhì)數(shù)為任意n個正整數(shù))，

8、 那么 4．應(yīng)用推論3.3證明§3的定理4〔ii〕 證：設(shè)， 其中p1, p2, L, pk是互不相同的素數(shù)，ai，bi〔1 ￡ i ￡ k〕都是非負整數(shù)，有 由此知(a, b)[a, b] ==ab；從而有． ５．假設(shè)是質(zhì)數(shù)〔n>1〕，那么n是2的方冪． 證：〔反證法〕設(shè)為奇數(shù)〕， 那么 ∵ ， ∴ 為合數(shù)矛盾，故ｎ一定為２的方冪． §5 函數(shù)[x],{x}及其在數(shù)論中的一個應(yīng)用 1．求30！的標準分解式． 解：30內(nèi)的素數(shù)為2，3，5，7，11，13，17，19，23，29 ， ， ， ∴ 2．設(shè)n是任一正整數(shù)，a

9、是實數(shù)，證明： (i) (ii) 證：(i)設(shè).那么由性質(zhì)II知, 所以 , 所以，所以，又在ｍ與ｍ+１之間只有唯一整數(shù)ｍ，所以． (ii) [證法一]設(shè), 那么 ①當時, ; ②當時,; [證法二] 令, 是以為周期的函數(shù)。 又當， 即。 [評注]：[證一]充分表達了 常規(guī)方法的特點，而[證二]那么表現(xiàn)了較高的技巧。 3．設(shè)，是任意二實數(shù)，證明： (i) 或 (ii) 證明：〔i〕由高斯函數(shù)[x]的定義有 。那么 當 當

10、 故 〔ii〕設(shè)， 那么有 下面分兩個區(qū)間討論： ①假設(shè)，那么，所以，所以 ②假設(shè)，那么，所以。 所以 〔ii〕〔證法2〕由于，對稱，不妨設(shè) 4. (i) 設(shè)函數(shù)在閉區(qū)間上是連續(xù)的，并且非負，證明:和式 表示平面區(qū)域，內(nèi)的整點〔整數(shù)坐標的點〕的個數(shù). (ii) 設(shè)p，q是兩個互質(zhì)的單正整數(shù)，證明： (iii) 設(shè)，T 是區(qū)域 內(nèi)的整點數(shù)，證明： (iv) 設(shè)，T 是區(qū)域，， 內(nèi)的整點數(shù)，證明： 證明：(略) 5. 設(shè)任一正整數(shù)，且，p 是質(zhì)數(shù)，，證明：在的標準分解式中，質(zhì)因數(shù)p的指數(shù)是 其中.

11、證明：在的標準分解式中，質(zhì)因數(shù)p的指數(shù)有限，即 ， 所以 而 第二章 不定方程 §2．1 習題 1、解以下不定方程 解： 原方程等價于： 顯然它有一個整數(shù)解 ， 故一般解為 原方程等價于： 顯然它有一個整數(shù)解 故一般解為 2、把100分成兩份，使一份可被整除，一份可被整除。 解：依題意 即求 的正整數(shù)解，解得 一般解是： 但除 外無其他正整數(shù)解，故有且只有 3、證明：二元一次不定方程 的非負整數(shù)解為 或 證明：當時，原方程沒有整數(shù)解，而 故命題正確 當時，原

12、方程有且只有一個非負整數(shù)解 而 因為 所以 原方程有整數(shù)解 其中，由于，故中一正一負，可設(shè) 原方程的一般解是： 要求， 僅當 是整數(shù)時，才能取 ，否那么 故這個不等式的整數(shù)解個數(shù) 是 ： 當是整數(shù)時 因而 當 不是整數(shù)時 因而 所以 證明2：二元一次不定方程ax + by = N的一切整數(shù)解為，t?Z，于是由x 3 0，y 3 0得，但區(qū)間的長度是，故此區(qū)間內(nèi)的整數(shù)個數(shù)為+ 1。 ： 4、證明：二元一次不定方程 ，當 時有非負整數(shù)解， 那么不然。 證明：先證后一點，當

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

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

15、1。 解：設(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 = 1：，a > 0，b > 0，(a, b ) = 1，3b，a, b同為奇數(shù)； (ⅱ) 當d = 2：x = |b2 - 3a2|，y = 2ab，z = b2 + 3a2，a > 0，b > 0，(a, b ) = 1，3b，a, b一奇一偶。反之，易驗證(ⅰ)或(ⅱ)是原不定方

16、程的解，且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,

17、b) = 1，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一奇一偶。反之，易驗證它是原不定方程的整數(shù)解，且x > 0，y > 0，z > 0，(x, y) = 1，2?x。 其中正負號可任意選取． 第三章 同余 1同余的概念及其

18、根本性質(zhì) 1、 證明〔i〕假設(shè)(modm) xy(modm)、i=1，2，、、、，k 那么(modm) 特別地，假設(shè)〔modm〕，i=0，1，那么 〔modm〕 (ii)假設(shè)ab(modm)，k 〔iii〕假設(shè)ab(modm)，d是a，b及m的任一正公因數(shù)，那么 (iv)假設(shè)ab(modm)， 那么ab(modd)． 證明 ：〔i〕據(jù)性質(zhì)戊，由 得 進一步，那么 最后據(jù)性質(zhì)丁，可得： 〔modm〕 (ii) 據(jù)定理1，ab(modm) 又據(jù)定理1，即得 〔iii〕據(jù)定理1， ab(modm) 即a-b=ms(sz) ，即 仍據(jù)定理1，立得 (iv)

19、 據(jù)定理1， ab(modm) 又 故 2、設(shè)正整數(shù) 試證11整除的充分且必要條件是11整除 證明 ：由上題(i)的特殊情形立得 ． 3．找出整數(shù)能被37，101整除有判別條件來。 解： 故正整數(shù) 立得 故設(shè)正整數(shù)， 立得 4、證明｜ 證明：∵ ∴ ∴ 即∣ 5、假設(shè)是任一單數(shù)，那么， 證明：〔數(shù)學歸納法〕設(shè) 〔1〕時，， 結(jié)論成立。 〔2〕設(shè)時，結(jié)論成立，即： ， 而 故時，結(jié)論也成立；

20、∴時，結(jié)論也成立。 證明：假設(shè)2a，n是正整數(shù)，那么o 1 (mod 2n + 2)。 (4) 設(shè)a = 2k + 1，當n = 1時，有 a2 = (2k + 1)2 = 4k(k + 1) + 1 o 1 (mod 23)， 即式(4)成立。 設(shè)式(4)對于n = k成立，那么有 o 1 (mod 2k + 2) T= 1 + q2k + 2， 其中q?Z，所以 = (1 + q2k + 2)2 = 1 + q ￠2k + 3 o 1 (mod 2k + 3)， 其中q ￠是某個整數(shù)。這說明式(4)當n = k + 1也成立。 由歸納法知式(4)對所有正

21、整數(shù)n成立。 ； 解：； §2 剩余類及完全剩余系 1、 證明，，是模的一個完全剩余類。 證明：顯然對的不同取值，共有個值，故只需證這樣的個值，關(guān)于模的兩兩互不同余。 假設(shè) ∣，即 ∴或時， ．結(jié)論成立。 2、 假設(shè)是個兩兩互質(zhì)的正整數(shù)，分別通過模的完全剩余類，那么 通過模的完全剩余系，其中， 證明：〔數(shù)學歸納法〕 （1） 根據(jù)本節(jié)定理3，知時，結(jié)論成立。 （2） 設(shè)對整數(shù)，結(jié)論成立，即假設(shè)兩兩互質(zhì)，令，當分別通過模的完全剩余系時，必過模 的完全剩余系，其中。 現(xiàn)增加使 ， 令，， 那么易

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

23、當?shù)闹禃r，可使之值等于你所要稱的物體的斤數(shù)。 4、假設(shè)是K個兩兩互質(zhì)的正整數(shù)，分別過模的完全剩余系，那么 ? 通過模的完全剩余系。 證明：〔數(shù)學歸納法〕 〔1〕時，分別過模的完全剩余系時， 共有個值，且假設(shè) ，且 ，，即時結(jié)論成立； 〔2〕設(shè)當分別過模的完全剩余系時， 過模的完全剩余系。 因為，由本節(jié)定理2得， 亦過模的完全剩余系。 當分別過模的完全剩余系時， 2有個值，且據(jù)歸納假設(shè)， 假設(shè) ； ，，…， ，，…，。 所以過模的完全剩余系。 3．簡化剩余系與歐拉函數(shù) 1．證明定理2：假設(shè)是與互質(zhì)的

24、整數(shù)， 并且兩對模不同余，那么是模的一個簡化剩余系。 證明： 兩對模不同余，所以它們分別取自模的不同剩余類， 又恰是個與互質(zhì)的整數(shù)，即它們恰取自與?；ベ|(zhì)的全部剩余類。 2．假設(shè)是大于1的正整數(shù)，是整數(shù)，，通過的簡化剩余系， 那么，其中表示展布在所通過的一切值上的和式。 證明：由定理3知，通過的簡化剩余系： ，其中0＜＜且， 而〔〕。 假設(shè)＞2，那么必是偶數(shù)，又由， 得，且易見， 故 所以 左邊每一項都存在另一項， 使得，右邊共有對， 此即。 特別地，當m=2時，。 3．〔i〕證明，p質(zhì)數(shù)。 (ii) 證明，其中展布在a的一切正整數(shù)上的和式。 證明：〔i

25、〕因為， 所以 = = (ii)設(shè)是a的標準分解式， 那么， = =a 4．假設(shè)是k個兩兩互質(zhì)的正整數(shù)， 分別通過模的簡化剩余系，那么 通過模的簡化剩余系，其中。 證明：〔數(shù)學歸納法〕 （1） 由定理4知k=2時，結(jié)論成立； （2） 設(shè)k-1時結(jié)論成立，即，分別過模時， 過模的簡化剩余系。 顯見，那么又由定理4知，通過模的簡化剩余系，注意到： 所以，通過模m的簡化剩余系。 ．歐拉定理費馬定理及其對循環(huán)小數(shù)的應(yīng)用 １、如果今天是星期一，問從今天起再過天是星期幾？ 解：假設(shè)被除的非負最

26、小剩余是，那么這一天就是星期〔當時是星期日〕． ，由費馬定理得， 又 即這一天是星期五． ２、求被除的余數(shù)。 解：， 據(jù)歐拉定理，易知 　　　　　　　　　　　　〔１〕 又 故　　 那么?。伞玻薄臣吹? ． 由以上計算，知?。? ． ３、證明以下事實但不許用定理１推論：假設(shè)是質(zhì)數(shù)，是整數(shù)，那么。 由證明定理１推論，然后再由定理１推論證明定理１。 證明　對應(yīng)用數(shù)學歸納法： 當時，按二項式展開即得 設(shè)時，結(jié)論成立，即 當時， 結(jié)論成立。 在的結(jié)論中，令，即得： 　　　　　 即定理１推論成立。 進一步，設(shè)，那么　 固對任一整數(shù)，假

27、設(shè)，那么由上述已證性質(zhì)得： 存在，使 故=〔〕 依此類推可得． 假設(shè)，那么 ，定理成立。 4、證明：有理數(shù)表成純循環(huán)小數(shù)的充分與必要條件是有一正數(shù)t使得同余式成立，并且使上式成立的最小正整數(shù)t就是循環(huán)節(jié)的長度。 證明：必要性，假設(shè)結(jié)論成立，那么由定理2知〔b，10〕=1， 令t=那么據(jù)歐拉定理得； 充分性，假設(shè)有正數(shù)t，滿足 令t為使上式成立的最小正整數(shù)，且= 且。 以下參照課本51頁的證明可得： =即可表成循環(huán)小數(shù)，但循環(huán)節(jié)的長度就是t。 第四章 同余式 1 根本概念及一次同余式 例 解同余式 解：〔12，45〕=

28、 同余多項式有3個解 而原同余式為 4 與也一樣 所以原同余式的3個解是 〔ｔ＝０、１、２〕 即，，　 1、 求以下各同余式的解 256x179 1215x560 1296x1125 337是素數(shù)， ，原同余式有唯一解。 先解同余式256x1 由輾轉(zhuǎn)相除法，得 上述同余式的解是 原同余式的解是 〔1215，2755〕=5，故先解 243x112 同的方法的得其解是 原同余式的解是 (1296，1935)=9，故原同余式有9個解。

29、 由144x125得 原同余式的解是 2．求聯(lián)立同余式的解。 解：據(jù)同余式的有關(guān)性質(zhì)， 為所求的解。 3．(i)設(shè)是正整數(shù)，．證明 是同余式 的解 (ii)設(shè)是質(zhì)數(shù)，，證明 是同余式的解． 證明: (i) ， 有唯一解． 而據(jù)歐拉定理，得 ， 即 是的解． (ii) 即有唯一解 又 個連續(xù)整數(shù)之積必被所整除， 故可令 那么 即 即 是的解． 設(shè)p是素數(shù)，0 < a < p，證明： (mod p)。 是同余方程ax o b (mod p)的解。 解：首先易知是整數(shù)，又由(a, p)

30、 = 1知方程ax o b (mod p)解唯一，故只須將(mod p)代入ax o b (mod p)驗證它是同余方程的解即可。 4．設(shè)是正整數(shù)，是實數(shù)，，證明同余式 有解． 證明: 因 故同余式 必有解， (i) 假設(shè) ，那么結(jié)論成立; (ii) 假設(shè)，令，， 那么 又假設(shè) 那么由 ，結(jié)論成立． 假設(shè) 令 那么 又假設(shè) 那么由 即 故 結(jié)論成立。 假設(shè)又令 那么 重復(fù)上述討論：即假設(shè) 那么結(jié)論成立， 假設(shè)又令 `````` 例解同余方程組 解：互質(zhì)，故原方程組對模有唯一

31、解 即 根據(jù)孫子定理方程組的解是 注意到 故有限步后，必有 其中即結(jié)論成立。 孫子定理 試解以下各題： （i） 十一數(shù)余三，七二數(shù)余二，十三數(shù)余一，問本數(shù)。 （ii） 二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問本數(shù)。 〔楊輝：續(xù)古摘奇算法〔1275〕〕。 解：〔i〕依題意得 那么據(jù)孫子定理，上述方程組有唯一解 由 故原方程組的解是 (ii)依題意得 2、〔i〕設(shè) 是三個正整數(shù)，證明： ． 〔ii〕設(shè) 證明：同余式組 〔1〕 有解的充分與必要條件是 在有解的情

32、況下，適合〔1〕的一切整數(shù)可由下式求出： 其中是適合的一個整數(shù)。 應(yīng)用證明同余式組 有解的充分與必要條件是，并且有解的情況下，適合的一切整數(shù)可由下式求出： 其中是適合的一個整數(shù)。 證明： 即 設(shè)有解，即 故此得，必要性成立； 反之，設(shè)即 那么由§1定理，知方程必有解， 設(shè)其解為，即 令那么易見： 且 即有解，充分性得證。 進一步，假設(shè)有解，那么 即是的公倍數(shù)，當然也是的倍數(shù)， 故假設(shè)是的一個解，那么的任一解必滿足 。 假設(shè)同余式組有解， 那么 也有解。從而由知必有 ，必要性成立。 下證

33、充分性。首先，推，用歸納法易證： 又由知時，充分性也成立； 現(xiàn)設(shè)同余式組 有解， 即。 設(shè)；又由條件知， 而，從而， 所以， 即， 又由，那么同余式組， 必有解 〔※〕 顯然，即〔※〕就是同余式組的解，據(jù)歸納性原理，結(jié)論成立。后一結(jié)論由上述過程亦成立。 §3 高次同余式的解數(shù)及解法 1、 解同余式。 解：原同余式等價于 據(jù)孫子定理，可得 故原同余式共有6個解是： 2、 解同余式 解： 故原同余式等價于 1） 先解 即 得 ②再解 即

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

35、±1 (mod 5)。 2．判定 (ⅰ) 2x3 - x2 + 3x - 1 o 0 (mod 5)是否有三個解； (ⅱ) x6 + 2x5 - 4x2 + 3 o 0 (mod 5)是否有六個解？ 解：(ⅰ) 2x3 - x2 + 3x - 1 o 0 (mod 5)等價于x3 - 3x2 + 4x - 3 o 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系數(shù)不都是5的倍數(shù)，故原方程沒有三個解； (ⅱ) 因為這是對模5的同余方程

36、，故原方程不可能有六個解。 定理5 假設(shè)p是素數(shù)，n?p - 1，pa那么 x n o a (mod p) (14) 有解的充要條件是 o1 (mod p)。 (15) 假設(shè)有解，那么解數(shù)為n。 證明 必要性 假設(shè)方程(14)有解x0，那么px0，由Fermat定理，得到 = x0p - 1 o1 (mod p)。 充分性 假設(shè)式(15)成立，那么 其中P(x)是關(guān)于x的整系數(shù)多項式。由定理4可知同余方程(14)有n個解。證畢。 1、 設(shè)︱， ， ．證明同余式

37、 有解的充分必要條件是，并且在有解的情況下就有個解。 證明： 設(shè) 那么 但 那么由 可得。 它有個解。 ︱ 令 那么 無多于個解，而 恰有個解，必有個解。 2．設(shè)n是整數(shù)，〔a，m〕=1，且同余式 有一解，證明這個同余式的一切解可以 表成 其中y是同余式的解。 證明：設(shè)均是的解， 那么， 〔a，m〕=1 ， 〔，m〕= (，m) = 1 那么由第三章定理3．3知，必存在y，使 ， ． 故原同余式的任一解可表示為 而y滿足 3．設(shè)(

38、a, m) = 1，k與m是正整數(shù)，又設(shè)x0k o a (mod m)，證明同余方程 xk o a(mod m) 的一切解x都可以表示成x o yx0 (mod m)，其中y滿足同余方程yk o 1 (mod m)。 解：設(shè)x1是xk o a(mod m)的任意一個解，那么一次同余方程yx0 o x1 (mod m)有解y，再由yka o ykx0k o (yx0)k o x1k o a (mod m)得yk o 1 (mod m)，即x1可以表示成x o yx0 (mod m)，其中y滿足同余方程yk o 1 (mod m)；反之，易知如此形式的x是xk o a(mod m)的解。

39、 第五章 二次同余式與平方剩余 §1 一般二次同余式 1、 在同余式中，假設(shè)，試求出它的一切解來。 解：假設(shè)，那么，上同余式即為 從而，即有。 易見，當為偶數(shù)時，，那么，上同余式有解： ，共有個解 當為奇數(shù)時，，上同余式有解： ，共有個解。 2、證明：同余式 有解的充分必要條件是 有解，并且前一同余式的一切解可由后一同余式的解導(dǎo)出。 證明：因，故 用乘后再配方，即得 仍記為，即有 由以上討論即知假設(shè)為的解， 那么為的解，必要性得證。 反之，假設(shè)有一解，即有： 由于，故有解 即有： 即有： 由，即有： 即為的解，充分性得證。

40、 由充分性的討論即知的解可由的解導(dǎo)出。 §2 單質(zhì)數(shù)的平方剩余與平方非剩余 1、 求出模的平方剩余與平方非剩余。 解：，由書中定理2知，模的簡化剩余系中個平方剩余分別與序列 例2．試判斷下述同余方程是否是有解。 〔1〕 〔2〕 〔3〕 中之一數(shù)同余，而 故模37的平方剩余為： 1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36 而其它的18個數(shù)為模37的平方非剩余： 2，5，6，8，13，14，15，17，18，19，20，22，2

41、3，24，29，31，32，35 2． 應(yīng)用前幾章的結(jié)果證明:模的簡化剩余系中一定有平方剩余及平方非剩余存在， 證明兩個平方剩余的乘積是平方剩余;平方剩余與平方非剩余的乘積是平方非剩余。 應(yīng)用、證明：模的簡化剩余系中平方剩余與平方非剩余的個數(shù)各為。 證明：因為1為模的簡化剩余系中的平方剩余。假設(shè)模的簡化剩余系中均為平方剩余，考慮模的絕對最小簡化剩余系： 它們的平方為模下的個數(shù)： 由假設(shè)模的簡化剩余系中任一個數(shù)與上個數(shù)同余，而模的簡化剩余系中有個數(shù)，故必有兩個互相同余，矛盾。從而必有平方非剩余存在。 假設(shè)為平方剩余，那么故從而也為平方剩余。假設(shè)為平方剩余，

42、為平方非剩余，那么 故從而為平方非剩余。 設(shè)為模的簡化剩余系中的平方剩余；為模的簡化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。 3．證明：同余式，的解是 ，其中 證明：假設(shè)有解，那么有解， 設(shè)其解是：，即有： ， 令 而 ， 為整數(shù) 由此兩式即得： 兩式相乘得： 取使得： 那么 故其解為 4．證明同余式 的解是

43、 證明：首先我們證明對任意： 有下式： 因為 ，于是 因此由威爾生定理得： 其次由，可令 ，代入上式 即有 故原同余式的解為 §3 勒讓得符號 1．用本節(jié)方法判斷以下同余式是否有解 其中503，563，769，1013都是質(zhì)數(shù) 解：，有解。 ，有解。 ，有解。 2、求出以為平方剩余的質(zhì)數(shù)的一般表達式；以為平方非剩余的質(zhì)數(shù)的一般表達式。 解： 為模平方剩余時，必有 ，必有，故 ，必有，故 為模平方非剩余時，必有 ，必有，故

44、 ，必有，故 3、設(shè)是正整數(shù)，及都是質(zhì)數(shù)，說明 由此證明：。 證明：當時，由本節(jié)定理1的推論知為平方剩余，應(yīng)用歐拉判別條件即有 由，即得出 而都是形如的素數(shù)，并且 ，所以 。 §4 前節(jié)定理的證明 1、 求以為平方剩余的質(zhì)數(shù)的一般表達式，什么質(zhì)數(shù)以為平方非剩余？ 解：由互反律 因此當它們同為或同時為時，， 一為，一為時， 顯然，當為偶數(shù)，而時，， 當是奇數(shù)，即時，。 再因為是奇質(zhì)數(shù)，關(guān)于模我們有或， 當時， 當時， 這樣為平方剩余時，為下方程組的解 或 由孫子定理，即可知或，立即 當時，為平方剩余。 為平方非剩余時，為下方程組的解

45、 或 由孫子定理，即可知或，立即 當時，為平方非剩余。 因為 當為偶數(shù)，，或為奇數(shù)，時，即 或時，為平方剩余， 類似或，為平方非剩余。 2、求以為最小平方非剩余的質(zhì)數(shù)的一般表達式。 解：由上題知以為平方非剩余的質(zhì)數(shù)滿足： 又由為模的最小平方非剩余，故 從而〔§3推證〕 滿足的素數(shù)形如， 其中只有滿足 故或時，為它的最小平方非剩余。 §5 雅可比符號 1、 判斷§3習題1所列各同余式是否有解。 略 2、 求出以下同余式的解數(shù)： ，其中是一個質(zhì)數(shù)。 解： ，故 故，即的解數(shù)為0． ，故解數(shù)為2． 3． 在有解的情況下，應(yīng)用定理

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

47、 得出 ， 即 從而 故 所以 為所給同余式的解 從而所有的解為： 〔ⅱ〕 ，故有四解 記代入，即有： 解得 記，代入 即有：，解得： 又記，代入 即有，解得: 故為其一解 其余三解為： 2．〔ⅰ〕證明同余式與同余式等價，〔ⅱ〕應(yīng)用〔ⅰ〕舉出一個求同余式的一切解的方法。 證明：〔ⅰ〕顯然 〔ⅱ〕記 有解，等價于方程組 有解 易見的解為 的解為 的解為 或 二者不能同時成立，否那么矛盾 故它有兩個 解，聯(lián)立方程組即可求出一切解。 第六章 原

48、根與指標 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對模q的質(zhì)數(shù)是 是質(zhì)數(shù) 從而或p 假設(shè)，那么，故; 假設(shè)，而，q-1為偶數(shù)， 記q-1=2x，那么，又假設(shè) 故q=2px+1得證。 (ii)設(shè)q為的奇質(zhì)因數(shù)，那么 從而，從而a對模q的指數(shù)．故，2，p，2p之一 假設(shè)，那么，從而 即有，不可能，故 假設(shè)，那么，而(否那么) 故 假設(shè)，那么，而有，不可能

49、假設(shè)，那么由，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ù)。 根據(jù)定義1直接計算，得到 d7(1) = 1，d7(2) = 3，d7(3) = 6， d7(4) = 3，d7(5) = 6，d7(6) = 2。 例1中的結(jié)果可列表如下： a 1 2 3 4 5 6 d7(a) 1 3 6 3 6 2 這樣的表稱為指數(shù)表。這個表就是模7的指數(shù)表。 下面是模

50、10的指數(shù)表： a 1 3 7 9 d10(a) 1 4 4 2 1．寫出模11的指數(shù)表。 解：經(jīng)計算得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，列表得 a 1 2 3 4 5 6 7 8 9 10 d11(a) 1 10 5 5 5 10 10 10 5 2 2．求模14的全部原根。 解：x o 3，5 (mod 14)是模

51、14的全部原根。 1．求模29的最小正原根。 解：因j(29) = 28 = 22×7，由 知2是模29的最小正原根。 2．分別求模293和模2×293的原根。 解：由2是模29的原根及229 - 1 = 228 = 2281 (mod 292)知2是模293的原根；由2是模293的原根及2是偶數(shù)知2 + 293是模2×293的原根。 3．解同余方程：x12 o 16 (mod 17)。 解：易得3是模17的原根，3i〔i = 0, 1, 2, L, 15〕構(gòu)成模17的簡化剩余系，列表為 i 0 1 2 3 4 5

52、 6 7 3i (mod 17) 1 3 9 10 13 5 15 11 i 8 9 10 11 12 13 14 15 3i (mod 17) 16 14 8 7 4 12 2 6 由上表知38 o 16 (mod 17)，設(shè)x o 5 y (mod 17)，那么12y o 8 (mod 16)，由此解得y1 o 2，y2 o 6，y3 o 10，y4 o 14 (mod 16)，查上表得x1 o 9，x2 o

53、 15，x3 o 8，x4 o 2 (mod 17)。 3 指標及n次剩余 1．設(shè) 是的一切不同的質(zhì)因數(shù)，證明g是模m的一個原根的充要條件是g對模m的次非剩余。 證明：必要性，設(shè)g為模m的一個原根 由2 Th5 知 假設(shè)g為模m的次剩余，那么存在，使得 又由歐拉定理 故 ，矛盾！ 充分性，假設(shè)g不為模m的一個原根，由2 Th5 知 存在，使得： 設(shè)為模m的一個原根，那么對上式兩邊關(guān)于取指標： 記 ，那么由指標的定義即有： 故 即為同余式 的解 從而g為次剩余，矛盾。 2．證明10是模17及模2

54、57〔質(zhì)數(shù)〕的原根，并由此證明把化成循環(huán)小數(shù)時，循環(huán)節(jié)的長度分別是16及256． 證明：，它的有且只有質(zhì)因子2，而 從而10不是模17的平方剩余，由上題知10是模17的原根。 ，由且僅有質(zhì)因子2，而 故同上理10也是模257的原根。 由3§4的證明可知，，的循環(huán)節(jié)的長度，t，這是10關(guān)于模17，模257的指數(shù)，從而 t=16，256 證畢 3．試利用指標表解同余式 解：同余式等價于： 查表知，故： 由于，故上式由 5個解， 解之得： 查表知：原同余式的5個解為： 4．設(shè)模m〔m．>2〕

55、的原根是存在的，試證對模m的任一原根來說，的指標總是． 證明：模m的原根存在，故m=4，或 設(shè)為模m的一個原根，那么 從而 假設(shè)m=4，，那么模m有且只有一個原根3， ， 故的指標為 假設(shè)，為奇質(zhì)數(shù)，那么由知 或 但二者不能同時成立，否那么，矛盾! 假設(shè)又由〔*〕知 〔mod m〕，與的指數(shù)為矛盾。 從而，從而 〔mod m〕 故-1的指標為。 假設(shè)，為的原根，那么為奇數(shù) 類似于的討論，我們有 ， 從而 從而 〔mod m〕 故-1的指標為。 5、設(shè)，是模的兩個原根，試證：

56、 〔mod 〕； 〔mod 〕。 證明：由指標的定義知： 〔mod m〕 兩邊對原根取指標： 〔mod 〕 故 〔mod 〕 由指標的定義知： 〔mod m〕 兩邊對原根取指標： 〔mod 〕 故 〔mod 〕。 〔證畢〕 第九章　數(shù)論函數(shù) §1． 可乘函數(shù) 1．設(shè)是一個可乘函數(shù)，證明也是一個可乘函數(shù)．由此說明是可乘函數(shù)． 證明：首先我們證明：設(shè)，假設(shè)跑過的全部因子，跑過的全部因子，那么跑過的全部因子，事實上，因為，故，且當，時，由于，得，反之任給，由于，設(shè)，

57、，顯然．因此 　　　　　　　　 　　　　　　　　 故為一個可乘函數(shù)．　　　　　　　　　　　　　　　　　　　　(此為65頁) 假設(shè)，它為可乘函數(shù)．，且． 假設(shè)，它為可乘函數(shù)，且． 故為可乘函數(shù)． 2．　設(shè)是一個定義在一切正態(tài)數(shù)的函數(shù)，并且是一個可乘函數(shù)，證明是可乘函數(shù)． 證明：反證，假設(shè)不是可乘函數(shù)，那么存在一對正態(tài)數(shù)，使得，于是我們可以選擇這樣一對，使得最小．假設(shè)，那么，即，又，為可乘函數(shù)，故有矛盾！ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　 假設(shè)，那么對所有正態(tài)數(shù)對，有 于是有：

58、 = = 因為，故 此與 為可乘函數(shù)矛盾！ 3．證明： 證明：首先易證，假設(shè)d為的正約數(shù)，那么a的完全剩余系中與的最大公約數(shù)是d的個數(shù)為。 其次，假設(shè)為的所有正約數(shù)。那么也是的所有正約數(shù)，于是 最后，在的完全剩余系中住一數(shù)與的最大公約數(shù)必定是中某一個，而完全剩余系中與最大公約數(shù)為的數(shù)有個，所以 4．試計祘和式 解：此題較復(fù)雜，下分數(shù)步解之： ?反演公式 設(shè)和是兩個數(shù)論函數(shù)，且，那么反之亦然 事實上，

59、 反之，類似可得。參見習題5及6 。 ②假設(shè)是定義在閉區(qū)間上的函數(shù)，n正整數(shù)，記 ， 那么 事實上，由①，只要證明，但這幾乎是明顯的，因為如果分數(shù)化成既約分數(shù)，就得到形如 的分數(shù)，這里， b是n的一個約數(shù)．每一個這樣形式的分數(shù)都可得到一次也好一次． ③ 記 ， 那么 記 那么 那么 這樣由②知: 由本節(jié)推論2．2 2．3，即有： 5． 是任一函數(shù)，并且： 試證： 證明：設(shè) ， 即，那么 由推論2．3知，其內(nèi)部之和只有當c=a時為１，c