《初等數論(閔嗣鶴、嚴士健)》第三版習題解答

《初等數論》習題解答（第三版）廣東石油化工學院111/111《初等數論(閔嗣鶴、嚴士健)》第三版習題解答第一章整數的可除性§1整除的概念·帶余除法1．證明定理3定理3若都是得倍數，是任意n個整數，則是得倍數．證明：都是的倍數。存在個整數使又是任意個整數即是的整數2．證明證明又，是連續(xù)的三個整數故從而可知3．若是形如（x，y是任意整數，a，b是兩不全為零的整數）的數中最小整數，則．證：不全為在整數集合中存在正整數，因而有形如的最小整數，由帶余除法有則，由是中的最小整數知（為任意整數）又有，故4．若a，b是任意二整數，且，證明：存在兩個整數s，t使得成立，并且當b是奇數時，s，t是唯一存在的．當b是偶數時結果如何？證：作序列則必在此序列的某兩項之間即存在一個整數，使成立當為偶數時，若則令，則有若則令，則同樣有當為奇數時，若則令，則有若，則令，則同樣有，綜上所述，存在性得證．下證唯一性當為奇數時，設則而矛盾故當為偶數時，不唯一，舉例如下：此時為整數§2最大公因數與輾轉相除法1．證明推論4.1推論4.1a，b證：設是a，b的任一公因數，|a，|b由帶余除法|，|，┄,|,即是的因數。反過來|且|，若則，所以的因數都是的公因數，從而的公因數與的因數相同。2．證明：見本書P2，P3第3題證明。3．應用§1習題4證明任意兩整數的最大公因數存在，并說明其求法，試用你的所說的求法及輾轉相除法實際算出（76501，9719）．解：有§1習題4知：使。，，使如此類推知：且而b是一個有限數，使，存在其求法為：4．證明本節(jié)（1）式中的證：由P3§1習題4知在（1）式中有，而，，即§3整除的進一步性質及最小公倍數1．證明兩整數a，b互質的充分與必要條件是：存在兩個整數s，t滿足條件．證明必要性。若，則由推論1.1知存在兩個整數s，t滿足：，充分性。若存在整數s，t使as+bt=1，則a，b不全為0。又因為，所以即。又，2．證明定理3定理3證：設，則∴又設則。反之若，則，從而，即=3．設（1）是一個整數系數多項式且，都不是零，則（1）的根只能是以的因數作分子以為分母的既約分數，并由此推出不是有理數．證：設（1）的任一有理根為，。則（2）由，所以q整除上式的右端，所以，又，所以；又由（2）有因為p整除上式的右端，所以，，所以故（1）的有理根為，且。假設為有理數，，次方程為整系數方程，則由上述結論，可知其有有理根只能是，這與為其有理根矛盾。故為無理數。另證，設為有理數=，則但由知，矛盾，故不是有理數?！?質數·算術基本定理1．試造不超過100的質數表解：用Eratosthenes篩選法（1）算出a（2）10內的質數為：2，3，5，7（3）劃掉2，3，5，7的倍數，剩下的是100內的素數將不超過100的正整數排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002．求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，又所以；同理有。3．證明推論3.3并推廣到n個正整數的情形．推論3.3設a，b是任意兩個正整數，且，，，，，，則，，其中，，證：，∴∴，.∴，又顯然∴，同理可得，推廣設,,(其中為質數為任意n個正整數)，則4．應用推論3.3證明§3的定理4（ii）證：設，其中p1,p2,,pk是互不相同的素數，i，i（1ik）都是非負整數，有由此知(a,b)[a,b]==ab；從而有．５．若是質數（n>1），則n是2的方冪．證：（反證法）設為奇數），則∵，∴為合數矛盾，故ｎ一定為２的方冪．§5函數[x],{x}及其在數論中的一個應用1．求30！的標準分解式．解：30內的素數為2，3，5，7，11，13，17，19，23，29，，，∴2．設n是任一正整數，是實數，證明：(i)(ii)證：(i)設.則由性質II知,所以,所以，所以，又在ｍ與ｍ+１之間只有唯一整數ｍ，所以．(ii)[證法一]設,則=1\*GB3①當時,;=2\*GB3②當時,;[證法二]令,是以為周期的函數。又當，即。[評注]：[證一]充分體現了常規(guī)方法的特點，而[證二]則表現了較高的技巧。3．設，是任意二實數，證明：(i)或(ii)證明：（i）由高斯函數[x]的定義有。則當當故（ii）設，則有下面分兩個區(qū)間討論：=1\*GB3①若，則，所以，所以②若，則，所以。所以（ii）（證法2）由于，對稱，不妨設4.(i)設函數f(x)在閉區(qū)間上是連續(xù)的，并且非負，證明:和式表示平面區(qū)域，內的整點（整數坐標的點）的個數.(ii)設p，q是兩個互質的單正整數，證明：(iii)設r>0，T是區(qū)域(iv)設n>0，T是區(qū)域x>0證明：(略)5.設任一正整數，且，p是質數，，證明：在n!的標準分解式中，質因數p的指數是其中.證明：在n!的標準分解式中，質因數p的指數有限，即，所以而第二章不定方程§2．1習題1、解下列不定方程解：原方程等價于：顯然它有一個整數解，故一般解為原方程等價于：顯然它有一個整數解故一般解為2、把100分成兩份，使一份可被整除，一份可被整除。解：依題意即求的正整數解，解得一般解是：但除外無其他正整數解，故有且只有3、證明：二元一次不定方程的非負整數解為或證明：當時，原方程沒有整數解，而故命題正確當時，原方程有且只有一個非負整數解而因為所以原方程有整數解其中，由于，故中一正一負，可設原方程的一般解是：要求，僅當是整數時，才能取，否則故這個不等式的整數解個數是：當是整數時因而當不是整數時因而所以證明2：二元一次不定方程axby=N的一切整數解為，tZ，于是由x0，y0得，但區(qū)間的長度是，故此區(qū)間內的整數個數為1。：4、證明：二元一次不定方程，當時有非負整數解，則不然。證明：先證后一點，當時，原方程有非負整數解則，這是不可能的。次證，當N>ab-a-b時，因(a，b)=1，故原方程有整數解（x，y），一般解是要求x-bt0，y會證明存在滿足這個不等式的整數可取使于是對于這個有：而這就證明了當時，原方程有非負整數解．1．證明定理2推論。推論單位圓周上座標都是有理數的點（稱為有理點），可以寫成的形式，其中a與b是不全為零的整數。證明：設有理數（m0）滿足方程x2y2=1，即l2n2=m2，于是得l=2abd，n=(a2b2)d，m=(a2b2)d或l=(a2b2)d，m=2abd，m=(a2b2)d，由此得(x,y)=。反之，代入方程x2y2=1即知這樣的點在單位圓周上。2．求出不定方程的一切正整數解的公式。解：設不定方程有解則(1)3/z-x或3/z+x因為或3/z+x以下不妨設=2\*GB3②，設與矛盾!這樣而=3\*GB3③，，即=4\*GB3④若由引理可設從而，為證得為整數，必須有a，b均為奇數，且=5\*GB3⑤若設，其中為一奇一偶，且有4．解不定方程：x23y2=z2，x>0，y>0，z>0，(x,y)=1。解：設(zx,zx)=d，易知d=1或2。由(zx)(zx)=3y2得zx=3da2，zx=db2，y=dab或zx=db2，zx=3da2，y=dab，a>0，b>0，(a,b)=1。(ⅰ)當d=1：，a>0，b>0，(a,b)=1，3b，a,b同為奇數；(ⅱ)當d=2：x=|b23a2|，y=2ab，z=b23a2，a>0，b>0，(a,b)=1，3b，a,b一奇一偶。反之，易驗證(ⅰ)或(ⅱ)是原不定方程的解，且x>0，y>0，z>0，(x,y)=1。3．證明不等式方程的一切正整數解．可以寫成公式:∣∣，其中證明:由定理1知道原方程的解是，且c，d為一奇一偶，其中，，且a，b為一奇一偶．所以∣∣，是原方程的正整數解，原方程正整數的解有:，，6．求方程x2y2=z4的滿足(x,y)=1，2x的正整數解。解：設x，y，z是x2y2=z4的滿足(x,y)=1，2x的正整數解，則x=2ab，y=a2b2，z2=a2b2，a>b>0，(a,b)=1，a,b一奇一偶，再由z2=a2b2得a=2uv，b=u2v2，z=u2v2或a=u2v2，b=2uv，z=u2v2，u>v>0，(u,v)=1，u,v一奇一偶，于是得x=4uv(u2v2)，y=|u4v46u2v2|，z=u2v2，u>v>0，(u,v)=1，u,v一奇一偶。反之，易驗證它是原不定方程的整數解，且x>0，y>0，z>0，(x,y)=1，2x。其中正負號可任意選?。谌峦?同余的概念及其基本性質證明（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的任一正公因數，則(iv)若ab(modm)，則ab(modd)．證明：（i）據性質戊，由得進一步，則最后據性質丁，可得：（modm）(ii)據定理1，ab(modm)又據定理1，即得（iii）據定理1，ab(modm)即a-b=ms(sz)，即仍據定理1，立得(iv)據定理1，ab(modm)又故2、設正整數試證11整除的充分且必要條件是11整除證明：由上題(i)的特殊情形立得．3．找出整數能被37，101整除有判別條件來。解：故正整數立得故設正整數，立得4、證明｜證明：∵∴∴即∣5、若是任一單數，則，證明：（數學歸納法）設（1）時，，結論成立。（2）設時，結論成立，即：，而故時，結論也成立；∴時，結論也成立。證明：若2a，n是正整數，則1(mod2n+2)。(4)設a=2k1，當n=1時，有a2=(2k1)2=4k(k1)11(mod23)，即式(4)成立。設式(4)對于n=k成立，則有1(mod2k+2)=1q2k+2，其中qZ，所以=(1q2k+2)2=1q2k+31(mod2k+3)，其中q是某個整數。這說明式(4)當n=k1也成立。由歸納法知式(4)對所有正整數n成立。；解：；§2剩余類及完全剩余系證明，，是模的一個完全剩余類。證明：顯然對的不同取值，共有個值，故只需證這樣的個值，關于模的兩兩互不同余。若∣，即∴或時，．結論成立。若是個兩兩互質的正整數，分別通過模的完全剩余類，則通過模的完全剩余系，其中，證明：（數學歸納法）根據本節(jié)定理3，知時，結論成立。設對整數，結論成立，即若兩兩互質，令，當分別通過模的完全剩余系時，必過模的完全剩余系，其中?，F增加使，令，，則易知，再令，當過模的完全剩余系，過模的完全剩余系時，據本節(jié)定理3，必過模的完全剩余系，即對結論成立。3、（i）證明整數中每一個整數有而且只有一種方法表示成的形狀，其中；反之，中每一數都。（ii）說明應用個特別的砝碼，在天平上可以量出1到H中的任意一個斤數。證明：（i）當時，過模的絕對最小完全剩余系，也就是表示中的個整數，事實上，當時，共有個值，且兩兩互不相等，否則此即又的最大值是最小值是所以，結論成立。（ii）特制個砝碼分別重斤，把要稱的物體及取-1的砝碼放在天平的右盤，取1的砝碼放在左盤，則從（i）的結論知，當取適當的值時，可使之值等于你所要稱的物體的斤數。4、若是K個兩兩互質的正整數，分別過模的完全剩余系，則通過模的完全剩余系。證明：（數學歸納法）（1）時，分別過模的完全剩余系時，共有個值，且若，且，，即時結論成立；（2）設當分別過模的完全剩余系時，過模的完全剩余系。因為，由本節(jié)定理2得，亦過模的完全剩余系。當分別過模的完全剩余系時，2有個值，且據歸納假設，若；，，…，，，…，。所以過模的完全剩余系。3．簡化剩余系與歐拉函數1．證明定理2：若是與互質的整數，并且兩對模不同余，則是模的一個簡化剩余系。證明：兩對模不同余，所以它們分別取自模的不同剩余類，又恰是個與互質的整數，即它們恰取自與?；ベ|的全部剩余類。2．若是大于1的正整數，是整數，，通過的簡化剩余系，則，其中表示展布在所通過的一切值上的和式。證明：由定理3知，通過的簡化剩余系：，其中0＜＜且，而（）。若＞2，則必是偶數，又由，得，且易見，故所以左邊每一項都存在另一項，使得，右邊共有對，此即。特別地，當m=2時，。3．（=1\*romani）證明，p質數。(=2\*romanii)證明，其中展布在a的一切正整數上的和式。證明：（=1\*romani）因為，所以==(=2\*romanii)設是a的標準分解式，則，==a4．若是k個兩兩互質的正整數，分別通過模的簡化剩余系，則通過模的簡化剩余系，其中。證明：（數學歸納法）由定理4知k=2時，結論成立；設k-1時結論成立，即，分別過模時，過模的簡化剩余系。顯見，則又由定理4知，通過模的簡化剩余系，注意到：所以，通過模m的簡化剩余系。．歐拉定理費馬定理及其對循環(huán)小數的應用１、如果今天是星期一，問從今天起再過天是星期幾？解：若被除的非負最小剩余是，則這一天就是星期（當時是星期日）．，由費馬定理得，又即這一天是星期五．２、求被除的余數。解：，據歐拉定理，易知（１）又故則．由（１）即得．由以上計算，知．．３、證明下列事實但不許用定理１推論：若是質數，是整數，則。由證明定理１推論，然后再由定理１推論證明定理１。證明對應用數學歸納法：當時，按二項式展開即得設時，結論成立，即當時，結論成立。在的結論中，令，即得：即定理１推論成立。進一步，設，則固對任一整數，若，則由上述已證性質得：存在，使故=（）依此類推可得．若，則，定理成立。4、證明：有理數表成純循環(huán)小數的充分與必要條件是有一正數t使得同余式成立，并且使上式成立的最小正整數t就是循環(huán)節(jié)的長度。證明：必要性，若結論成立，則由定理2知（b，10）=1，令t=則據歐拉定理得；充分性，若有正數t，滿足令t為使上式成立的最小正整數，且=且。以下參照課本51頁的證明可得：=即可表成循環(huán)小數，但循環(huán)節(jié)的長度就是t。第四章同余式1基本概念及一次同余式例解同余式解：（12，45）=同余多項式有3個解而原同余式為4與也一樣所以原同余式的3個解是（ｔ＝０、１、２）即，，求下列各同余式的解256x1791215x5601296x1125337是素數，，原同余式有唯一解。先解同余式256x1由輾轉相除法，得上述同余式的解是原同余式的解是（1215，2755）=5，故先解243x112同的方法的得其解是原同余式的解是(1296，1935)=9，故原同余式有9個解。由144x125得原同余式的解是2．求聯立同余式的解。解：據同余式的有關性質，為所求的解。3．(i)設是正整數，．證明是同余式的解(ii)設是質數，，證明是同余式的解．證明:(i)，有唯一解．而據歐拉定理，得，即是的解．(ii)即有唯一解又個連續(xù)整數之積必被所整除，故可令則即即是的解．設p是素數，0<a<p，證明：(modp)。是同余方程axb(modp)的解。解：首先易知是整數，又由(a,p)=1知方程axb(modp)解唯一，故只須將(modp)代入axb(modp)驗證它是同余方程的解即可。4．設是正整數，是實數，，證明同余式有解．證明:因故同余式必有解，若，則結論成立;若，令，，則又若則由，結論成立．若令則又若則由即故結論成立。若又令則重復上述討論：即若則結論成立，若又令``````例解同余方程組解：互質，故原方程組對模有唯一解即根據孫子定理方程組的解是注意到故有限步后，必有其中即結論成立。孫子定理試解下列各題：十一數余三，七二數余二，十三數余一，問本數。二數余一，五數余二，七數余三，九數余四，問本數。（楊輝：續(xù)古摘奇算法（1275））。解：（i）依題意得則據孫子定理，上述方程組有唯一解由故原方程組的解是(ii)依題意得2、（i）設是三個正整數，證明：．（ii）設證明：同余式組（1）有解的充分與必要條件是在有解的情況下，適合（1）的一切整數可由下式求出：其中是適合的一個整數。應用證明同余式組有解的充分與必要條件是，并且有解的情況下，適合的一切整數可由下式求出：其中是適合的一個整數。證明：即設有解，即故此得，必要性成立；反之，設即則由§1定理，知方程必有解，設其解為，即令則易見：且即有解，充分性得證。進一步，若有解，則即是的公倍數，當然也是的倍數，故若是的一個解，則的任一解必滿足。若同余式組有解，則也有解。從而由知必有，必要性成立。下證充分性。首先，推，用歸納法易證：又由知時，充分性也成立；現設同余式組有解，即。設；又由條件知，而，從而，所以，即，又由，則同余式組，必有解（※）顯然，即（※）就是同余式組的解，據歸納性原理，結論成立。后一結論由上述過程亦成立?！?高次同余式的解數及解法解同余式。解：原同余式等價于據孫子定理，可得故原同余式共有6個解是：解同余式解：故原同余式等價于先解即得②再解即設而由孫子定理設即原四條式有4個解是§4．質數模的同余式補充例子：1．解同余方程：(ⅰ)3x112x85x410(mod7)；(ⅱ)4x203x122x73x20(mod5)。解：(ⅰ)原同余方程等價于3x55x42x210(mod7)，用x=0，1，2，3代入知后者無解；(ⅱ)原同余方程等價于2x42x33x20(mod5)，將x=0，1，2代入，知后者有解x1(mod5)。2．判定(ⅰ)2x3x23x10(mod5)是否有三個解；(ⅱ)x62x54x230(mod5)是否有六個解？解：(ⅰ)2x3x23x10(mod5)等價于x33x24x30(mod5)，又x5x=(x33x24x3)(x23x5)+(6x212x15)，其中r(x)=6x212x15的系數不都是5的倍數，故原方程沒有三個解；(ⅱ)因為這是對模5的同余方程，故原方程不可能有六個解。定理5若p是素數，np1，pa則xna(modp)(14)有解的充要條件是1(modp)。(15)若有解，則解數為n。證明必要性若方程(14)有解x0，則px0，由Fermat定理，得到=x0p11(modp)。充分性若式(15)成立，則其中P(x)是關于x的整系數多項式。由定理4可知同余方程(14)有n個解。證畢。設︱，，．證明同余式有解的充分必要條件是，并且在有解的情況下就有個解。證明：設則但則由可得。它有個解。︱令則無多于個解，而恰有個解，必有個解。2．設n是整數，（a，m）=1，且已知同余式有一解，證明這個同余式的一切解可以表成其中y是同余式的解。證明：設均是的解，則，（a，m）=1，（，m）=(，m)=1則由第三章定理3．3知，必存在y，使，．故原同余式的任一解可表示為而y滿足3．設(a,m)=1，k與m是正整數，又設x0ka(modm)，證明同余方程xka(modm)的一切解x都可以表示成xyx0(modm)，其中y滿足同余方程yk1(modm)。解：設x1是xka(modm)的任意一個解，則一次同余方程yx0x1(modm)有解y，再由ykaykx0k(yx0)kx1ka(modm)得yk1(modm)，即x1可以表示成xyx0(modm)，其中y滿足同余方程yk1(modm)；反之，易知如此形式的x是xka(modm)的解。

二次同余式與平方剩余§1一般二次同余式在同余式中，若，試求出它的一切解來。解：若，則，上同余式即為從而，即有。易見，當為偶數時，，則，上同余式有解：，共有個解當為奇數時，，上同余式有解：，共有個解。2、證明：同余式有解的充分必要條件是有解，并且前一同余式的一切解可由后一同余式的解導出。證明：因，故用乘后再配方，即得仍記為，即有由以上討論即知若為的解，則為的解，必要性得證。反之，若有一解，即有：由于，故有解即有：即有：由，即有：即為的解，充分性得證。由充分性的討論即知的解可由的解導出?！?單質數的平方剩余與平方非剩余求出模的平方剩余與平方非剩余。解：，由書中定理2知，模的簡化剩余系中個平方剩余分別與序列例2．試判斷下述同余方程是否是有解。（1）（2）（3）中之一數同余，而故模37的平方剩余為：1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36而其它的18個數為模37的平方非剩余：2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，352．應用前幾章的結果證明:模的簡化剩余系中一定有平方剩余及平方非剩余存在，證明兩個平方剩余的乘積是平方剩余;平方剩余與平方非剩余的乘積是平方非剩余。應用、證明：模的簡化剩余系中平方剩余與平方非剩余的個數各為。證明：因為1為模的簡化剩余系中的平方剩余。若模的簡化剩余系中均為平方剩余，考慮模的絕對最小簡化剩余系：它們的平方為模下的個數：由假設模的簡化剩余系中任一個數與上個數同余，而模的簡化剩余系中有個數，故必有兩個互相同余，矛盾。從而必有平方非剩余存在。若為平方剩余，則故從而也為平方剩余。若為平方剩余，為平方非剩余，則故從而為平方非剩余。設為模的簡化剩余系中的平方剩余；為模的簡化剩余系中的平方非剩余。由知，為平方非剩余，顯然互不同余。故反之，由為平方剩余知故，得證。3．證明：同余式，的解是，其中證明：若有解，則有解，設其解是：，即有：，令而，為整數由此兩式即得：兩式相乘得：取使得：則故其解為4．證明同余式的解是證明：首先我們證明對任意：有下式：因為，于是因此由威爾生定理得： 其次由，可令，代入上式即有故原同余式的解為§3勒讓得符號1．用本節(jié)方法判斷下列同余式是否有解其中503，563，769，1013都是質數解：，有解。，有解。，有解。2、求出以為平方剩余的質數的一般表達式；以為平方非剩余的質數的一般表達式。解：為模平方剩余時，必有，必有，故，必有，故為模平方非剩余時，必有，必有，故，必有，故3、設是正整數，及都是質數，說明由此證明：。證明：當時，由本節(jié)定理1的推論知為平方剩余，應用歐拉判別條件即有由，即得出而都是形如的素數，并且，所以?！?前節(jié)定理的證明求以為平方剩余的質數的一般表達式，什么質數以為平方非剩余？解：由互反律因此當它們同為或同時為時，，一為，一為時，顯然，當為偶數，而時，，當是奇數，即時，。再因為是奇質數，關于模我們有或，當時，當時，這樣為平方剩余時，為下方程組的解或由孫子定理，即可知或，立即當時，為平方剩余。為平方非剩余時，為下方程組的解或由孫子定理，即可知或，立即當時，為平方非剩余。因為當為偶數，，或為奇數，時，即或時，為平方剩余，類似或，為平方非剩余。2、求以為最小平方非剩余的質數的一般表達式。解：由上題知以為平方非剩余的質數滿足：又由為模的最小平方非剩余，故從而（§3推證）滿足的素數形如，其中只有滿足故或時，為它的最小平方非剩余。§5雅可比符號判斷§3習題1所列各同余式是否有解。略求出下列同余式的解數：，其中是一個質數。解：，故故，即的解數為0．，故解數為2．3．在有解的情況下，應用定理1，求同余式，的解。在有解的情況下，應用§2定理1及§3定理1的推論，求同余式，的解。解：同余式有解，故由知故即為原同余式的解。由知，故故因此或若前式成立，那末即若則原同余式的解是即為原同余式的解。若后式成立，那末由§3定理1的推論知，2是模p的平方剩余，即于是：若則原同余式的解是故為原同余式的解．§6合數模的情形解同余式，解：從同余式得令代入得出從而即有故，再令代入得出，即從而故所以為所給同余式的解從而所有的解為：（ⅱ），故有四解記代入，即有：解得記，代入即有：，解得：又記，代入即有，解得:故為其一解其余三解為：2．（?。┳C明同余式與同余式等價，（ⅱ）應用（ⅰ）舉出一個求同余式的一切解的方法。證明：（?。╋@然（ⅱ）記有解，等價于方程組有解 易見的解為的解為的解為或二者不能同時成立，否則矛盾故它有兩個解，聯立方程組即可求出一切解。第六章原根與指標設p是單質數，a是大于1的整數，證明:(i)的奇質數q是a-1的因數或是形如2px+1的整數，其中x是整數(ii)的單質因數是a+1的因數或是形如2px+1的整數，其中x是整數證明(i)設則設a對模q的質數是是質數從而或p若，則，故;若，而，q-1為偶數，記q-1=2x，則，又假設故q=2px+1得證。(ii)設q為的奇質因數，則從而，從而a對模q的指數．故，2，p，2p之一若，則，從而即有，不可能，故若，則，而(否則)故若，則，而有，不可能若，則由，q－1＝2m記m＝px，則q＝2px+1，得證設對模m的指數是，試證對模m的指數是證明：設對模m的指數為，則而，股反之故，從而=得證例1求1，2，3，4，5，6對模7的指數。根據定義1直接計算，得到7(1)=1，7(2)=3，7(3)=6，7(4)=3，7(5)=6，7(6)=2。例1中的結果可列表如下：a1234567(a)136362這樣的表稱為指數表。這個表就是模7的指數表。下面是模10的指數表：a137910(a)14421．寫出模11的指數表。解：經計算得11(1)=1，11(2)=10，11(3)=5，11(4)=5，11(5)=5，11(6)=10，11(7)=10，11(8)=10，11(9)=5，11(10)=2，列表得a1234567891011(a)110555101010522．求模14的全部原根。解：x3，5(mod14)是模14的全部原根。1．求模29的最小正原根。解：因(29)=28=227，由知2是模29的最小正原根。2．分別求模293和模2293的原根。解：由2是模29的原根及2291=228=2281(mod292)知2是模293的原根；由2是模293的原根及2是偶數知2+293是模2293的原根。3．解同余方程：x1216(mod17)。解：易得3是模17的原根，3i（i=0,1,2,,15）構成模17的簡化剩余系，列表為 i012345673i(mod17)139101351511i891011121314153i(mod17)16148741226由上表知3816(mod17)，設x5y(mod17)，則12y8(mod16)，由此解得y12，y26，y310，y414(mod16)，查上表得x19，x215，x38，x42(mod17)。3指標及n次剩余1．設是的一切不同的質因數，證明g是模m的一個原根的充要條件是g對模m的次非剩余。證明：必要性，設g為模m的一個原根由2Th5知若g為模m的次剩余，則存在，使得又由歐拉定理故，矛盾！充分性，若g不為模m的一個原根，由2Th5知存在，使得：設為模m的一個原根，則對上式兩邊關于取指標：記，則由指標的定義即有：故即為同余式的解從而g為次剩余，矛盾。2．證明10是模17及模257（質數）的原根，并由此證明把化成循環(huán)小數時，循環(huán)節(jié)的長度分別是16及256．證明：，它的有且只有質因子2，而從而10不是模17的平方剩余，由上題知10是模17的原根。，由且僅有質因子2，而故同上理10也是模257的原根。由3§4的證明可知，，的循環(huán)節(jié)的長度，t，這是10關于模17，模257的指數，從而t=16，256證畢3．試利用指標表解同余式解：同余式等價于：查表知，故：由于，故上式由5個解，解之得：查表知：原同余式的5個解為：4．設模m（m．>2）的原根是存在的，試證對模m的任一原根來說，的指標總是．證明：模m的原根存在，故m=4，或設為模m的一個原根，則從而若m=4，，則模m有且只有一個原根3，，故的指標為若，為奇質數，則由知或但二者不能同時成立，否則，矛盾!若又由（*）知（modm），與的指數為矛盾。從而，從而（modm）故-1的指標為。若，為的原根，則為奇數類似于的討論，我們有，從而從而（modm）故-1的指標為。5、設，是模的兩個原根，試證：（mod）；（mod）。證明：由指標的定義知：（modm）兩邊對原根取指標：（mod）故（mod）由指標的定義知：（modm）兩邊對原根取指標：（mod）故（mod）。（證畢）第九章數論函數§1．可乘函數1．設是一個可乘函數，證明也是一個可乘函數．由此說明是可乘函數．證明：首先我們證明：設，若跑過的全部因子，跑過的全部因子，則跑過的全部因子，事實上，因為，故，且當，時，由于，得，反之任給，由于，設，，顯然．因此故為一個可乘函數．(此為65頁)若，它為可乘函數．，且．若，它為可乘函數，且．故為可乘函數．2．設是一個定義在一切正態(tài)數的函數，并且是一個可乘函數，證明是可乘函數．證明：反證，假設不是可乘函數，則存在一對正態(tài)數，使得，于是我們可以選擇這樣一對，使得最?。?，則，即，又，為可乘函數，故有矛盾！若，則對所有正態(tài)數對，有于是有：==因為，故此與為可乘函數矛盾！3．證明：證明：首先易證，若d為的正約數，那么a的完全剩余系中與的最大公約數是d的個數為。其次，若為的所有正約數。那么也是的所有正約數，于是最后，在的完全剩余系中住一數與的最大公約數必定是中某一個，而完全剩余系中與最大公約數為的數有個，所以4．試計祘和式解：此題較復雜，下分數步解之：?反演公式設和是兩個數論函數，且，則反之亦然事實上，反之，類似可得。參見習題5及6。②若是定義在閉區(qū)間上的函數，n正整數，記，則事實上，由①，只要證明，但這幾乎是明顯的，因為如果分數化成既約分數，就得到形如的分數，這里，b是n的一個約數．每一個這樣形式的分數都可得到一次也好一次．③記，則記則那么這樣由②知:由本節(jié)推論2．22．3，即有：5．是任一函數，并且：試證：證明：設，即，則由推論2．3知，其內部之和只有當c=a時為１，c<a時，為０，故上式右邊等于．設是任一函數，并且:證明:證明:其證法與上習題類似，我們有: 7．設是定義在實數上的兩個函數，并且對于任何不小于1的實數x來說:則反之，亦然．證明: （）記，則，并且遍取數目，則（）比較兩式即有上式右邊除第一頁其余諾項都等于0（推論2．3）右上式右邊等于類似可證明它的逆定理成立。初等數論試卷單項選擇題：（1分/題×20題=20分）１．設為實數，為的整數部分，則()Ａ．；Ｂ．；Ｃ．；Ｄ．．２．下列命題中不正確的是()Ａ．整數的公因數中最大的稱為最大公因數；Ｂ．整數的公倍數中最小的稱為最小公倍數Ｃ．整數與它的絕對值有相同的倍數Ｄ．整數與它的絕對值有相同的約數３．設二元一次不定方程（其中是整數，且不全為零）有一整數解，則此方程的一切解可表為()Ａ．Ｂ．Ｃ．Ｄ．４．下列各組數中不構成勾股數的是()Ａ．５，１２，１３；Ｂ．７，２４，２５；Ｃ．３，４，５；Ｄ．８，１６，１７５．下列推導中不正確的是()Ａ．Ｂ．Ｃ．Ｄ．６．模１０的一個簡化剩余系是()Ａ．Ｂ．Ｃ．Ｄ．７．的充分必要條件是()Ａ．Ｂ．Ｃ．Ｄ．８．設，同余式的所有解為()Ａ．或Ｂ．或Ｃ．或Ｄ．無解．9、設f(x)=其中為f(x)的一個解，則:()A．B．C．D．10．則同余式：（）A．有時大于p但不大于n;B．可超過pC．等于pD．等于n11．若2為模p的平方剩余，則p只能為下列質數中的:()A．3B．11C．13D．2312．若雅可比符號，則()A．B．;C．;D．．13．()A．4B．3C．2D．114．模12的所有可能的指數為;()A．1，2，4B．1，2，4，6，12C．1，2，3，4，6，12D．無法確定15．若模m的單根存在，下列數中，m可能等于:()A．2B．3C．4D．16．對于模5，下列式子成立的是:()A．B．C．D．17．下列函數中不是可乘函數的是:()A．茂陛鳥斯(mobius)函數w(a);B．歐拉函數；C．不超過x的質數的個數；D．除數函數；18．若對模的指數是，>0，>0，則對模的指數是()A．B．C．D．無法確定19．，均為可乘函數，則()A．為可乘函數；B．為可乘函數C．為可乘函數；D．為可乘函數20．設為茂陛烏斯函數，則有()不成立A．B．C．D．二．填空題：（每小題1分，共10分）21．3在45中的最高次n＝____________________；22．多元一次不定方程：，其中，，…，，N均為整數，，有整數解的充分必要條件是___________________；23．有理數，，，能表成純循環(huán)小數的充分必要條件是_______________________；24．設為一次同余式，的一個解，則它的所有解為_________________________；25．威爾生（wilson）定理：________________________________________；26．勒讓德符號=________________________________________；27．若，則是模的平方剩余的充分必要條件是_____________(歐拉判別條件)；28．在模的簡化剩余系中，原根的個數是_______________________；29．設，為模的一個原根，則模的一個原根為_____________；30．_________________________________。三．簡答題：（5分／題×4題＝20分）31．命題“任意奇數的平方減1是8的倍數”對嗎？說明理由。32．“若，通過模的簡化剩余系，則也通過模的簡化剩余系”這命題是否正確？正確請證明，不正確請舉反例。33．求模17的簡化剩余系中平方剩余與平方非剩余。34．設為的標準分解式，記為的正因數的和，為的正因數的個數，則＝？＝？為什么？四．計算題。（7分／題×4題＝28分）35．求不定方程6x+93y=75的一切整數解。36．解同余方程組37．解同余式≡11(mod125)38．求模13的所有原根。五、證明題：（7分/題×2題=14分）39、試證：，（x，y）=1y是偶數的整數解可寫成：這里，，并且一為奇數，一為偶數。40、設a為正整數，試證：其中表示展布在a的一切正因數上的和式。六、應用題：（8分）41、求30！中末尾0的個數。參考答案：一．單項選擇：ABCDD；DACCB；DCAAD；BCBAB。二．填空題：21．21；22．；23．；24．；25．！+1為素數；26．1；27．；28．；29．與中的單數；30．16三．簡答題：31．答：命題正確。而必為2的倍數。86頁32．正確．證明見教材。33．在摸的簡化剩余系中與同余的數是數的平方剩余，，，故1，2，4，8，9，13，15，16為摸17的平方剩余，而3，5，6，7，10，11，12，14為摸17的平方非剩余。34．證明：若為可乘函數，則．分別令，它們?yōu)榭沙撕瘮?，即得出。四．計算題35．解：因為，故原不定方程有解。又原方程即，而易見方程有解。所以原方程的一個解是所以，原方程的一切整數解是：（）t是整數36．解：因為模5，6，7兩兩互質，由孫子定理得所給同余方程組關于模5×6×7＝210有唯一解，分別解同余方程：，，，得，，因此所給同余方程組的解是：即：37．解：從同余方程，，，是得即是所給方程的一個解，于是所解為：解畢。38．解：為其質因數，故g為模13的原根的主要條件是：，用g=1，2，……12逐一驗證，得：2，6，7，11為模13的原根，因為，故模13原根只有4個，即為所求。五、證明題：39．證明：易驗證所給的解為原方程的解，因y為偶數，原方程可化為：但而x,z=1，所以（，）=1由書中引理，我們可假設=，=b顯然>b，(，b)=1，于是X=－b，z=+，y=2因子為奇數，所以，b一定是一為奇，一為偶，證畢40．證明：假定，，為的所有正約數，那末，，也是的所有正約數，于是=再因為在的完全剩余系中任一數的最大公約數必定是，，中某一個數，而完全剩余系中與的最大公約數為的數有，所以：=m證畢六．應用題：41．解：5在30！中的最高次冪=++=6+1+0=72在30！的最高次冪=++++=15+7+3+1+0=2610=2×5，故30！的末尾有7個零。2007年4月廣東省高等教教育育自學考試初等數論試卷單項選擇題。（本大題共15小題，每小題2分，共30分）1．-36，420，48三個數的公因數是（）A．±1，±3，±4，±5，±6，±12B.±1,±2,±3,±4,±6,±,12C.±2,±3,±4,±6D1,2,3,4,5,6,122.設a,b(整數集)，p是素數，且。則（）Aa,b中恰有一個是p的倍數B.a,b中沒有p的倍數C.a,b中必有一個是p的倍數D.a,b都是p的倍數3.設a,b是非零整數,d=(a,b),則下列成立的是()AB.C.D.4.則對于任意(正整數集)()A.B.C.D.5.對任意實數,必有()A.B.C.D.6.下列不定方程中,有整數解的是()A.B.C.D.7.設a,b則()A.(a,b)=(a,m)B.(a,b)=(b,m)C.(a,m)=(m,b)D.(a-b,m)=(a,m)8.下列集合中,是模15的簡化剩余系的是()A.B.C.D.9.下列同余式中成立的是()A.B.C.D.10.設同余式有解,則下述斷語中正確的是()A.該同余式有模m的m-1個解B.在模m的一組完全剩余系中,有(b,m)個數滿足該同余式C.在模m的一組完全剩余系中,有(a,m)個數滿足該同余式D.在模m的一組完全剩余系中,有(ab,m)個數滿足該同余式11.設素數p>2,a,b分別是模p的平方剩余和平方非剩余,則下列成的是()A.ab是模p的平方非剩余B.是模p的平方非剩余C是模p的平方剩余D.