【正文】 你的所說的求法及輾轉相除法實際算出（76501，9719）．解：有167。3 整除的進一步性質及最小公倍數(shù)1．證明兩整數(shù)a，b互質的充分與必要條件是：存在兩個整數(shù)s，t滿足條件．證明 必要性。又，2．證明定理3定理3 證：設，則∴又設則。故為無理數(shù)。算術基本定理1．試造不超過100的質數(shù)表解：用Eratosthenes篩選法（1）算出a（2）10內(nèi)的質數(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 1011 12 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 1002．求82798848及81057226635000的標準式．解：因為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，又所以；同理有。 k）都是非負整數(shù)，有由此知(a, b)[a, b] ==ab；從而有．５．若是質數(shù)（n1），則n是2的方冪．證：（反證法）設為奇數(shù)），則∵ ，∴ 為合數(shù)矛盾，故ｎ一定為２的方冪．167。又當，即。所以（ii）（證法2）由于，對稱，不妨設4. (i) 設函數(shù)f(x)在閉區(qū)間上是連續(xù)的，并且非負，證明:和式表示平面區(qū)域，內(nèi)的整點（整數(shù)坐標的點）的個數(shù).(ii) 設p，q是兩個互質的單正整數(shù)，證明：(iii) 設r0，T 是區(qū)域 內(nèi)的整點數(shù)，證明：(iv) 設n0，T 是區(qū)域 x0，y0， 內(nèi)的整點數(shù)，證明：證明：(略) 5. 設任一正整數(shù)，且，p 是質數(shù)，證明：在n!的標準分解式中，質因數(shù)p的指數(shù)是其中.證明：在n!的標準分解式中，質因數(shù)p的指數(shù)有限，即，所以而第二章 不定方程167。 0，y 179。次證，當Nabab時，因(a，b)=1，故原方程有整數(shù)解（x，y），一般解是要求xbt0，y會證明存在滿足這個不等式的整數(shù)可取使于是對于這個有：而這就證明了當時，原方程有非負整數(shù)解．1．證明定理2推論。2abd，n = 177。2abd，m = 177。解：設不定方程有解則(1)3/zx或3/z+x因為或3/z+x以下不妨設②， 設 與矛盾!這樣而③， ， 即 ④若由引理可設從而 ， 為證得為整數(shù)， 必須有a ， b均為奇數(shù)，且⑤若設，其中為一奇一偶，且有4．解不定方程：x2 + 3y2 = z2，x 0，y 0，z 0，(x, y ) = 1。反之，易驗證(ⅰ)或(ⅱ)是原不定方程的解，且x 0，y 0，z 0，(x, y) = 1。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一奇一偶。解：故正整數(shù)立得故設正整數(shù)，立得證明｜證明：∵ ∴ ∴ 即∣若是任一單數(shù)，則，證明：（數(shù)學歸納法）設 （1）時， 結論成立。 (4)設a = 2k + 1，當n = 1時，有a2 = (2k + 1)2 = 4k(k + 1) + 1 186。= 1 + q2k + 2，其中q206。是某個整數(shù)。2 剩余類及完全剩余系 證明，是模的一個完全剩余類。（2） 設對整數(shù)，結論成立，即若兩兩互質，令，當分別通過模的完全剩余系時，必過模的完全剩余系，其中。證明：（i）當時，?過模的絕對最小完全剩余系，也就是?表示中的個整數(shù)，事實上，當時，共有個值，且兩兩互不相等，否則此即又?的最大值是最小值是所以，結論成立。因為，由本節(jié)定理2得，亦過模的完全剩余系。證明： 兩對模不同余，所以它們分別取自模的不同剩余類，又恰是個與互質的整數(shù)，即它們恰取自與模互質的全部剩余類。特別地，當m=2時。證明：（數(shù)學歸納法）（1） 由定理4知k=2時，結論成立；（2） 設k1時結論成立，即，分別過模時，過模的簡化剩余系。由證明定理１推論，然后再由定理１推論證明定理１。證明：有理數(shù)表成純循環(huán)小數(shù)的充分與必要條件是有一正數(shù)t使得同余式成立，并且使上式成立的最小正整數(shù)t就是循環(huán)節(jié)的長度。先解同余式256x1由輾轉相除法，得上述同余式的解是原同余式的解是（1215，2755）=5，故先解 243x112 同的方法的得其解是原同余式的解是(1296，1935)=9，故原同余式有9個解。是同余方程ax 186。 b (mod p)驗證它是同余方程的解即可。孫子定理試解下列各題：（i） 十一數(shù)余三，七二數(shù)余二，十三數(shù)余一，問本數(shù)。應用證明同余式組 有解的充分與必要條件是，并且有解的情況下，適合的一切整數(shù)可由下式求出：其中是適合的一個整數(shù)。若同余式組有解，則 也有解。設；又由條件知，而，從而，所以，即，又由，則同余式組，必有解 （※）顯然，即（※）就是同余式組的解，據(jù)歸納性原理，結論成立。解：原同余式等價于 據(jù)孫子定理，可得故原同余式共有6個解是： 解同余式解： 故原同余式等價于1） 先解即 得②再解即 設 而由孫子定理設即原四條式有4個解是167。解：(ⅰ) 原同余方程等價于3x5 + 5x4 + 2x2 1 186。3代入知后者無解； (ⅱ) 原同余方程等價于2x4 + 2x3 + 3x 2 186。 177。 0 (mod 5)是否有六個解？解：(ⅰ) 2x3 x2 + 3x 1 186。p 1，pa則x n 186。證明 必要性 若方程(14)有解x0，則px0，由Fermat定理，得到= x0p 1 186。證畢。︱ 令則無多于個解，而 恰有個解，必有個解。 a(mod m)的一切解x都可以表示成x 186。 a(mod m)的任意一個解，則一次同余方程yx0 186。 x1k 186。 1 (mod m)；反之，易知如此形式的x是xk 186。解：若，則，上同余式即為從而，即有。反之，若有一解，即有：由于，故有解即有：即有：由，即有：即為的解，充分性得證。解：，由書中定理2知，模的簡化剩余系中個平方剩余分別與序列例2．試判斷下述同余方程是否是有解。證明：因為1為模的簡化剩余系中的平方剩余。若為平方剩余，為平方非剩余，則故從而為平方非剩余。3．證明：同余式，的解是 ，其中 證明：若有解，則有解， 設其解是：，即有： ，令而 ， 為整數(shù)由此兩式即得： 兩式相乘得： 取使得： 則 故其解為 4．證明同余式 的解是 證明：首先我們證明對任意： 有下式： 因為 ，于是 因此由威爾生定理得： 其次由，可令 ，代入上式即有 故原同余式的解為 167。求出以為平方剩余的質數(shù)的一般表達式；以為平方非剩余的質數(shù)的一般表達式。4 前節(jié)定理的證明 求以為平方剩余的質數(shù)的一般表達式，什么質數(shù)以為平方非剩余？解：由互反律 因此當它們同為或同時為時，一為，一為時，顯然，當為偶數(shù)，而時，當是奇數(shù)，即時。求以為最小平方非剩余的質數(shù)的一般表達式。5 雅可比符號 判斷167。在有解的情況下，應用 167。 由知，故故因此或若前式成立，那末 即 若則原同余式的解是 即 為原同余式的解。證明：（?。╋@然 （ⅱ）記有解，等價于方程組有解 易見的解為的解為的解為或二者不能同時成立，否則矛盾故它有兩個解，聯(lián)立方程組即可求出一切解。根據(jù)定義1直接計算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，d7(4) = 3，d7(5) = 6，d7(6) = 2。解：經(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，列表得a12345678910d11(a)110555101010522．求模14的全部原根。解：因j(29) = 28 = 227，由知2是模29的最小正原根。 16 (mod 17)。 8 (mod 16)，由此解得y1 186。 14 (mod 16)，查上表得x1 186。 2 (mod 17)。，由且僅有質因子2，而故同上理10也是模257的原根。 若，為的原根，則為奇數(shù) 類似于的討論，我們有，從而 從而 （mod m）故1的指標為。1． 可乘函數(shù)1．設是一個可乘函數(shù)，證明也是一個可乘函數(shù)．由此說明是可乘函數(shù)．證明：首先我們證明：設，若跑過的全部因子，跑過的全部因子，則跑過的全部因子，事實上，因為，故，且當，時，由于，得，反之任給，由于，設，顯然．因此　　　　　　　　　　　　　　　　故為一個可乘函數(shù)．　　　　　　　　　　　　　　　　　　　　(此為65頁)若，它為可乘函數(shù)．，且．若，它為可乘函數(shù)，且．故為可乘函數(shù)．2．　設是一個定義在一切正