初等數(shù)論試卷

1、一 填空題：1、(, 1573)=143 2、對(duì)于任意的正整數(shù)，有3、 4、22345680的標(biāo)準(zhǔn)分解式是.5、整數(shù)集合中含有個(gè)整數(shù)，且中任意兩個(gè)整數(shù)對(duì)于是不同余的，則整數(shù)集合是模的完全剩余系.6、設(shè)、是任意兩個(gè)正整數(shù)，則不大于而為的倍數(shù)的正整數(shù)個(gè)數(shù)為. 7、素?cái)?shù)寫成兩個(gè)平方數(shù)和的方法是唯一的. 8、不同剩余類中的任何兩個(gè)不同整數(shù)對(duì)模是不同余的.9、n元一次不定方程有解的充分必要條件是 10、初等數(shù)論按研究方法分為：初等數(shù)論、解析數(shù)論、代數(shù)數(shù)論、幾何數(shù)論.11、數(shù)集合是模的簡化剩余系的充要條件（1）中含有個(gè)整數(shù)；（2）任意兩個(gè)整數(shù)對(duì)模不同余；（3）中每個(gè)整數(shù)都與互素；12、 設(shè)n是正整數(shù)的最大

2、公約數(shù)為 13、若，則.14、被13除的余數(shù)是12. 15、模7的最小非負(fù)完全剩余系是0、1、2、3、4、5、6.二、判斷題：1、若為奇數(shù)，則8|。 （ ）2、設(shè)、是正整數(shù)與的個(gè)位數(shù)字不一定相同。 （ × ）3、任何大于1的整數(shù)都至少有一個(gè)素因數(shù). （ ）4、任何一個(gè)大于1的合數(shù)與，必然有一個(gè)不超過的素因數(shù). （ ）5、任意給出的五個(gè)整數(shù)中必有三個(gè)數(shù)之和能被整數(shù)3整除. （ ）6、最大公約數(shù)等于1是兩兩互素的必要而不充分條件. （ ）7、設(shè)是素?cái)?shù)，是整數(shù)，則或 （ ）8、如果是互素的，則一定兩兩互素 （ ×）9、設(shè)是素?cái)?shù)，若，則且 （ × ）10、（劉維爾定理）設(shè)

3、是素?cái)?shù)，則！ （ ）11、是正整數(shù)，則（ ）12、由于每個(gè)非零整數(shù)的約數(shù)個(gè)數(shù)是有限的，所以最大的公約數(shù)存在，且正整數(shù)。（ ）13、設(shè)是的一個(gè)約數(shù)，則（ ）14、不能被整除。（ × ）15、 (n2) 是整數(shù)（ × ）16、為正整數(shù)，若為素?cái)?shù)，則不一定是素?cái)?shù)（ × ）17、若并且!,則不是素?cái)?shù)（ × ）18、設(shè)是整系數(shù)多項(xiàng)式，并且都不能被整除，則有整數(shù)解（ × ）19、若（是任意兩個(gè)互質(zhì)的正整數(shù)），是則 （ × ）20、如果兩個(gè)整數(shù)互相整除，則這兩個(gè)數(shù)僅相差一個(gè)符號(hào)（ × ）三、計(jì)算題：1、設(shè)、是整數(shù)且，則解：由.再由得.由定

4、理4的推論1（設(shè)是素?cái)?shù)，若，則或）得或2、求(12345, 678).解：(12345, 678).= 3、求被50除的余數(shù).解：根據(jù)定理4，有即所求的余數(shù)是29.4、將寫成三個(gè)既約分?jǐn)?shù)之和，它們的分母分別是2，3和5.解：設(shè)即 上述方程等價(jià)于解得從而，故取得即5、求不定方程的解.解：方程有解由輾轉(zhuǎn)相除法，可以知道是方程的一個(gè)解所以，就是原方程的解； 由定理2知6、用輾轉(zhuǎn)相除法求整數(shù)、使得1387-162=(1387,162).解：作輾轉(zhuǎn)相除：，由此可得，=，=,又(1387,162).=，故7、將寫成三個(gè)既約分?jǐn)?shù)之和，它們的分母分別是3，5和7（第四章習(xí)題一1）解：設(shè)，即.因，故有解.分別解

5、得消去得、.對(duì)于任意的確定的和的值，都給出一種表示法。8、求最大的正整數(shù)，使得解：由定理（設(shè)是正整數(shù)，是的標(biāo)準(zhǔn)分解式，則）從而得知，的標(biāo)準(zhǔn)分解式中所含的的冪指數(shù)是（）所以所求得的最大正整數(shù)是.9、若四個(gè)數(shù),被同一個(gè)大于1的整數(shù)除所得的余數(shù)相同，且不等于零，求除數(shù)和余數(shù)各是多少？解：設(shè)除數(shù)為，余數(shù)為，則由，知由此得或10、將分解因數(shù).（ 第三章 第四節(jié) 定理 例7 ）解：若，則是或的素因數(shù)或者其中有和，因?yàn)?，所以分別是因數(shù)只能用來尋求在數(shù)列71、211、281中經(jīng)檢驗(yàn)顯然，的素因數(shù)也在、或數(shù)列71、211、281中簡單計(jì)算不能被、整除，也不能被數(shù)列71、211、281（）整除. 所以是素?cái)?shù)，故四

6、、證明題：1、求證：平方數(shù)的正因數(shù)個(gè)數(shù)是奇數(shù).證明：因?yàn)槊總€(gè)自然數(shù)的正因數(shù)個(gè)數(shù)是成對(duì)出現(xiàn)的，若是的因數(shù)，則也是的因數(shù)當(dāng)時(shí)，則.當(dāng)時(shí)，則即當(dāng)為平方數(shù)時(shí)，是的因數(shù)，與其配對(duì)的是自身.于是，當(dāng)且僅當(dāng)為平方數(shù)時(shí)，的正因數(shù)個(gè)數(shù)是奇數(shù).2、求證：若，則或2.證明：假設(shè)是的任意一個(gè)公約數(shù)，則有且 于是，又 從而，或.3、假設(shè)為正整數(shù)，則的充要條件為證明：因?yàn)?，所以，由費(fèi)馬定理有故，若，則用、分別代入上式，則當(dāng)、時(shí)當(dāng)時(shí)，5不整除.因此，若為正整數(shù)，則的充要條件為4、證明：對(duì)任意整數(shù)，被15整除.證明：對(duì)任意整數(shù)記作因?yàn)閷?duì)任意的整數(shù)有則與被除的余數(shù)相同即與被15除的余數(shù)是相同的記為.同理，與被15除的余數(shù)是相同

7、的記為.即，則考慮被15除的余數(shù)可見，與的余數(shù)相同記為.且與有相同的余數(shù)記為.當(dāng)時(shí)，即【對(duì)于的情形通過計(jì)算列出下表：】、14、13、12、11、10、9、85、定理（帶余除法）：若、是兩個(gè)整數(shù)，其中b0，則存在著兩個(gè)整數(shù)和，使得, 成立.而且及是唯一的.證明：存在性：若，則可以取若，考慮集合集合中有無限多個(gè)正整數(shù)，設(shè)其中最小的正整數(shù)為則必有，否則就有（，若，則矛盾，于是即這樣集合中又有正整數(shù)與的最小值矛盾）故，取使得, 成立. 存在性得證唯一性：假設(shè)存在兩對(duì)整數(shù)、及、都使得, 成立.即有，則，. 6、設(shè)是模的一個(gè)完全剩余系，以表示的小數(shù)部分，證明：若，則證明：當(dāng)通過模的完全剩余系時(shí)，通過模的完

8、全剩余系.因此，對(duì)任意的，一定與且只與某個(gè)整數(shù)同余即存在整數(shù)使得：從而，7、設(shè),，,是模的簡化剩余系，證明：.其中表示的小數(shù)部分。證明：由題可設(shè)：由通過模m的簡化剩余系知通過模的最小非負(fù)簡化剩余系，于是由定理可知：8、設(shè)、是正整數(shù)，則證明：（1）若且成立，則于是，即與矛盾，故命題結(jié)論成立.（2）若且，則于是，與矛盾，故命題結(jié)論成立.（3）若，記此時(shí).故由，在（1）中已經(jīng)證明這是不可能的，故命題結(jié)論成立.9、證明：存在無窮多個(gè)正整數(shù),使得都是合數(shù)（即分成兩項(xiàng)乘積即可）。證明：取,對(duì)任意的,有都是合數(shù)。10、證明：、，無平方因子且 ,證明：證明：設(shè),則有與,.由得，因?yàn)闊o平方因子，所以，即.11、

9、對(duì)任意的正整數(shù)、.證明下面的結(jié)論成立。（1）由且,可得出b|c.（2）由與, 且.可推出.證明：（1）.存在整數(shù)與使得. 即(2). 由,存在整數(shù)與使得.又由與,得,.因此，12、設(shè)是整數(shù)且,與,是模的兩個(gè)完全剩余系，證明：, 不是模的完全剩余系。證明：因?yàn)?，? 是模的完全剩余系，則其中的奇數(shù)與偶數(shù)各半.又因?yàn)?與,也是模m的兩個(gè)完全剩余系，從而有必須使，同為奇數(shù)或偶數(shù).即,這對(duì)于的模的完全剩余系是不可能的。13、設(shè)、是整數(shù)，并且,.求證：. 證明： 因?yàn)?，由定義知，從而， 故，. 由定理1（3）知存在整數(shù)與，使得，,從而.因此，.初等數(shù)論1：單選題已知361a是一個(gè)4位數(shù)（其中a 是個(gè)位

10、數(shù)），它能被5整除，也能被3整除，則a的值是（ ）。  A：0B：2C：5D：9參考答案：C2：單選題下面的（ ）是模4的一個(gè)簡化剩余系。  A：4,17B：1,15C：3,23D：13,6參考答案：B3：單選題小于20的正素?cái)?shù)的個(gè)數(shù)是（ ）。  A：11B：10C：9D：8參考答案：D4：單選題 下面的數(shù)是3的倍數(shù)的數(shù)是（ ）。  A：19B：119C：1119D：11119參考答案：C5：單選題-4除-39的余數(shù)是（ ）。  A：3B：2C：1D：0參考答案：C6：單選題一個(gè)正整數(shù)n的各位上

11、的數(shù)字是0或1，并且n能被2和3整除，則最小的n是（    ）。  A：1110B：1101C：1011D：1001參考答案：A7：單選題4.5+3.7等于（     ）。  A：3B：4C：7D：8參考答案：C8：單選題1.8+2.9等于（     ）。  A：0.4B：0.5C：0.6D：0.7參考答案：D9：單選題100與44的最小公倍數(shù)是（     ）。  A

12、：4400B：2200C：1100D：440參考答案：C10：單選題使3的n次方對(duì)模7同余于1的最小的正整數(shù)n等于（   ）。  A：6B：2C：3D：13參考答案：A11：單選題設(shè)a,b,c,d是模5的一個(gè)簡化剩余系，則a+b+c+d對(duì)模5同余于（    ）。  A：0B：1C：2D：3參考答案：A12：單選題下面的（    ）是不定方程3x + 7y = 20的一個(gè)整數(shù)解。  A：x=0,y=3B：x=2,y=1C：x=4,y=2D：x=2,y=2參考

13、答案：D13：單選題下面的（    ）是模4的一個(gè)完全剩余系。  A：9，17，-5，-1B：25，27，13，-1C：0，1，6，7D：1，-1，2，-2參考答案：C14：單選題下面的（   ）是模12的一個(gè)簡化剩余系。  A：0，1，5，11B：25，27，13，-1C：1，5，7，11D：1，-1，2，-2參考答案：C15：單選題若a，b均為偶數(shù)，則a + b為（   ）。  A：偶數(shù)B：奇數(shù)C：正整數(shù)D：負(fù)整數(shù)參考答案：A16：單選題1到20之間的素?cái)?shù)是（&

14、#160;  ）。  A：1，2，3，5，7，11，13，17，19B：2，3，5，7，11，13，17，19C：1，2，4，5，10，20D：2，3，5，7，12，13，15，17參考答案：B17：單選題如果a|b，b|c，則（ ）。  A：a=cB：a=-cC：a|cD：c|a參考答案：C18：單選題360與200的最大公約數(shù)是（ ）。  A：10B：20C：30D：40參考答案：D19：單選題如果 a|b，b|a ，則（ ）。  A：a=bB：a=-bC：a=b或a=-bD：a，b的關(guān)系無法確定參考

15、答案：C20：單選題如果5|n ，7|n，則35（ ）n 。  A：不整除B：等于C：不一定D：整除參考答案：D21：單選題整數(shù)6的正約數(shù)的個(gè)數(shù)是（ ）。  A：1B：2C：3D：4參考答案：D22：單選題設(shè)n，m為整數(shù)，如果3整除n，3整除m，則9（ ）mn。  A：整除B：不整除C：等于D：小于參考答案：A初等數(shù)論第二次作業(yè)填空題116除100的余數(shù)是 4 _。2如果今天是星期一，那么從今天起再過1010天后是星期 四 。33.2 = 0.8 ；2.84 = 3 。43.6 + 1.7 = 0.9 。5=_-1.5_。615的所有

16、正因數(shù)的和是 24 。71260的標(biāo)準(zhǔn)分解式是 。820！的標(biāo)準(zhǔn)分解式是。998!的末尾有_22_個(gè)零。10890的標(biāo)準(zhǔn)分解式是  2×5× 89 。11歐拉函數(shù)值 20 。127除3301的余數(shù)是 3 。13不定方程ax + by = c有解的充要條件是 。14設(shè)m為正整數(shù)，a，b為兩個(gè)整數(shù)，如果用m去除a與b所得的余數(shù)相同，那么就稱a，b對(duì)模m 同余 。15一次同余式有解的充分必要條件是 。16模7的最小非負(fù)完全剩余系是 0，1，2，3，4，5，6 。17（1516，600）= 4 。18不定方程ax + by = c(其中a，b，c是整數(shù))有整數(shù)解的充要條件

17、是 （a，b）c 。19710被11除的余數(shù)是 1 。2077的個(gè)位數(shù)是_ 3 _。初等數(shù)論第三次作業(yè)參考答案計(jì)算題1寫出400與600的標(biāo)準(zhǔn)分解式，并求出400與600的最大公因數(shù)。解 ，。2求128121被11除的余數(shù)。解 因?yàn)閖(11)=10，而128與11互素，所以128101(mod 11)，于是1281211287(mod 11)，所以128121被11除的余數(shù)為7。3求1050與858的最大公因數(shù)。解：因?yàn)?050 = 2´3´52´7，858 = 2´3´11´13，所以(1050，858) = 2´3 =

18、6。4求1001！中末尾0的個(gè)數(shù)。解：因?yàn)?0=2´5，所以1001！中末尾相當(dāng)于1001！的質(zhì)因數(shù)分解式中2´5的個(gè)數(shù)。由于2<5，所以1001！的質(zhì)因數(shù)分解式中2的個(gè)數(shù)比5的個(gè)數(shù)要多，因此，只要考察1001！中因子5的個(gè)數(shù)即可。因?yàn)椋?001÷5=2001，1001÷52=401，1001÷53=81，1000÷54=1375，又因?yàn)?00+40+8+1=249，所以答案為249。即1001！中末尾0的個(gè)數(shù)為249個(gè)。5求不定方程3x + 5y = 20的一切非負(fù)整數(shù)解。解：因?yàn)椋?，5）=1，所以不定方程有整數(shù)解。由觀察知

19、x0 = 0，y0 = 4是不定方程3x+5y=20的一個(gè)整數(shù)解，所以不定方程3x+5y=20的一切整數(shù)解是，其中t取一切整數(shù)。由可解得，所以，故不定方程的一切非負(fù)整數(shù)解為，。6求出不定方程7x + 2y = 1的一個(gè)整數(shù)解，并寫出其一切整數(shù)解的表達(dá)式。解：因?yàn)椋?,2）=1,1|1，所以不定方程有解。觀察知其一個(gè)整數(shù)解是。于是其一切整數(shù)解為，t取一切整數(shù)。7求不定方程15x + 10y + 6z = 61的一切整數(shù)解。解：不定方程的一切整數(shù)解為，其中u，v取一切整數(shù)。8計(jì)算歐拉函數(shù)值：j（100）。解：100 = 22´52，由公式有j（100）= = 40。9解同余式3x

20、86; 8 (mod 10)。解：因?yàn)椋?,10）=1,1|8，所以同余式有解，并且只有一個(gè)解。由得一個(gè)解，所以同余式的解為。10解同余式組：。解：因?yàn)?，3，5兩兩互質(zhì)，所以由孫子定理該同余式組有一個(gè)解。由孫子定理可得該同余式組的解為x º 1(mod 30)。11解同余式28x º 21 (mod 35)。解 因?yàn)椋?8，35） = 7，而7|21，所以同余式28x º 21(mod 35)有解，且有7個(gè)解。同余式28x º 21(mod 35)等價(jià)于4x º 3(mod 5)，解4x º 3(mod 5)得x º 2(

21、mod 5)，故同余式28x º 21(mod 35)的7個(gè)解為x º 2，7，12，17，22，27，32(mod 35)。12解同余式組：。解：由得，將其代入得，即，解得，所以，于是。所以同余式組的解為。初等數(shù)論第四次作業(yè)參考答案證明題1證明：若，則。證明：由，得，由整除的性質(zhì)得，即，所以。2證明：設(shè)m, n為整數(shù)，求證m+n, m-n與mn中一定有一個(gè)是3的倍數(shù)。證明：若m或n為3的倍數(shù)，則mn是3的倍數(shù)；若m是3的倍數(shù)加1，n是3的倍數(shù)加1，則m-n是3的倍數(shù)；若m是3的倍數(shù)加1，n是3的倍數(shù)加2，則m+n是3的倍數(shù)；若m是3的倍數(shù)加2，n是3的倍數(shù)加1，則m+n是

22、3的倍數(shù)；若m是3的倍數(shù)加2，n是3的倍數(shù)加2，則m-n是3的倍數(shù)，結(jié)論成立。3證明：若，則。證明：由，知存在整數(shù)p，q使得，所以，因?yàn)閜q為整數(shù)，所以由整除的定義知。4證明：若n為自然數(shù)，求證9n+1º8n+9(mod 64)。證明：因?yàn)?º1(mod 8)，所以9kº1(mod 8)，k=2，3，n-1，于是9n-1+92+9+1ºn(mod 8)，所以9(9n-1+92+9+1)º n(mod 8)，從而9´(9-1)´(9n-1+92+9+1)º 8n(mod 64)，即9(9n-1) º 8n(

23、mod 64)，所以9n+1º8n+9(mod 64)。5若p為奇質(zhì)數(shù)，證明2p | (22p-12)。證明：因?yàn)閜為質(zhì)數(shù)，所以j(p)=p-1，又p為奇質(zhì)數(shù)，所以(2，p)=1，于是由歐拉定理得2p-1º1(mod p)，兩邊平方得22p-2º1(mod p)，再由同余的性質(zhì)有2´22p-2º2(mod 2p)，即：22p-1º2(mod 2p)。所以2p|(22p-1-2)。6證明：整數(shù)a，b對(duì)模m同余的充分與必要條件是。證明：設(shè)，。若ab（mod m），則，因此，即mab。反之，若mab，則，因此，但，故，即ab（mod m）。

24、7設(shè)a是大于1的整數(shù)，證明是合數(shù)。證明：由于且是整數(shù)，所以，且均為整數(shù)，故當(dāng)a是大于1的整數(shù)時(shí)，是合數(shù)。8設(shè)m為整數(shù)，證明：。證明：因?yàn)槭莾蓚€(gè)連續(xù)整數(shù)的積，所以。又2|2，所以由整除的性質(zhì)知。9設(shè)p是質(zhì)數(shù)，a與b是任二整數(shù)。證明：。證明：因?yàn)閜是質(zhì)數(shù)，a與b是整數(shù)，所以，于是。又，所以。10證明：若，并且，則。證明：由得，所以，于是。初等數(shù)論練習(xí)題答案信陽職業(yè)技術(shù)學(xué)院2010年12月初等數(shù)論練習(xí)題一一、填空題1、d(2420)=12; (2420)=_880_2、設(shè)a,n是大于1的整數(shù)，若an-1是質(zhì)數(shù)，則a=_2.3、模9的絕對(duì)最小完全剩余系是_-4，-3，-2，-1,0,1,2,3,4.4

25、、同余方程9x+120(mod 37)的解是x11(mod 37)。5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t tÎZ。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為_j(m)_。7、18100被172除的余數(shù)是_256。8、 =-1。9、若p是素?cái)?shù)，則同余方程x p - 1 º1(mod p)的解數(shù)為 p-1 。二、計(jì)算題1、解同余方程：3x2+11x-20 º 0 (mod 105)。解：因105 = 3×5×7，同余方程3x2+11x-20 º 0 (mod 3)的解為x º 1 (mo

26、d 3)，同余方程3x2+11x-38 º 0 (mod 5)的解為x º 0，3 (mod 5)，同余方程3x2+11x-20 º 0 (mod 7)的解為x º 2，6 (mod 7)，故原同余方程有4解。作同余方程組：x º b1 (mod 3)，x º b2 (mod 5)，x º b3 (mod 7)，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孫子定理得原同余方程的解為x º 13，55，58，100 (mod 105)。2、判斷同余方程x242(mod 107)是否有解？ 故同余方程x24

27、2(mod 107)有解。3、求（127156+34）28除以111的最小非負(fù)余數(shù)。 解：易知127150（mod 111）。由502 58（mod 111）, 503 58×5014（mod 111），50914380（mod 111）知5028 （509）3×50803×50803×5068×5070（mod 111）從而5056 16（mod 111）。故（127156+34）28（16+34）28 502870（mod 111）三、證明題1、已知p是質(zhì)數(shù)，（a,p）=1，證明：（1）當(dāng)a為奇數(shù)時(shí)，ap-1+(p-1)a0 (mod p)

28、；（2）當(dāng)a為偶數(shù)時(shí)，ap-1-(p-1)a0 (mod p)。證明：由歐拉定理知ap-11 (mod p)及(p-1)a-1 (mod p)立得（1）和（2）成立。2、設(shè)a為正奇數(shù)，n為正整數(shù)，試證1(mod 2n+2)。 （1）證明 設(shè)a = 2m + 1，當(dāng)n = 1時(shí)，有a2 = (2m + 1)2 = 4m(m + 1) + 1 º 1 (mod 23)，即原式成立。設(shè)原式對(duì)于n = k成立，則有 º 1 (mod 2k + 2) Þ= 1 + q2k + 2，其中qÎZ，所以 = (1 + q2k + 2)2 = 1 + q ¢2k

29、 + 3 º 1 (mod 2k + 3)，其中q ¢是某個(gè)整數(shù)。這說明式(1)當(dāng)n = k + 1也成立。由歸納法知原式對(duì)所有正整數(shù)n成立。3、設(shè)p是一個(gè)素?cái)?shù)，且1kp-1。證明： º （-1 ）k(mod p)。 證明：設(shè)A= 得： k!·A =（p-1）(p-2)（p-k）（-1）(-2)（-k）(mod p) 又（k!，p）=1，故A = º （-1 ）k(mod p)4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p61(mod 84)。 說明：因?yàn)?4=4×3×7，所以，只需證明： p61(mod 4) p61(mod3)

30、 p61(mod 7) 同時(shí)成立即可。 證明：因?yàn)?4=4×3×7及p是不等于3和7的奇質(zhì)數(shù)，所以（p，4）=1，（p，3）=1，（p，7）=1。 由歐拉定理知：pj(4)p21(mod 4)，從而 p61(mod 4)。 同理可證：p61(mod3) p61(mod 7)。 故有p61(mod 84)。注：設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p61(mod 168)。（見趙繼源p86）初等數(shù)論練習(xí)題二一、填空題1、d(1000)=_16_；(1000)=_2340_.2、2010!的標(biāo)準(zhǔn)分解式中，質(zhì)數(shù)11的次數(shù)是199_.3、費(fèi)爾馬(Fermat)數(shù)是指Fn=+1,這種數(shù)中

31、最小的合數(shù)Fn中的n=5。4、同余方程13x5(mod 31)的解是x29(mod 31)_5、分母不大于m的既約真分?jǐn)?shù)的個(gè)數(shù)為j(2)+ j(3)+ j(m)。6、設(shè)7(80n-1),則最小的正整數(shù)n=_6_.7、使41x+15y=C無非負(fù)整數(shù)解的最大正整數(shù)C=_559_.8、=_1_.9、若p是質(zhì)數(shù)，n½p - 1，則同余方程x n º 1 (mod p) 的解數(shù)為n .二、計(jì)算題1、試求被19除所得的余數(shù)。 解：由20027 (mod 19) 2002211(mod 19) 200231 (mod 19) 又由2003200422004（22）10021 (mod 3

32、)可得：20023n+1(20023)n×20027(mod 19)2、解同余方程3x14 + 4x10 + 6x - 18 º 0 (mod 5)。 解：由Fermat定理，x5 º x (mod 5)，因此，原同余方程等價(jià)于2x2 + x - 3 º 0 (mod 5)將x º 0，±1，±2 (mod 5)分別代入上式進(jìn)行驗(yàn)證，可知這個(gè)同余方程解是x º 1 (mod 5)。3、已知a=5，m=21,求使a x º 1 (mod m)成立的最小自然數(shù)x。 解：因?yàn)椋?,21）=1，所以有歐拉定理知5

33、j(21)1(mod 21)。 又由于j(21)=12，所以x|12，而12的所有正因數(shù)為1,2,3,4,6,12。于是x應(yīng)為其中使 5 x º 1 (mod 12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進(jìn)行計(jì)算性證明) 證明：54m+46n+2000 º 252m+642n+2000 º（-1）2m+（-1）2n+2000 º 2002º 0(mod 13)。2、證明Wilson定理的逆定理：若n > 1，并且(n - 1)! º -1 (mod n)，則n是素

34、數(shù)。證明：假設(shè)n是合數(shù)，即n = n1n2，1 < n1 < n，由題設(shè)易知(n - 1)! º -1 (mod n1)，得0 º -1 (mod n1)，矛盾。故n是素?cái)?shù)。3、證明：設(shè)ps表示全部由1組成的s位十進(jìn)制數(shù)，若ps是素?cái)?shù)，則s也是一個(gè)素?cái)?shù)。 證明：假設(shè)s是合數(shù)，即s=ab，1<a，b<s。則 ，其中M1是正整數(shù)。由pa1也是正整數(shù)知ps是合數(shù)，這與題設(shè)矛盾。故s也是一個(gè)素?cái)?shù)。4、證明：若2p + 1是奇素?cái)?shù)，則 (p!)2 + (-1)p º 0 (mod 2p + 1)。證明：由威爾遜定理知 -1 º (2p)!

35、= p!(p + 1)L(2p) º (-1)p(p!)2(mod 2p + 1)，由此得(p!)2 + (-1)p º 0 (mod 2p + 1)。5、設(shè)p是大于5的質(zhì)數(shù)，證明：p41(mod 240)。（提示：可由歐拉定理證明） 證明：因?yàn)?40=23×3×5，所以只需證：p41(mod 8)，p41(mod 3)，p41(mod 5)即可。事實(shí)上，由j(8)=4，j(3)=2，j(5)=4以及歐拉定理立得結(jié)論。初等數(shù)論練習(xí)題三一、單項(xiàng)選擇題1、若n1，j(n)=n-1是n為質(zhì)數(shù)的（ C ）條件。 A.必要但非充分條件 B.充分但非必要條件 C.充

36、要條件 D.既非充分又非必要條件2、設(shè)n是正整數(shù)，以下各組a，b使為既約分?jǐn)?shù)的一組數(shù)是（D）。A.a=n+1,b=2n-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 D.a=3n+1,b=5n+23、使方程6x+5y=C無非負(fù)整數(shù)解的最大整數(shù)C是（A）。A.19B.24 C.25D.304、不是同余方程28x21(mod 35)的解為（D）。 A.x2(mod 35) B. x7(mod 35) C. x17(mod 35)D. x29(mod 35)5、設(shè)a是整數(shù)，(1)a0(mod9) (2)a2010(mod9)(3)a的十進(jìn)位表示的各位數(shù)字之和可被9整除(4)劃去a

37、的十進(jìn)位表示中所有的數(shù)字9，所得的新數(shù)被9整除以上各條件中，成為9|a的充要條件的共有（C）。A.1個(gè)B.2個(gè) C.3個(gè) D.4個(gè)二、填空題1、(2010)=_4896_；(2010)=528。2、數(shù)的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)7的指數(shù)是_3。3、每個(gè)數(shù)都有一個(gè)最小質(zhì)因數(shù)。所有不大于10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是97。4、同余方程24x6(mod34)的解是x113(mod34) x230(mod34)_。5、整數(shù)n>1，且(n-1)!+10(mod n),則n為素?cái)?shù)。6、3103被11除所得余數(shù)是_5_。7、=_-1_。三、計(jì)算題1、判定 () 2x3 - x2 + 3x - 1

38、º 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è)解。2、設(shè)n是正整數(shù)，求 的最大公約數(shù)。 解

39、：設(shè)知d½22n-1，設(shè)2k|n且2k+1n，即2k +1|n ，則由2k +1|，i = 3, 5, L, 2n - 1 得d = 2k + 1。3、已知a=18,m=77,求使axº 1 (mod m)成立的最小自然數(shù)x。 解：因?yàn)椋?8,77）=1，所以有歐拉定理知18j(77)1(mod 77)。 又由于j(77)=60，所以x|60，而60的所有正因數(shù)為1,2,3,4,5,6,10,12,15,20,30, 60。于是x應(yīng)為其中使18x º 1 (mod 77)成立的最小數(shù)，經(jīng)計(jì)算知：x=30。四、證明題 1、若質(zhì)數(shù)p5,且2p+1是質(zhì)數(shù)，證明：4p+1

40、必是合數(shù)。 證明：因?yàn)橘|(zhì)數(shù)p5,所以（3，p）=1，可設(shè)p=3k+1或p=3k+2。 當(dāng)p=3k+1時(shí)，2p+1=6k+3是合數(shù)，與題設(shè)矛盾，從而p=3k+2，此時(shí)2p+1是形如6k+5的質(zhì)數(shù)，而4p+1=12k+9=3(4k+3)是合數(shù)。注：也可設(shè)p=6k+r，r=0,1,2,3,4,5。再分類討論。2、設(shè)p、q是兩個(gè)大于3的質(zhì)數(shù)，證明：p2q2(mod 24)。 證明：因?yàn)?4=3×8，（3,8）=1，所以只需證明：p2q2(mod 3) p2q2(mod 8)同時(shí)成立。事實(shí)上， 由于（p，3）=1，（q，3）=1，所以p21(mod 3) ， q21(mod 3)， 于是p2q

41、2(mod 3)，由于p，q都是奇數(shù)，所以p21(mod 8) ， q21(mod 8)，于是p2q2(mod 8)。故p2q2(mod 24)。3、若x,yR+ ，（1）證明：xyxy； （2）試討論xy與xy的大小關(guān)系。注：我們知道，x + y x+ y，x+yx+y。此題把加法換成乘法又如何呢？ 證明：（1）設(shè)x=x+,0<1，y=y+,0<1。于是xy=xy+x+y+所以xy= xy+ x+y+ xy。（2）xy與xy之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。當(dāng)x=y=時(shí)，xy=xy=； 當(dāng)x=， y=時(shí)，xy=，xy=，此時(shí)xyxy； 當(dāng)x=-，y=-時(shí)，xy=，xy=，

42、此時(shí)xyxy。4、證明：存在一個(gè)有理數(shù)，其中d < 100,能使 = 對(duì)于k=1，2，.，99均成立。證明：由（73，100）=1以及裴蜀恒等式可知：存在整數(shù)c，d，使得 73d-100c=1從而-=，由k< 100可知：0-設(shè)=n，則n+1=,于是=n+1，故 = n =。初等數(shù)論練習(xí)題四一、單項(xiàng)選擇題 1、若Fn=是合數(shù)，則最小的n是( D )。A. 2 B. 3 C. 4 D. 52、記號(hào)baa表示baa,但ba+1a. 以下各式中錯(cuò)誤的一個(gè)是( B )。A. 21820! B. 10550! C. 119100! D. 1316200!3、對(duì)于任意整數(shù)n，最大公因數(shù)(2n+

43、1，6n-1)的所有可能值是( A )。A. 1 B. 4 C. 1或2 D. 1，2或44、設(shè)a是整數(shù)，下面同余式有可能成立的是( C )。A. a22 (mod 4) B. a25 (mod 7) C. a25 (mod 11) D. a26 (mod 13)5、如果ab(mod m)，c是任意整數(shù)，則下列錯(cuò)誤的是（A）Aacbc(mod mc)Bm|a-b C(a,m)=(b,m) Da=b+mt,tZ二、填空題 1、d(10010)=_32_，(10010)=_2880_。2、對(duì)于任意一個(gè)自然數(shù)n，為使自N起的n個(gè)相繼自然數(shù)都是合數(shù)，可取N=（n+1）！3、為使3n-1與5n+7的最大

44、公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=26k+9，kZ。4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來構(gòu)成模12的一個(gè)簡化系，則這組數(shù)是5,25,35,555、同余方程26x+133 (mod 74)的解是x124(mod74) x261(mod74)_。6、不定方程5x+9y=86的正整數(shù)解是_x=1,y=9或x=10,y=4。7、=_-1_。三、計(jì)算題1、設(shè)n的十進(jìn)制表示是，若792½n，求x，y，z。 解：因?yàn)?92 = 8×9×11，故792½n Û 8½n，9½n及11½n。我們有8½n 

45、9; 8½ Þ z = 6，以及9½n Û 9½1 + 3 + x + y + 4 + 5 + z = 19 + x + y Û 9½x + y + 1， (1)11½n Û 11½z - 5 + 4 - y + x - 3 + 1 = 3 - y + x Û 11½3 - y + x。 (2)由于0 £ x, y £ 9，所以由式(1)與式(2)分別得出x + y + 1 = 9或18，3 - y + x = 0或11。這樣得到四個(gè)方程組：其中a取值9或

46、18，b取值0或11。在0 £ x, y £ 9的條件下解這四個(gè)方程組，得到：x = 8，y = 0，z = 6。2、求3406的末二位數(shù)。解： （3，100）=1，3(100)1（mod 100），而(100)= (22·52)=40, 3401(mod 100) 3406=(340)10·36(32)2·32-19×9-17129(mod 100) 末二位數(shù)為29。3、求(214928+40)35被73除所得余數(shù)。 解：(214928+40)35(3228+40)35(32×32)14+4035 (102414+40)3

47、5 (214+40)35 (210×24+40)35 (25+40)35 7235 -172(mod 73)四、證明題1、設(shè)a1, a2, L, am是模m的完全剩余系，證明： （1）當(dāng)m為奇數(shù)時(shí)，a1+ a2+ L+ am 0（mod m）；（2）當(dāng)m為偶數(shù)時(shí)，a1+ a2+ L+ am （mod m）。 證明：因?yàn)?, 2, L, m與a1, a2, L, am都是模m的完全剩余系，所以 (mod m)。（1）當(dāng)m為奇數(shù)時(shí)，即得：，故(mod m)。（2）當(dāng)m為偶數(shù)時(shí)，由（m,m+1）=1即得：(mod m)。2、證明：若m2，a1, a2, L, aj(m)是模m的任一簡化剩余

48、系，則 證明：若a1, a2, L, aj(m)是模m的一個(gè)簡化剩余系，則m-a1, m-a2, L, m-aj(m) 也是模m的一個(gè)簡化剩余系，于是： 從而： 又由于m2，j(m)是偶數(shù)。故：3、設(shè)m > 0是偶數(shù)，a1, a2, L, am與b1, b2, L, bm都是模m的完全剩余系，證明：a1 + b1, a2 + b2, L, am + bm不是模m的完全剩余系。 證明：因?yàn)?, 2, L, m與a1, a2, L, am都是模m的完全剩余系，所以 (mod m)。 (1)同理 (mod m)。 (2)如果a1 + b1, a2 + b2, L, am + bm是模m的完全剩

49、余系，那么也有(mod m)。聯(lián)合上式與式(1)和式(2)，得到 0(mod m)，這是不可能的，所以a1 + b1, a2 + b2, L, am + bm不能是模m的完全剩余系。4、證明：（1）2730x13-x； （2）24x(x+2)(25x2-1)；（3）504x9-x3； （4）設(shè)質(zhì)數(shù)p3，證明：6pxp-x。證明：（1）因?yàn)?730=2×3×5×7×13，2,3,5，7,13兩兩互質(zhì)，所以：由x13-x=x (x12-1)0 (mod 2)知：2x13-x；13x13-x；由x13-x=x (x12-1)=x(x2-1)(x2+1)(x8+

50、x4+1)0 (mod 3)知：3x13-x；由x13-x=x (x12-1)=x(x4-1)(x8+x4+1)0 (mod 5)知：5x13-x；由x13-x=x (x12-1)=x(x6-1)(x6+1)0 (mod 7)知：7x13-x。故有2730x13-x。同理可證（2）、（3）、（4）。初等數(shù)論練習(xí)題五一、單項(xiàng)選擇題 1、設(shè)x、y分別通過模m、n的完全剩余系，若（ C ）通過模mn的完全剩余系。A. m、n都是質(zhì)數(shù)，則my + nx B. mn，則my + nx C. （m，n）=1，則my + nx D. （m，n）=1，則mx + ny2、1×3×5

51、5;×2003×2005×2007×2009×2011標(biāo)準(zhǔn)分解式中11的冪指數(shù)是( A )。A.100 B.101 C.99 D.1023、n為正整數(shù)，若2n-1為質(zhì)數(shù)，則n是( A )。A.質(zhì)數(shù) B.合數(shù) C.3 D.2k(k為正整數(shù))4、從100到500的自然數(shù)中，能被11整除的數(shù)的個(gè)數(shù)是( B )。A.33 B.34 C.35 D.365、模100的最小非負(fù)簡化剩余系中元素的個(gè)數(shù)是( C )。A.100 B.10 C.40 D.4二、填空題 1、同余方程ax+b0(modm)有解的充分必要條件是(a,m)b。2、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母

52、，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個(gè)奇質(zhì)數(shù)， 3、20122012被3除所得的余數(shù)為_1_。4、設(shè)n是大于2的整數(shù)，則(-1)(n)=_1_。5、單位圓上的有理點(diǎn)的坐標(biāo)是，其中a與b是不全為零的整數(shù)。6、若3258×a恰好是一個(gè)正整數(shù)的平方，則a的最小值為362。7、已知2011是一素?cái)?shù)，則=_-1_。三、計(jì)算題 1、求32008×72009×132010的個(gè)位數(shù)字。 解：32008×72009×#215;（-3）2009×32010 -32008+2009+2010 -36027 -3×（32）30

53、13 3(mod 10)。2、求滿足j(mn)=j(m)+j(n)的互質(zhì)的正整數(shù)m和n的值。 解：由（m，n）=1知，j(mn)=j(m)j(n)。于是有：j(m)+j(n)= j(m)j(n) 設(shè)j(m)=a， j(n)=b，即有：a+b=ab。 顯然ab，且ba，因此a=b。 于是由2a=a2 得a=2，即j(m)= j(n)=2。 故 m=3,n=4或m=4,n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100斤，問各買幾斤? 解：設(shè)買甲物x斤，乙物y斤，丙物z斤，則5x + 3y +z = 100，x + y + z = 100。消去z，得到 7x

54、 + 4y = 100。 (1)顯然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是 ， tÎZ因?yàn)閤0，y0，所以 0t £ 3。即t可以取值t1 = 1，t2 = 2，t3 = 3。相應(yīng)的x，y，z的值是(x, y, z) = (4, 18, 78)，(8, 11, 81)，(12, 4, 84)。四、證明題 1、已知2011是質(zhì)數(shù)，則有2011|。 證明：=102011-10 (mod 2011)。2、設(shè)p是4n+1型的質(zhì)數(shù)，證明若a是p的平方剩余，則p-a也是p的平方剩余。 證明：因?yàn)橘|(zhì)數(shù)p=4n+1，a是p的平方剩余，所以 =1 即：p-a也是p的平方剩余。3、已知p,q是兩