《《初等數(shù)論》第三版習(xí)題解答》由會(huì)員分享，可在線閱讀，更多相關(guān)《《初等數(shù)論》第三版習(xí)題解答（73頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正。 第一章 整數(shù)的可除性 1 整除的概念帶余除法 1．證明定理3 定理3 若都是得倍數(shù)，是任意n個(gè)整數(shù)，則是得倍數(shù)． 證明： 都是的倍數(shù)。 存在個(gè)整數(shù)使 又是任意個(gè)整數(shù) 即是的整數(shù) 2．證明 證明 又，是連續(xù)的三個(gè)整數(shù) 故 從而可知 3．若是形如（x，y是任意整數(shù)，a，b是兩不全為零的整數(shù)）的數(shù)中最小整數(shù)，則． 證： 不全為 在整數(shù)集合中存在正整數(shù)，因而有形如的最小整數(shù) ，由帶余除法有 則，由是中的最小整數(shù)知 （為任意整數(shù)） 又

2、有， 故 4．若a，b是任意二整數(shù)，且，證明：存在兩個(gè)整數(shù)s，t使得 成立，并且當(dāng)b是奇數(shù)時(shí)，s，t是唯一存在的．當(dāng)b是偶數(shù)時(shí)結(jié)果如何？ 證：作序列則必在此序列的某兩項(xiàng)之間 即存在一個(gè)整數(shù)，使成立 當(dāng)為偶數(shù)時(shí)，若則令，則有 若 則令，則同樣有 當(dāng)為奇數(shù)時(shí)，若則令，則有 若 ，則令，則同樣有，綜上所述，存在性得證． 下證唯一性 當(dāng)為奇數(shù)時(shí)，設(shè)則 而 矛盾 故 當(dāng)為偶數(shù)時(shí)，不唯一，舉例如下：此時(shí)為整數(shù) 2 最大公因數(shù)與輾轉(zhuǎn)相除法 1．證明推論4.1 推論4.1 a，b的公因數(shù)與（a，b）的因數(shù)相同． 證：設(shè)是a，b的任一公因數(shù)，|a，|b

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

4、，b互質(zhì)的充分與必要條件是：存在兩個(gè)整數(shù)s，t滿足條件． 證明 必要性。若，則由推論1.1知存在兩個(gè)整數(shù)s，t滿足：， 充分性。若存在整數(shù)s，t使as+bt=1，則a，b不全為0。 又因?yàn)?，所? 即。 又， 2．證明定理3 定理3 證：設(shè)，則 ∴又設(shè) 則。反之若，則， 從而，即= 3．設(shè) （1） 是一個(gè)整數(shù)系數(shù)多項(xiàng)式且，都不是零，則（1）的根只能是以的因數(shù)作分子以為分母的既約分?jǐn)?shù)，并由此推出不是有理數(shù)． 證：設(shè)（1）的任一有理根為，。則 （2） 由， 所以q整除上式的右端，所以，又， 所以； 又由（2）

5、有 因?yàn)閜整除上式的右端，所以 ，，所以 故（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)的素?cái)?shù) 將不超過100的正整數(shù)排列如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 1

6、4 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 8

7、9 90 91 92 93 94 95 96 97 98 99 100 2．求82798848及81057226635000的標(biāo)準(zhǔn)式． 解：因?yàn)?|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個(gè)正整數(shù)的情形． 推論3.3 設(shè)a，b是任意兩個(gè)正整數(shù)，且 ，，， ，，， 則，， 其中，， 證：， ∴ ∴ ，. ∴ ，又顯然 ∴ ，同理可得，

8、推廣 設(shè),, (其中為質(zhì)數(shù)為任意n個(gè)正整數(shù))， 則 4．應(yīng)用推論3.3證明3的定理4（ii） 證：設(shè)， 其中p1, p2, L, pk是互不相同的素?cái)?shù)，ai，bi（1 i k）都是非負(fù)整數(shù)，有 由此知(a, b)[a, b] ==ab；從而有． ５．若是質(zhì)數(shù)（n>1），則n是2的方冪． 證：（反證法）設(shè)為奇數(shù)）， 則 ∵ ， ∴ 為合數(shù)矛盾，故ｎ一定為２的方冪． 5 函數(shù)[x],{x}及其在數(shù)論中的一個(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 ， ， ，

9、 ∴ 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)注]：[證一]充分體現(xiàn)了 常規(guī)方法的特點(diǎn)，而[證二]則表現(xiàn)了較高的技巧。 3．設(shè)，是任意二實(shí)數(shù)，證明： (i) 或 (ii) 證明：（i）由高斯函數(shù)[x]的定義有 。則 當(dāng)

10、 當(dāng) 故 （ii）設(shè)， 則有 下面分兩個(gè)區(qū)間討論： ①若，則，所以，所以 ②若，則，所以。 所以 （ii）（證法2）由于，對(duì)稱，不妨設(shè) 4. (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ù)

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

12、 當(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ù)解為，tZ，于是由x 0，y 0得，但區(qū)間的長(zhǎng)度是，故此區(qū)間內(nèi)的整數(shù)個(gè)數(shù)為+ 1。 ： 4、證明：二元一次不定方程 ，當(dāng) 時(shí)有非負(fù)整數(shù)解， 則不然。 證明：先證后

13、一點(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 = (a2 + b2)d或l = (a2 -

14、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)? 或3/z+x 以下不妨設(shè) ②， 設(shè) 與矛盾! 這樣而 ③， ， 即 ④若 由引理可設(shè) 從而 ， 為證得為整數(shù)， 必須有a ， b均為奇數(shù)，且 ⑤若 設(shè)， 其中為一奇一偶，且有 4．解不定方程：x2 + 3y2 = z2，x > 0，y > 0，z > 0，(x, y ) = 1。 解：設(shè)

15、(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)證(ⅰ)或(ⅱ)是原不定方程的解，且x

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

17、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，2x。 其中正負(fù)號(hào)可任意選?。? 第三章 同余 1同余的概念及其基本性質(zhì) 1、 證明

18、（i）若(modm) xy(modm)、i=1，2，、、、，k 則(modm) 特別地，若（modm），i=0，1，則 （modm） (ii)若ab(modm)，k （iii）若ab(modm)，d是a，b及m的任一正公因數(shù)，則 (iv)若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) 又 故

19、 2、設(shè)正整數(shù) 試證11整除的充分且必要條件是11整除 證明 ：由上題(i)的特殊情形立得 ． 3．找出整數(shù)能被37，101整除有判別條件來。 解： 故正整數(shù) 立得 故設(shè)正整數(shù)， 立得 4、證明｜ 證明：∵ ∴ ∴ 即∣ 5、若是任一單數(shù)，則， 證明：（數(shù)學(xué)歸納法）設(shè) （1）時(shí)，， 結(jié)論成立。 （2）設(shè)時(shí)，結(jié)論成立，即： ， 而 故時(shí)，結(jié)論也成立；∴時(shí)，結(jié)論也成立。 證明：若2a，n是正整數(shù)

20、，則 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 + 2， 其中qZ，所以 = (1 + q2k + 2)2 = 1 + q 2k + 3 1 (mod 2k + 3)， 其中q 是某個(gè)整數(shù)。這說明式(4)當(dāng)n = k + 1也成立。 由歸納法知式(4)對(duì)所有正整數(shù)n成立。 ； 解：；

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

22、完全剩余系，即對(duì)結(jié)論成立。 3、（i）證明整數(shù)中每一個(gè)整數(shù)有而且只有一種方法表示成 ? 的形狀，其中；反之，?中每一數(shù)都。 （ii）說明應(yīng)用個(gè)特別的砝碼，在天平上可以量出1到H中的任意一個(gè)斤數(shù)。 證明：（i）當(dāng)時(shí)，?過模的絕對(duì)最小完全剩余系，也就是?表示中的個(gè)整數(shù)，事實(shí)上，當(dāng)時(shí)，共有個(gè)值，且兩兩互不相等，否則 此即 又?的最大值是 最小值是 所以，結(jié)論成立。 （ii）特制個(gè)砝碼分別重斤，把要稱的物體及取-1的砝碼放在天平的右盤，取1的砝碼放在左盤，則從（i）的結(jié)論知，當(dāng)取適當(dāng)?shù)闹禃r(shí)，可使之值等于你所要稱的物體的斤數(shù)。 4、若是K個(gè)兩兩互質(zhì)的正整數(shù)，分別過

23、模的完全剩余系，則 ? 通過模的完全剩余系。 證明：（數(shù)學(xué)歸納法） （1）時(shí)，分別過模的完全剩余系時(shí)， 共有個(gè)值，且若 ，且 ，，即時(shí)結(jié)論成立； （2）設(shè)當(dāng)分別過模的完全剩余系時(shí)， 過模的完全剩余系。 因?yàn)?，由本?jié)定理2得， 亦過模的完全剩余系。 當(dāng)分別過模的完全剩余系時(shí)， 2有個(gè)值，且據(jù)歸納假設(shè)， 若 ； ，，…， ，，…，。 所以過模的完全剩余系。 3．簡(jiǎn)化剩余系與歐拉函數(shù) 1．證明定理2：若是與互質(zhì)的整數(shù)， 并且兩對(duì)模不同余，則是模的一個(gè)簡(jiǎn)化剩余系。 證明： 兩對(duì)模不同余，所以它們分別

24、取自模的不同剩余類， 又恰是個(gè)與互質(zhì)的整數(shù)，即它們恰取自與?；ベ|(zhì)的全部剩余類。 2．若是大于1的正整數(shù)，是整數(shù)，，通過的簡(jiǎn)化剩余系， 則，其中表示展布在所通過的一切值上的和式。 證明：由定理3知，通過的簡(jiǎn)化剩余系： ，其中0＜＜且， 而（）。 若＞2，則必是偶數(shù)，又由， 得，且易見， 故 所以 左邊每一項(xiàng)都存在另一項(xiàng)， 使得，右邊共有對(duì)， 此即。 特別地，當(dāng)m=2時(shí)，。 3．（i）證明，p質(zhì)數(shù)。 (ii) 證明，其中展布在a的一切正整數(shù)上的和式。 證明：（i）因?yàn)椋? 所以 = = (ii)設(shè)是a的標(biāo)準(zhǔn)分解式， 則， =

25、 =a 4．若是k個(gè)兩兩互質(zhì)的正整數(shù)， 分別通過模的簡(jiǎn)化剩余系，則 通過模的簡(jiǎn)化剩余系，其中。 證明：（數(shù)學(xué)歸納法） （1） 由定理4知k=2時(shí)，結(jié)論成立； （2） 設(shè)k-1時(shí)結(jié)論成立，即，分別過模時(shí)， 過模的簡(jiǎn)化剩余系。 顯見，則又由定理4知，通過模的簡(jiǎn)化剩余系，注意到： 所以，通過模m的簡(jiǎn)化剩余系。 ．歐拉定理費(fèi)馬定理及其對(duì)循環(huán)小數(shù)的應(yīng)用 １、如果今天是星期一，問從今天起再過天是星期幾？ 解：若被除的非負(fù)最小剩余是，則這一天就是星期（當(dāng)時(shí)是星期日）． ，由費(fèi)馬定理得， 又 即這一天是星期五． ２、求被除

26、的余數(shù)。 解：， 據(jù)歐拉定理，易知 　　　　　　　　　　　?。ǎ保? 又 故　　 則?。桑ǎ保┘吹? ． 由以上計(jì)算，知　． ． ３、證明下列事實(shí)但不許用定理１推論：若是質(zhì)數(shù)，是整數(shù)，則。 由證明定理１推論，然后再由定理１推論證明定理１。 證明　對(duì)應(yīng)用數(shù)學(xué)歸納法： 當(dāng)時(shí)，按二項(xiàng)式展開即得 設(shè)時(shí)，結(jié)論成立，即 當(dāng)時(shí)， 結(jié)論成立。 在的結(jié)論中，令，即得： 　　　　　 即定理１推論成立。 進(jìn)一步，設(shè)，則　 固對(duì)任一整數(shù)，若，則由上述已證性質(zhì)得： 存在，使 故=（） 依此類推可得． 若，則 ，定理成立。 4、證明：有理數(shù)表成純循環(huán)

27、小數(shù)的充分與必要條件是有一正數(shù)t使得同余式成立，并且使上式成立的最小正整數(shù)t就是循環(huán)節(jié)的長(zhǎng)度。 證明：必要性，若結(jié)論成立，則由定理2知（b，10）=1， 令t=則據(jù)歐拉定理得； 充分性，若有正數(shù)t，滿足 令t為使上式成立的最小正整數(shù)，且= 且。 以下參照課本51頁的證明可得： =即可表成循環(huán)小數(shù)，但循環(huán)節(jié)的長(zhǎng)度就是t。 第四章 同余式 1 基本概念及一次同余式 例 解同余式 解：（12，45）= 同余多項(xiàng)式有3個(gè)解 而原同余式為 4

28、 與也一樣 所以原同余式的3個(gè)解是 （ｔ＝０、１、２） 即，，　 1、 求下列各同余式的解 256x179 1215x560 1296x1125 337是素?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è)是正

29、整數(shù)，．證明 是同余式 的解 (ii)設(shè)是質(zhì)數(shù)，，證明 是同余式的解． 證明: (i) ， 有唯一解． 而據(jù)歐拉定理，得 ， 即 是的解． (ii) 即有唯一解 又 個(gè)連續(xù)整數(shù)之積必被所整除， 故可令 則 即 即 是的解． 設(shè)p是素?cái)?shù)，0 < a < p，證明： (mod p)。 是同余方程ax b (mod p)的解。 解：首先易知是整數(shù)，又由(a, p) = 1知方程ax b (mod p)解唯一，故只須將(mod p)代入ax b (mod p)驗(yàn)證它是同余方程的解即可。 4．設(shè)是正

30、整數(shù)，是實(shí)數(shù)，，證明同余式 有解． 證明: 因 故同余式 必有解， (i) 若 ，則結(jié)論成立; (ii) 若，令，， 則 又若 則由 ，結(jié)論成立． 若 令 則 又若 則由 即 故 結(jié)論成立。 若又令 則 重復(fù)上述討論：即若 則結(jié)論成立， 若又令 `````` 例解同余方程組 解：互質(zhì)，故原方程組對(duì)模有唯一解 即 根據(jù)孫子定理方程組的解是 注意到 故有限步后，必有 其中即結(jié)論成立。 孫子定理 試解下列各題： （i） 十一數(shù)余三，七二數(shù)余二，

31、十三數(shù)余一，問本數(shù)。 （ii） 二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問本數(shù)。 （楊輝：續(xù)古摘奇算法（1275））。 解：（i）依題意得 則據(jù)孫子定理，上述方程組有唯一解 由 故原方程組的解是 (ii)依題意得 2、（i）設(shè) 是三個(gè)正整數(shù)，證明： ． （ii）設(shè) 證明：同余式組 （1） 有解的充分與必要條件是 在有解的情況下，適合（1）的一切整數(shù)可由下式求出： 其中是適合的一個(gè)整數(shù)。 應(yīng)用證明同余式組 有解的充分與必要條件是，并且有解的情況下，適合的一切整數(shù)可由下式求出：

32、 其中是適合的一個(gè)整數(shù)。 證明： 即 設(shè)有解，即 故此得，必要性成立； 反之，設(shè)即 則由1定理，知方程必有解， 設(shè)其解為，即 令則易見： 且 即有解，充分性得證。 進(jìn)一步，若有解，則 即是的公倍數(shù)，當(dāng)然也是的倍數(shù)， 故若是的一個(gè)解，則的任一解必滿足 。 若同余式組有解， 則 也有解。從而由知必有 ，必要性成立。 下證充分性。首先，推，用歸納法易證： 又由知時(shí)，充分性也成立； 現(xiàn)設(shè)同余式組 有解， 即。 設(shè)；又由條件知， 而，從而， 所以， 即， 又由，則同余式組， 必有解

33、 （※） 顯然，即（※）就是同余式組的解，據(jù)歸納性原理，結(jié)論成立。后一結(jié)論由上述過程亦成立。 3 高次同余式的解數(shù)及解法 1、 解同余式。 解：原同余式等價(jià)于 據(jù)孫子定理，可得 故原同余式共有6個(gè)解是： 2、 解同余式 解： 故原同余式等價(jià)于 1） 先解 即 得 ②再解 即 設(shè) 而 由孫子定理設(shè) 即原四條式有4個(gè)解是 4．質(zhì)數(shù)模的同余式 補(bǔ)充例子： 1．解同余方程： (ⅰ) 3x11 + 2x8 + 5x4 - 1 0

34、(mod 7)； (ⅱ) 4x20 + 3x12 + 2x7 + 3x - 2 0 (mod 5)。 解：(ⅰ) 原同余方程等價(jià)于3x5 + 5x4 + 2x2 - 1 0 (mod 7)，用x = 0，1，2，3代入知后者無解； (ⅱ) 原同余方程等價(jià)于2x4 + 2x3 + 3x - 2 0 (mod 5)，將x = 0，1，2 代入，知后者有解x 1 (mod 5)。 2．判定 (ⅰ) 2x3 - x2 + 3x - 1 0 (mod 5)是否有三個(gè)解； (ⅱ) x6 + 2x5 - 4x2 + 3 0 (mod 5)是否有六個(gè)解？ 解：(ⅰ) 2x

35、3 - 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ù)，故原方程沒有三個(gè)解； (ⅱ) 因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解。 定理5 若p是素?cái)?shù)，np - 1，pa則 x n a (mod p) (14) 有解的充要條件是 1 (mod p)。

36、 (15) 若有解，則解數(shù)為n。 證明 必要性 若方程(14)有解x0，則px0，由Fermat定理，得到 = x0p - 1 1 (mod p)。 充分性 若式(15)成立，則 其中P(x)是關(guān)于x的整系數(shù)多項(xiàng)式。由定理4可知同余方程(14)有n個(gè)解。證畢。 1、 設(shè)︱， ， ．證明同余式 有解的充分必要條件是，并且在有解的情況下就有個(gè)解。 證明： 設(shè) 則 但 則由 可得。 它有個(gè)解。 ︱ 令 則 無多于個(gè)解，而 恰有個(gè)解，必有個(gè)解。 2．設(shè)n是整數(shù)，（a，m）=1，且已知

37、同余式 有一解，證明這個(gè)同余式的一切解可以 表成 其中y是同余式的解。 證明：設(shè)均是的解， 則， （a，m）=1 ， （，m）= (，m) = 1 則由第三章定理3．3知，必存在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)的任意一個(gè)解

38、，則一次同余方程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、 在同余式中，若，試求出它的一切解來。 解：若，則，上同余式即為 從而，即有。 易見，當(dāng)為偶數(shù)時(shí)，，則，上同余式有解： ，共有個(gè)解 當(dāng)為奇數(shù)時(shí)，，上同余式有解： ，共有個(gè)解。 2、證明：同余式 有解的充

39、分必要條件是 有解，并且前一同余式的一切解可由后一同余式的解導(dǎo)出。 證明：因，故 用乘后再配方，即得 仍記為，即有 由以上討論即知若為的解， 則為的解，必要性得證。 反之，若有一解，即有： 由于，故有解 即有： 即有： 由，即有： 即為的解，充分性得證。 由充分性的討論即知的解可由的解導(dǎo)出。 2 單質(zhì)數(shù)的平方剩余與平方非剩余 1、 求出模的平方剩余與平方非剩余。 解：，由書中定理2知，模的簡(jiǎn)化剩余系中個(gè)平方剩余分別與序列 例2．試判斷下述同余方程是否是有解。 （1） （2） （3） 中之一數(shù)同余，而

40、 故模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，35 2． 應(yīng)用前幾章的結(jié)果證明:模的簡(jiǎn)化剩余系中一定有平方剩余及平方非剩余存在， 證明兩個(gè)平方剩余的乘積是平方剩余;平方剩余與平方非剩余的乘積是平方非剩余。 應(yīng)用、證明：模的簡(jiǎn)化剩余系中平方剩余與平方非剩余的個(gè)數(shù)各為。 證明：因?yàn)?為模的簡(jiǎn)化剩余系中的平方剩余

41、。若模的簡(jiǎn)化剩余系中均為平方剩余，考慮模的絕對(duì)最小簡(jiǎn)化剩余系： 它們的平方為模下的個(gè)數(shù)： 由假設(shè)模的簡(jiǎn)化剩余系中任一個(gè)數(shù)與上個(gè)數(shù)同余，而模的簡(jiǎn)化剩余系中有個(gè)數(shù)，故必有兩個(gè)互相同余，矛盾。從而必有平方非剩余存在。 若為平方剩余，則故從而也為平方剩余。若為平方剩余，為平方非剩余，則 故從而為平方非剩余。 設(shè)為模的簡(jiǎn)化剩余系中的平方剩余；為模的簡(jiǎn)化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。 3．證明：同余式，的解是 ，其中 證明：若有解，則有解， 設(shè)其解是：，即有：

42、 ， 令 而 ， 為整數(shù) 由此兩式即得： 兩式相乘得： 取使得： 則 故其解為 4．證明同余式 的解是 證明：首先我們證明對(duì)任意： 有下式： 因?yàn)?，于是 因此由威爾生定理得： 其次由，可令 ，代入上式 即有 故原同余式的解為 3 勒讓得符號(hào) 1．用本節(jié)方法判斷下列同余式是否有解

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

44、或同時(shí)為時(shí)，， 一為，一為時(shí)， 顯然，當(dāng)為偶數(shù)，而時(shí)，， 當(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ù)形如， 其中只有滿足

45、 故或時(shí)，為它的最小平方非剩余。 5 雅可比符號(hào) 1、 判斷3習(xí)題1所列各同余式是否有解。 略 2、 求出下列同余式的解數(shù)： ，其中是一個(gè)質(zhì)數(shù)。 解： ，故 故，即的解數(shù)為0． ，故解數(shù)為2． 3． 在有解的情況下，應(yīng)用定理1，求同余式 ，的解。 在有解的情況下，應(yīng)用 2 定理1及3定理1的推論，求同余式 ，的解。 解：同余式有解，故 由知 故即為原同余式的解。 由知，故 故 因此或 若前式成立，那末 即 若則原同余式的解是 即 為原同余式的解。 若后式成立，那末 由3定理

46、1的推論知，2是模p的平方剩余，即 于是： 若則原同余式的解是 故為原同余式的解． 6 合數(shù)模的情形 1. 解同余式 ， 解：從同余式 得 令代入得出 從而即有 故， 再令代入 得出 ， 即 從而 故 所以 為所給同余式的解 從而所有的解為： （ⅱ） ，故有四解 記代入，即有： 解得 記，代入 即有：，解得： 又記，代入 即有，解得: 故為其一解 其余三解為： 2．（ⅰ）證明同余式與同余式等價(jià)，（ⅱ）應(yīng)用（ⅰ）舉出一個(gè)求

47、同余式的一切解的方法。 證明：（?。╋@然 （ⅱ）記 有解，等價(jià)于方程組 有解 易見的解為 的解為 的解為 或 二者不能同時(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 若，則，故; 若，而，q-1為偶數(shù)， 記q-1=2x，則，又假設(shè) 故q=2px

48、+1得證。 (ii)設(shè)q為的奇質(zhì)因數(shù)，則 從而，從而a對(duì)模q的指數(shù)．故，2，p，2p之一 若，則，從而 即有，不可能，故 若，則，而(否則) 故 若，則，而有，不可能 若，則由，q－1＝2m 記m＝px，則q＝2px+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，

49、d7(6) = 2。 例1中的結(jié)果可列表如下： a 1 2 3 4 5 6 d7(a) 1 3 6 3 6 2 這樣的表稱為指數(shù)表。這個(gè)表就是模7的指數(shù)表。 下面是模10的指數(shù)表： a 1 3 7 9 d10(a) 1 4 4 2 1．寫出模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，列表得 a 1 2

50、 3 4 5 6 7 8 9 10 d11(a) 1 10 5 5 5 10 10 10 5 2 2．求模14的全部原根。 解：x 3，5 (mod 14)是模14的全部原根。 1．求模29的最小正原根。 解：因j(29) = 28 = 227，由 知2是模29的最小正原根。 2．分別求模293和模2293的原根。 解：由2是模29的原根及229 - 1 = 228 = 2281 (mod 292)知2是模293的原根；由2是模293的原根及2是偶數(shù)知2 + 293是模2293的原根。 3．解同余方程：x12 16 (mod

51、17)。 解：易得3是模17的原根，3i（i = 0, 1, 2, L, 15）構(gòu)成模17的簡(jiǎn)化剩余系，列表為 i 0 1 2 3 4 5 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 16 (mod 1

52、7)，設(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 知 若g為模m的次剩余，則存在，使得 又由歐拉定理 故 ，矛盾！ 充分性，若g不為模m的一個(gè)原根，由2 Th5 知 存在，使得： 設(shè)為模m的一個(gè)原根，則對(duì)上式兩邊關(guān)于

53、取指標(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的原根。 由34的證明可知，，的循環(huán)節(jié)的長(zhǎng)度，t，這是10關(guān)于模17，模257的指數(shù)，從而 t=16，256 證畢 3．試?yán)弥笜?biāo)表解同余式 解：

54、同余式等價(jià)于： 查表知，故： 由于，故上式由 5個(gè)解， 解之得： 查表知：原同余式的5個(gè)解為： 4．設(shè)模m（m．>2）的原根是存在的，試證對(duì)模m的任一原根來說，的指標(biāo)總是． 證明：模m的原根存在，故m=4，或 設(shè)為模m的一個(gè)原根，則 從而 若m=4，，則模m有且只有一個(gè)原根3， ， 故的指標(biāo)為 若，為奇質(zhì)數(shù)，則由知 或 但二者不能同時(shí)成立，否則，矛盾! 若又由（*）知 （mod m），與的指數(shù)為矛盾。 從而，從而 （mod m） 故-1的指標(biāo)為。 若，為的原根，則為奇數(shù)

55、 類似于的討論，我們有 ， 從而 從而 （mod m） 故-1的指標(biāo)為。 5、設(shè)，是模的兩個(gè)原根，試證： （mod ）； （mod ）。 證明：由指標(biāo)的定義知： （mod m） 兩邊對(duì)原根取指標(biāo)： （mod ） 故 （mod ） 由指標(biāo)的定義知： （mod m） 兩邊對(duì)原根取指標(biāo)： （mod ） 故 （mod ）。 （證畢） 第九章　數(shù)論函數(shù) 1． 可乘函數(shù) 1．設(shè)是一個(gè)可乘函數(shù)，證明也是一個(gè)可乘函數(shù)．由此說明是可乘函數(shù)．

56、 證明：首先我們證明：設(shè)，若跑過的全部因子，跑過的全部因子，則跑過的全部因子，事實(shí)上，因?yàn)?，故，且?dāng)，時(shí)，由于，得，反之任給，由于，設(shè)，，顯然．因此 　　　　　　　　 　　　　　　　　 故為一個(gè)可乘函數(shù)．　　　　　　　　　　　　　　　　　　　　(此為65頁) 若，它為可乘函數(shù)．，且． 若，它為可乘函數(shù)，且． 故為可乘函數(shù)． 2．　設(shè)是一個(gè)定義在一切正態(tài)數(shù)的函數(shù)，并且是一個(gè)可乘函數(shù)，證明是可乘函數(shù)． 證明：反證，假設(shè)不是可乘函數(shù)，則存在一對(duì)正態(tài)數(shù)，使得，于是我們可以選擇這樣一對(duì)，使得最小．若，則，即，又，為可乘函數(shù)，故有矛盾！ 　　　　　　　　　　　　　　　　　　　　　　

57、　　　　　　 若，則對(duì)所有正態(tài)數(shù)對(duì)，有 于是有： = = 因?yàn)椋? 此與 為可乘函數(shù)矛盾！ 3．證明： 證明：首先易證，若d為的正約數(shù)，那么a的完全剩余系中與的最大公約數(shù)是d的個(gè)數(shù)為。 其次，若為的所有正約數(shù)。那么也是的所有正約數(shù)，于是 最后，在的完全剩余系中住一數(shù)與的最大公約數(shù)必定是中某一個(gè)，而完全剩余系中與最大公約數(shù)為的數(shù)有個(gè)，所以 4．試計(jì)祘和式 解：此題較復(fù)雜，下分?jǐn)?shù)步解之： ?反演公式 設(shè)和是兩個(gè)數(shù)論函數(shù)

58、，且，則反之亦然 事實(shí)上， 反之，類似可得。參見習(xí)題5及6 。 ②若是定義在閉區(qū)間上的函數(shù)，n正整數(shù)，記 ， 則 事實(shí)上，由①，只要證明，但這幾乎是明顯的，因?yàn)槿绻謹(jǐn)?shù)化成既約分?jǐn)?shù)，就得到形如 的分?jǐn)?shù)，這里， b是n的一個(gè)約數(shù)．每一個(gè)這樣形式的分?jǐn)?shù)都可得到一次也好一次． ③ 記 ， 則 記 則 那么 這樣由②知: 由本節(jié)推論2．2 2．3，即有： 5． 是任一函數(shù)，并且：

59、 試證： 證明：設(shè) ， 即，則 由推論2．3知，其內(nèi)部之和只有當(dāng)c=a時(shí)為１，c

60、第一頁其余諾項(xiàng)都等于0（推論2．3）右上式右邊等于 類似可證明它的逆定理成立。 初等數(shù)論試卷 一、 單項(xiàng)選擇題：（1分/題20題=20分） １．設(shè)為實(shí)數(shù)，為的整數(shù)部分，則(　　) Ａ．；　?。拢?； Ｃ．；　　Ｄ．． ２．下列命題中不正確的是(　　) Ａ．整數(shù)的公因數(shù)中最大的稱為最大公因數(shù)； Ｂ．整數(shù)的公倍數(shù)中最小的稱為最小公倍數(shù) Ｃ．整數(shù)與它的絕對(duì)值有相同的倍數(shù) Ｄ．整數(shù)與它的絕對(duì)值有相同的約數(shù) ３．設(shè)二元一次不定方程（其中是整數(shù)，且不全為零）有一整數(shù)解，則此方程的一切解可表為(　　) Ａ． Ｂ． Ｃ． Ｄ． ４．下列各組數(shù)中不構(gòu)成勾股數(shù)的是(　　

61、) Ａ．５，１２，１３；　?。拢罚玻?，２５； Ｃ．３，４，５；　　　　Ｄ．８，１６，１７ ５．下列推導(dǎo)中不正確的是(　　) Ａ． Ｂ． Ｃ． Ｄ． ６．模１０的一個(gè)簡(jiǎn)化剩余系是(　　) Ａ．　　　　　　　?。拢? Ｃ．　　Ｄ． ７．的充分必要條件是(　　) Ａ．　　?。拢? Ｃ．　　　Ｄ． ８．設(shè)，同余式的所有解為(　　) Ａ．或　　　　?。拢? Ｃ．或　?。模疅o解． 9、設(shè)f(x)=其中為f(x)的一個(gè)解，則:( ) A． B． C． D． 10．則同余式 ：（ ） A．有時(shí)大于p但不大于n;

62、 B．可超過p C．等于p D．等于n 11．若2為模p的平方剩余，則p只能為下列質(zhì)數(shù)中的 :( ) A．3 B．11 C．13 D．23 12．若雅可比符號(hào)，則 ( ) A． B．; C．; D．． 13．( ) A． 4 B． 3 C． 2 D． 1 14． 模12的所有可能的指數(shù)為;( ) A．1，2，4

63、 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．對(duì)于模5，下列式子成立的是: ( ) A． B． C． D． 17．下列函數(shù)中不是可乘函數(shù)的是: ( ) A．茂陛鳥斯(mobius)函數(shù)w(a) ; B． 歐拉函數(shù)； C．不超過x的質(zhì)數(shù)的個(gè)數(shù)； D．除數(shù)函數(shù)

64、； 18． 若對(duì)模的指數(shù)是，>0，>0，則對(duì)模的指數(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ù)解的充分必要條件是_______________

65、____； 23．有理數(shù)，，，能表成純循環(huán)小數(shù)的充分必要條件是_______________________； 24． 設(shè)為一次同余式，的一個(gè)解，則它的所有解為_________________________； 25． 威爾生（wilson）定理：________________________________________； 26． 勒讓德符號(hào)=________________________________________； 27． 若，則是模的平方剩余的充分必要條件是_____________(歐拉判別條件)； 28． 在模的簡(jiǎn)化剩余系中，原根的個(gè)數(shù)是__________

66、_____________； 29． 設(shè)，為模的一個(gè)原根，則模的一個(gè)原根為_____________； 30． _________________________________。 三．簡(jiǎn)答題：（5分／題4題＝20分） 31．命題“任意奇數(shù)的平方減1是8的倍數(shù)”對(duì)嗎？說明理由。 32．“若，通過模的簡(jiǎn)化剩余系，則也通過模的簡(jiǎn)化剩余系”這命題是否正確？正確請(qǐng)證明，不正確請(qǐng)舉反例。 33．求模17的簡(jiǎn)化剩余系中平方剩余與平方非剩余。 34．設(shè)為的標(biāo)準(zhǔn)分解式，記為的正因數(shù)的和，為的正因數(shù)的個(gè)數(shù)，則＝？ ＝？ 為什么？ 四．計(jì)算題。（7分／題4題＝28分） 35． 求不定方程6x+93y=75的一切整數(shù)解。 36． 解同余方程組 37．解同余式≡11(mod125) 38．求模13的所有原根。 五、證明題：（7分/題2題=14分） 39、試證： ，（