第一章 整數(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è)整數(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ù)。 反過來|且|，假設(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〕式中的 證：由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ù)作分子以為分母的既約分?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．試造不超過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 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 89 90 91 92 93 94 95 96 97 98 99 100 解：因?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ù)，且 ，，， ，，， 那么，， 其中，， 證：， ∴ ∴ ，. ∴ ，又顯然 ∴ ，同理可得， 推廣 設(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；從而有． ５．假設(shè)是質(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 ， ， ， ∴ 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. (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ù)有限，即 ， 所以 而 第二章 不定方程 §2．1 習(xí)題 1、解以下不定方程 解： 原方程等價(jià)于： 顯然它有一個(gè)整數(shù)解 ， 故一般解為 原方程等價(jià)于： 顯然它有一個(gè)整數(shù)解 故一般解為 2、把100分成兩份，使一份可被整除，一份可被整除。 解：依題意 即求 的正整數(shù)解，解得 一般解是： 但除 外無(wú)其他正整數(shù)解，故有且只有 3、證明：二元一次不定方程 的非負(fù)整數(shù)解為 或 證明：當(dāng)時(shí)，原方程沒有整數(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、證明：二元一次不定方程 ，當(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 = ±(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)? 或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 ) = 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ā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 > 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，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)可任意選?。? 第三章 同余 1同余的概念及其根本性質(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ì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整除 證明 ：由上題(i)的特殊情形立得 ． 3．找出整數(shù)能被37，101整除有判別條件來。 解： 故正整數(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 + 2， 其中qÎZ，所以 = (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成立。 ； 解：； §2 剩余類及完全剩余系 1、 證明，，是模的一個(gè)完全剩余類。 證明：顯然對(duì)的不同取值，共有個(gè)值，故只需證這樣的個(gè)值，關(guān)于模的兩兩互不同余。 假設(shè) ∣，即 ∴或時(shí)， ．結(jié)論成立。 2、 假設(shè)是個(gè)兩兩互質(zhì)的正整數(shù)，分別通過模的完全剩余類，那么 通過模的完全剩余系，其中， 證明：〔數(shù)學(xué)歸納法〕 （1） 根據(jù)本節(jié)定理3，知時(shí)，結(jié)論成立。 （2） 設(shè)對(duì)整數(shù)，結(jié)論成立，即假設(shè)兩兩互質(zhì)，令，當(dāng)分別通過模的完全剩余系時(shí)，必過模 的完全剩余系，其中。 現(xiàn)增加使 ， 令，， 那么易知， 再令， 當(dāng)過模的完全剩余系，過模的完全剩余系時(shí)，據(jù)本節(jié)定理3，必過模的完全剩余系，即對(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、假設(shè)是K個(gè)兩兩互質(zhì)的正整數(shù)，分別過模的完全剩余系，那么 ? 通過模的完全剩余系。 證明：〔數(shù)學(xué)歸納法〕 〔1〕時(shí)，分別過模的完全剩余系時(shí)， 共有個(gè)值，且假設(shè) ，且 ，，即時(shí)結(jié)論成立； 〔2〕設(shè)當(dāng)分別過模的完全剩余系時(shí)， 過模的完全剩余系。 因?yàn)椋杀竟?jié)定理2得， 亦過模的完全剩余系。 當(dāng)分別過模的完全剩余系時(shí)， 2有個(gè)值，且據(jù)歸納假設(shè)， 假設(shè) ； ，，…， ，，…，。 所以過模的完全剩余系。 3．簡(jiǎn)化剩余系與歐拉函數(shù) 1．證明定理2：假設(shè)是與互質(zhì)的整數(shù)， 并且兩對(duì)模不同余，那么是模的一個(gè)簡(jiǎn)化剩余系。 證明： 兩對(duì)模不同余，所以它們分別取自模的不同剩余類， 又恰是個(gè)與互質(zhì)的整數(shù)，即它們恰取自與模互質(zhì)的全部剩余類。 2．假設(shè)是大于1的正整數(shù)，是整數(shù)，，通過的簡(jiǎn)化剩余系， 那么，其中表示展布在所通過的一切值上的和式。 證明：由定理3知，通過的簡(jiǎn)化剩余系： ，其中0＜＜且， 而〔〕。 假設(shè)＞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)分解式， 那么， = =a 4．假設(shè)是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)用 １、如果今天是星期一，問從今天起再過天是星期幾？ 解：假設(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)式展開即得 設(shè)時(shí)，結(jié)論成立，即 當(dāng)時(shí)， 結(jié)論成立。 在的結(jié)論中，令，即得： 　　　　　 即定理１推論成立。 進(jìn)一步，設(shè)，那么　 固對(duì)任一整數(shù)，假設(shè)，那么由上述已證性質(zhì)得： 存在，使 故=〔〕 依此類推可得． 假設(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 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è)是正整數(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è)是正整數(shù)，是實(shí)數(shù)，，證明同余式 有解． 證明: 因 故同余式 必有解， (i) 假設(shè) ，那么結(jié)論成立; (ii) 假設(shè)，令，， 那么 又假設(shè) 那么由 ，結(jié)論成立． 假設(shè) 令 那么 又假設(shè) 那么由 即 故 結(jié)論成立。 假設(shè)又令 那么 重復(fù)上述討論：即假設(shè) 那么結(jié)論成立， 假設(shè)又令 `````` 例解同余方程組 解：互質(zhì)，故原方程組對(duì)模有唯一解 即 根據(jù)孫子定理方程組的解是 注意到 故有限步后，必有 其中即結(jié)論成立。 孫子定理 試解以下各題： （i） 十一數(shù)余三，七二數(shù)余二，十三數(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ù)可由下式求出： 其中是適合的一個(gè)整數(shù)。 證明： 即 設(shè)有解，即 故此得，必要性成立； 反之，設(shè)即 那么由§1定理，知方程必有解， 設(shè)其解為，即 令那么易見： 且 即有解，充分性得證。 進(jìn)一步，假設(shè)有解，那么 即是的公倍數(shù)，當(dāng)然也是的倍數(shù)， 故假設(shè)是的一個(gè)解，那么的任一解必滿足 。 假設(shè)同余式組有解， 那么 也有解。從而由知必有 ，必要性成立。 下證充分性。首先，推，用歸納法易證： 又由知時(shí)，充分性也成立； 現(xiàn)設(shè)同余式組 有解， 即。 設(shè)；又由條件知， 而，從而， 所以， 即， 又由，那么同余式組， 必有解 〔※〕 顯然，即〔※〕就是同余式組的解，據(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 (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 代入，知后者有解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ù)，故原方程沒有三個(gè)解； (ⅱ) 因?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è) 那么 但 那么由 可得。 它有個(gè)解。 ︱ 令 那么 無(wú)多于個(gè)解，而 恰有個(gè)解，必有個(gè)解。 2．設(shè)n是整數(shù)，〔a，m〕=1，且同余式 有一解，證明這個(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è)解，那么一次同余方程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è)，試求出它的一切解來。 解：假設(shè)，那么，上同余式即為 從而，即有。 易見，當(dāng)為偶數(shù)時(shí)，，那么，上同余式有解： ，共有個(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，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)化剩余系中的平方剩余。假設(shè)模的簡(jiǎn)化剩余系中均為平方剩余，考慮模的絕對(duì)最小簡(jiǎn)化剩余系： 它們的平方為模下的個(gè)數(shù)： 由假設(shè)模的簡(jiǎn)化剩余系中任一個(gè)數(shù)與上個(gè)數(shù)同余，而模的簡(jiǎn)化剩余系中有個(gè)數(shù)，故必有兩個(gè)互相同余，矛盾。從而必有平方非剩余存在。 假設(shè)為平方剩余，那么故從而也為平方剩余。假設(shè)為平方剩余，為平方非剩余，那么 故從而為平方非剩余。 設(shè)為模的簡(jiǎn)化剩余系中的平方剩余；為模的簡(jiǎn)化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。 3．證明：同余式，的解是 ，其中 證明：假設(shè)有解，那么有解， 設(shè)其解是：，即有： ， 令 而 ， 為整數(shù) 由此兩式即得： 兩式相乘得： 取使得： 那么 故其解為 4．證明同余式 的解是 證明：首先我們證明對(duì)任意： 有下式： 因?yàn)?，于是 因此由威爾生定理得： 其次由，可令 ，代入上式 即有 故原同余式的解為 §3 勒讓得符號(hào) 1．用本節(jié)方法判斷以下同余式是否有解 其中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)它們同為或同時(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ù)形如， 其中只有滿足 故或時(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的推論，求同余式 ，的解。 解：同余式有解，故 由知 故即為原同余式的解。 由知，故 故 因此或 假設(shè)前式成立，那末 即 假設(shè)那么原同余式的解是 即 為原同余式的解。 假設(shè)后式成立，那末 由§3定理1的推論知，2是模p的平方剩余，即 于是： 假設(shè)那么原同余式的解是 故為原同余式的解． §6 合數(shù)模的情形 1. 解同余式 ， 解：從同余式 得 令代入得出 從而即有 故， 再令代入 得出 ， 即 從而 故 所以 為所給同余式的解 從而所有的解為： 〔ⅱ〕 ，故有四解 記代入，即有： 解得 記，代入 即有：，解得： 又記，代入 即有，解得: 故為其一解 其余三解為： 2．〔ⅰ〕證明同余式與同余式等價(jià)，〔ⅱ〕應(yīng)用〔ⅰ〕舉出一個(gè)求同余式的一切解的方法。 證明：〔ⅰ〕顯然 〔ⅱ〕記 有解，等價(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 假設(shè)，那么，故; 假設(shè)，而，q-1為偶數(shù)， 記q-1=2x，那么，又假設(shè) 故q=2px+1得證。 (ii)設(shè)q為的奇質(zhì)因數(shù)，那么 從而，從而a對(duì)模q的指數(shù)．故，2，p，2p之一 假設(shè)，那么，從而 即有，不可能，故 假設(shè)，那么，而(否那么) 故 假設(shè)，那么，而有，不可能 假設(shè)，那么由，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，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 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 = 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 º 16 (mod 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 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的次剩余，那么存在，使得 又由歐拉定理 故 ，矛盾！ 充分性，假設(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à)于： 查表知，故： 由于，故上式由 5個(gè)解， 解之得： 查表知：原同余式的5個(gè)解為： 4．設(shè)模m〔m．>2〕的原根是存在的，試證對(duì)模m的任一原根來說，的指標(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)： 〔mod 〕 故 〔mod 〕 由指標(biāo)的定義知： 〔mod m〕 兩邊對(duì)原根取指標(biāo)： 〔mod 〕 故 〔mod 〕。 〔證畢〕 第九章　數(shù)論函數(shù) §1． 可乘函數(shù) 1．設(shè)是一個(gè)可乘函數(shù)，證明也是一個(gè)可乘函數(shù)．由此說明是可乘函數(shù)． 證明：首先我們證明：設(shè)，假設(shè)跑過的全部因子，跑過的全部因子，那么跑過的全部因子，事實(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ì)，使得最?。僭O(shè)，那么，即，又，為可乘函數(shù)，故有矛盾！ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　 假設(shè)，那么對(duì)所有正態(tài)數(shù)對(duì)，有 于是有： = = 因?yàn)?，? 此與 為可乘函數(shù)矛盾！ 3．證明： 證明：首先易證，假設(shè)d為的正約數(shù)，那么a的完全剩余系中與的最大公約數(shù)是d的個(gè)數(shù)為。 其次，假設(shè)為的所有正約數(shù)。那么也是的所有正約數(shù)，于是 最后，在的完全剩余系中住一數(shù)與的最大公約數(shù)必定是中某一個(gè)，而完全剩余系中與最大公約數(shù)為的數(shù)有個(gè)，所以 4．試計(jì)祘和式 解：此題較復(fù)雜，下分?jǐn)?shù)步解之： ?反演公式 設(shè)和是兩個(gè)數(shù)論函數(shù)，且，那么反之亦然 事實(shí)上， 反之，類似可得。參見習(xí)題5及6 。 ②假設(shè)是定義在閉區(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ù)，并且： 試證： 證明：設(shè) ， 即，那么 由推論2．3知，其內(nèi)部之和只有當(dāng)c=a時(shí)為１，c<a時(shí)，為０，故上式右邊等于． 設(shè)是任一函數(shù)，并且: 證明: 證明:其證法與上習(xí)題類似，我們有: 7．設(shè)是定義在實(shí)數(shù)上的兩個(gè)函數(shù)，并且對(duì)于任何不小于1的實(shí)數(shù)x來說: 那么 反之，亦然． 證明: 〔〕 記，那么，并且遍取數(shù)目，那么 〔〕 比擬兩式即有 上式右邊除第一頁(yè)其余諾項(xiàng)都等于0〔推論2．3〕右上式右邊等于 類似可證明它的逆定理成立。