初等數(shù)論練習(xí)題答案

初等數(shù)論練習(xí)題答案WrittenbyPeterat2021inJanuary初 等 數(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、同余方程9x+12≡0(mod37)的解是x≡11(mod37)。518x-23y=100x=900+23t，y=700+18ttZ。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為_(m)_。7、18100被172除的余數(shù)是_256。8、65

=-1。 1039、若p是素?cái)?shù)，則同余方程xp11(modp)的解數(shù)為p-1 。二、計(jì)算題1、解同余方程：3x211x200(mod105)。解：因105=357，同余方程3x211x200(mod3)x1(mod3)，同余方程3x211x380(mod5)x0，3(mod5)，同余方程3x211x200(mod7)x2，6(mod7)，故原同余方程有4解。作同余方程組：xb1(mod3)，xb2(mod5)，xb3(mod7)，其中b1=1，b2=0，3，b3=2，6，由孫子定理得原同余方程的解為x13，55，58，100(mod105)。2、判斷同余方程x2≡42(mod107)是否有解？故同余方程x2≡42(mod107)有解。3、求（127156+34）28除以111的最小非負(fù)余數(shù)。解：易知1271≡50（mod111）。由502≡58（mod111）,503≡58×50≡14（mod111），509≡143≡80（mod111）知5028≡（509）3×50≡803×50≡803×50≡68×50≡70（mod111）從而5056≡16（mod111）。故（127156+34）28≡（16+34）28≡5028≡70（mod111）三、證明題1、已知p是質(zhì)數(shù)，（a,p）=1，證明：a為奇數(shù)時(shí)，ap-1+(p-1)a≡0(modp)；a為偶數(shù)時(shí)，ap-1-(p-1)a≡0(modp)。證明：由歐拉定理知ap-1≡1(modp)及(p-1)a≡-1(modp)立得（1）和（2）成立。2、設(shè)a為正奇數(shù)，n為正整數(shù)，試證a證明a=2m1，當(dāng)n1時(shí)，有

n2≡1(mod2n+2)。 （1）2=(2m1)2=1)11(mod23)，即原式成立。設(shè)原式對(duì)于n=k成立，則有

2k1(mod2k+

a2k=1q2k+2，其中qZ，所以 a1=(1+2)2=1q2k+31(mod2k+3)，q是某個(gè)整數(shù)。這說明式(1)當(dāng)n=k1n成立。3、設(shè)p是一個(gè)素?cái)?shù)，且1≤k≤p-1。證明：Ckp1

（-1）k(modp)。證明：設(shè)A=Ckp1

（p(p2) (pk)得：k!k!·A=（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(modp)又（k!，p）=1，故A=Ckp1

（-1）k(modp)4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6≡1(mod84)。說明：因?yàn)?4=4×3×7，所以，只需證明：p6≡1(mod4) p6≡1(mod3) p6≡1(mod7)84=4×3×7p37的奇質(zhì)數(shù)，所以（p，4）=1，（p，3）=1，（p，7）=1。由歐拉定理知：p(4)≡p2≡1(mod4)，從而p6≡1(mod4)。同理可證：p6≡1(mod3) p6≡1(mod7)。 故有p6≡1(mod84)。注：設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6≡1(mod168)。（見趙繼源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=22n+1,這種數(shù)中最小的合數(shù)Fn中的n=5。4、同余方程13x≡5(mod31)的解是x≡29(mod31)5、分母不大于m的既約真分?jǐn)?shù)的個(gè)數(shù)為(2)+(3)+…+(m)。6、設(shè)7∣(80n-1),則最小的正整數(shù)n=_6 .7、使41x+15y=C無非負(fù)整數(shù)解的最大正整數(shù)C= 559 .8、46=_1 .1019p是質(zhì)數(shù)，np1，則同余方程xn1(modn.二、計(jì)算題1、試求200220032004被19除所得的余數(shù)。解：由2002≡7(mod19) 20022≡11(mod19) 20023≡1(mod19)又由≡22004≡（22）1002≡1(mod3)可得：200220032004≡20023n+1≡(20023)n×2002≡7(mod19)24x106x180(mod5)。Fermatx(mod5)，因此，原同余方程等價(jià)于x30(mod5)x0，1，2(mod5)分別代入上式進(jìn)行驗(yàn)證，可知這個(gè)同余方程解是x1(mod5)。3a=5，m=21,ax1(modm)x。解：因?yàn)椋?,21）=1，所以有歐拉定理知5(21)≡1(mod21)又由于(21)=12，所以x|12，而12的所有正因數(shù)為1,2,3,4,6,12。于是x應(yīng)為其中使5x1(mod12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進(jìn)行計(jì)算性證明)證明：54m+46n+2000252m+642n+2000（-1）2m+（-1）2n+200020020(mod13)。2Wilson定理的逆定理：若n>1，并且(n1)!1(modn是素?cái)?shù)。n是合數(shù)，即n=nn，1<n<n1)!1(modn)，得12 1 101(modn)，矛盾。故n是素?cái)?shù)。s1ss3、證明：設(shè)數(shù)。s

p表示全部由1組成的s位十進(jìn)制數(shù)，若

是素?cái)?shù)，則s也是一個(gè)素證明：假設(shè)s是合數(shù)，即s=ab，1<a，b<s。則p110s110a)b110a1M，其中M＞1是正整數(shù)。s 9 9 9s由p＞1也是正整數(shù)知

是合數(shù)，這與題設(shè)矛盾。故s也是一個(gè)素?cái)?shù)。a s42p1(1)p0(mod2p1)。1(2p1)(2p)(1)p(p!)2(mod2p(1)p0(mod2p1)。5、設(shè)p是大于5的質(zhì)數(shù)，證明：p4≡1(mod240)。（提示：可由歐拉定理證明）證明：因?yàn)?40=23×3×5，所以只需證：p4≡1(mod8)，p4≡1(mod3)，p4≡1(mod5)即可。事實(shí)上，由(8)=4，(3)=2，(5)=4以及歐拉定理立得結(jié)論。初等數(shù)論練習(xí)題三一、單項(xiàng)選擇題1、若n＞1，(n)=n-1是n為質(zhì)數(shù)的（C ）條件。A.必要但非充分條件B.充分但非必要條件C.充要條件D.既非充分又非必要條件2、設(shè)n是正整數(shù)，以下各組a，b使b為既約分?jǐn)?shù)的一組數(shù)是（ D ）。a=n+1,b=2n-1 =2n-1,b=5n+2 =n+1,b=3n+1 =3n+1,b=5n+23、使方程6x+5y=C無非負(fù)整數(shù)解的最大整數(shù)C是（ A ）。4、不是同余方程28x≡21(mod35)的解為（ D ）?！?(mod35) B.x≡7(mod35) C.x≡17(mod35)5、設(shè)a是整數(shù)，(1)a≡0(mod9) (3)a的十進(jìn)位表示的各位數(shù)字之和可被9整除

D.x≡29(mod35)(4)劃去a的十進(jìn)位表示中所有的數(shù)字9，所得的新數(shù)被9整以上各條件中，成為9|a的充要條件的共有（C ）。個(gè)二、填空題

個(gè)個(gè) 個(gè)1、σ(2010)=_4896 ；(2010)=528。2、數(shù)C20100

的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)7的指數(shù)是_3。3、每個(gè)數(shù)都有一個(gè)最小質(zhì)因數(shù)。所有不大于10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是97。4、同余方程24x≡6(mod34)的解是x1≡13(mod34)x2≡30(mod34)_。5、整數(shù)n>1，且(n-1)!+1≡0(modn),則n為素?cái)?shù)。6、3103被11除所得余數(shù)是_5_。7、60=_-1_。 97三、計(jì)算題13x10(mod5)是否有三個(gè)解；(ⅱ)x62x54x230(mod5)是否有六個(gè)解？解：(ⅰ)2x33x10(mod5)3x24x30(mod5)x=(x33x24x3x5)+(6x212x15)，其中6x212x15的系數(shù)不都是5的倍數(shù)，故原方程沒有三個(gè)解。(ⅱ)因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解。2、設(shè)n是正整數(shù)，求C12n

,C32n

,,C2n2n

的最大公約數(shù)。解：設(shè)(C1

,

,C2n1d，由

C2n1

22n1d22n1，2n 2n 2n 2n 2n 2n設(shè)2k|n且2k+1|n，即2k+1||n，2n2n2k+1||C2n

及2k1|Ci 2n

Ci1i 2n

，i=3,5,,2n1得d=2k+1。3、已知a=18,m=77,求使ax1(modm)成立的最小自然數(shù)x。解：因?yàn)椋?8,77）=1，所以有歐拉定理知18(77)≡1(mod77)。又由于(77)=60，所以x|60，而60的所有正因數(shù)為1,2,3,4,5,6,10,12,15,20,30,60。于是x應(yīng)為其中使18x1(mod77)成立的最小數(shù)，經(jīng)計(jì)算知：x=30。四、證明題1、若質(zhì)數(shù)p≥5,且2p+1是質(zhì)數(shù)，證明：4p+1必是合數(shù)。證明：因?yàn)橘|(zhì)數(shù)p≥5,所以（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，2p+16k+54p+1=12k+9=3(4k+3)是合數(shù)。注p=6k+r，r=0,1,2,3,4,5。再分類討論。2、設(shè)p、q是兩個(gè)大于3的質(zhì)數(shù)，證明：p2≡q2(mod24)。證明：因?yàn)?4=3×8，（3,8）=1，所以只需證明：p2≡q2(mod3) p2≡q2(mod同時(shí)成立事實(shí)上，由于（p，3）=1，（q，3）=1，所以p2≡1(mod3)，q2≡1(mod3)，p2≡q2(mod3)p，qp2≡1(mod8)q2≡1(modp2≡q2(mod8)。故p2≡q2(mod24)。3、若x,y∈R+，（1）證明：[xy]≥[x][y]；（2）試討論{xy}與{x}{y}的大小關(guān)系。注：我們知道，[xxxy=[x][y]+β[x]+α[y]+αβ所以[xy]=[x][y]+[β[x]+α[y]+αβ]≥[x][y]。（2）{xy}與{x}{y}之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。1 1當(dāng)x=y=2時(shí)，{xy}={x}{y}=4；當(dāng)x=3，y=1時(shí)，{xy}=3，{x}{y}=1，此時(shí){xy}＞{x}{y}；2 2 4 4當(dāng)x=-1，y=-1時(shí)，{xy}=1，{x}{y}=1，此時(shí){xy}＜{x}{y}。2 3 6 3c4、證明：存在一個(gè)有理數(shù)

，其中d<100,能使[k

c]=[k73]d d 100對(duì)于k=1，2，….，99均成立。證明：由（73，100）=1c，d73d-100c=173從而100

kck-d

=k(73d100c)100d

k=100d

，由k<100可知：0＜73100

kc 1k-d＜d[k c[k 設(shè)d ，則d

＜n+1=

n1d,于是d73k＜kc1≤n1d=n+1，]c100 d d]cd故[k73]=n=[k 。d100初等數(shù)論練習(xí)題四一、單項(xiàng)選擇題1、若是合數(shù)，則最小的n是(D )A.2 B.3 C.4 D.52、記號(hào)baa表示ba｜a但ba+1|a.以下各式中錯(cuò)誤的一個(gè)是(B A.1820! B.1550! C.119100! D.116200!3、對(duì)于任意整數(shù)n，最大公因數(shù)(2n+1，6n-1)的所有可能值是( A )A.1 B.4 C.1或2 D.1，2或44、設(shè)a是整數(shù)，下面同余式有可能成立的是(C )。A.a2≡2(mod4) B.a2≡5(mod7) C.a2≡5(mod11) D.a2≡6(mod5、如果a≡b(modm)，c是任意整數(shù)，則下列錯(cuò)誤的是（A ）A．a(chǎn)c≡bc(modmc) B．m|a-b C．(a,m)=(b,m) D．a(chǎn)=b+mt,t∈Z二、填空題1、d(10010)=_32 ，(10010)=_2880 。2、對(duì)于任意一個(gè)自然數(shù)n，為使自N起的n個(gè)相繼自然數(shù)都是合數(shù)，可取N=（n+1）！3、為使3n-1與5n+7的最大公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=26k+9，k∈Z。4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來構(gòu)成模12的一個(gè)簡(jiǎn)化系，則這組數(shù)是{5,25,35,55}5、同余方程26x+1≡33(mod74)的解是x1≡24(mod74)x2≡61(mod74)_。6、不定方程5x+9y=86的正整數(shù)解是_x=1,y=9或x=10,y=4。7、54=_-1_。 89三、計(jì)算題1、設(shè)n的十進(jìn)制表示是13xy45z，若792n，求x，y，z。792=8911792n8n，9n及。我們有8n845z z=6，以及9n913xy45z=19xy9xy1，(1)11n11z54yx31=3yx113y。(2)0y9，(1)與式(2)分別得出xy1=9或3yx=011xy1ayxba918，b0110xy9的條件下解這四個(gè)方程組，得到：x=8，y=0，z=6。2、求3406的末二位數(shù)。（3，100）=1，∴3φ(100)≡1（mod100），φ(100)=φ(22·52)=40,∴340≡1(mod100)∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod100)∴末二位數(shù)為29。3、求(214928+40)35被73除所得余數(shù)。解：(214928+40)35≡(3228+40)35≡[(32×32)14+40]35≡(102414+40)35≡(214+40)35≡(210×24+40)35≡(25+40)35≡7235≡-1≡72(mod73)四、證明題1、設(shè)a,a,,a

是模m的完全剩余系，證明：1 2 m（1）當(dāng)m為奇數(shù)時(shí)，a+a++a≡0（modm）；1 2 m（2）當(dāng)m為偶數(shù)時(shí)，a+a++a≡m（modm）。1 2 m 2證明：因?yàn)閧1,2,,a,a,,a}都是模m的完全剩余系，所以1 2 mmai

im(m(mod2i1 im(m2當(dāng)m由m1m(m22m)。

maii1

m(m1)2

0(mod當(dāng)m（m,m+1）=1m

m(m

m(modm)。ii1

2 2（m）2m＞2，a1a2a(m)m的任一簡(jiǎn)化剩余系，則

aii1

0(modm).a1,a2,,a(m)mm-a1,m-a2m-a(m)m的一個(gè)簡(jiǎn)化剩余系，于是：

（m）

(m)

ma)(modm).從而：

（m）

m(m)(modm).a(2ai i ia(2ai1 i1 i1m＞2，(m)

（m）ai

m（m）0(modm).2i13、設(shè)m>0是偶數(shù)，{a1,a2,,am}與{b1,b2,,bm}都是模m的完全剩余系，證明：{a1b1,a2b2,,ambm}m的完全剩余系。證明：因?yàn)閧1,2,,a,a,,a}都是模m的完全剩余系，所以1 2 mmai

im(m2 2

(mod。 (1)同理 mbii1

i1 i1m(mod。 (2)2如果{a

b,

b,,

b}是模m的完全剩余系，那么也有1 1 2

2 m(aii1

mb)i

m(modm)。2聯(lián)合上式與式(1)和式(2)，得到 0mm

m(modm)，2 2 2這是不可能的，所以{a1b1,a2b2,,ambm}m的完全剩余系。4、證明：1）2730∣x13-； （2）24x(x+2)(25x-1；（3）504∣x9-3； 4）p＞3，證明：6p∣xp-x。證明：（1）因?yàn)?730=2×3×5×7×13，2,3,5，7,13兩兩互質(zhì)，所以：由x13-x=x(x12-1)≡0(mod2)知：2∣x13-x；13∣x13-x；x13-x=x(12-1)x(2-1(x2+1)(8+4+1≡0(mod3知：3∣x13-；x13-x=x(12-1)x(4-1(x8+4+1≡0(mod55∣x13-；x13-x=x(12-1)x(6-1(x6+1≡0(mod7知：7∣x13-。2730∣x13-。同理可證（2）、（3）、（4）。初等數(shù)論練習(xí)題五一、單項(xiàng)選擇題1x、ym、n的完全剩余系，若（C）mn的完全剩余系。m、n都是質(zhì)數(shù)，則mynx B.m≠n，則mynxC.（m，n）=1，則mynx D.（m，n）=1，則mxny2、1×3×5×…×2003×2005×2007×2009×2011標(biāo)準(zhǔn)分解式中11的冪指數(shù)是(A)。3、n為正整數(shù)，若2n-1為質(zhì)數(shù)，則n是(A)A.質(zhì)數(shù) B.合數(shù) (k為正整數(shù))4、從100到500的自然數(shù)中，能被11整除的數(shù)的個(gè)數(shù)是(B)。5、模100的最小非負(fù)簡(jiǎn)化剩余系中元素的個(gè)數(shù)是(C)。二、填空題1a+≡0(mod有解的充分必要條件是(a,)∣b。2、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個(gè)奇質(zhì)數(shù)，(q)p

p1q1 2011(1)22 2011q3、被3除所得的余數(shù)為_1 。4、設(shè)n是大于2的整數(shù)，則(-1)(n)= 1 。5、單位圓上的有理點(diǎn)的坐標(biāo)是(

2ab

,a2b2)或(a2b2, 2ab

)，其中a與b是不全為零的整數(shù)。

a2b2

a2b2

a2b2

a2b26、若3258×a恰好是一個(gè)正整數(shù)的平方，則a的最小值為362。7、已知2011是一素?cái)?shù)，則 72 =_-1_。 三、計(jì)算題1、求32008×72009×132010的個(gè)位數(shù)字。解：32008×72009×132010≡32008×（-3）2009×32010≡-32008+2009+2010≡-36027≡-3×（32）3013≡3(mod10)。2、求滿足(mn)=(m)+(n)的互質(zhì)的正整數(shù)m和n的值。解：由（m，n）=1知，(mn)=(m)(n)。于是有：(m)+(n)=(m)(n))=n)=b，即有：a+b=aa∣bb∣aa=b。2a=a2a=2，即(mn)=2m=3,n=4m=4,n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100斤，問各買幾斤?解：設(shè)買甲物x斤，乙物y斤，丙物z斤，則5x3y

1z=100，3xyz=100。消去得到 7x4y=100。 (1)顯然x=0，y=25是方程(1)的解，因此，方程(1)的一般解是x4t ，y257t因?yàn)閤＞0，y＞0，所以 0＜t3。即t可以取值t1

=1，t2

=2，t3

=3。相應(yīng)的x，y，z的值是(x,y,z)=(4,18,78)，(8,11,81)，(12,4,84)。四、證明題120112011|9。2010個(gè)9=12011-≡0(mod2011。2010個(gè)2p4n+1app-app=4n+1，ap的平方剩余，所以= =pa a 1= = p p pp

p2

a=1p=1

即：p-a也是p的平方剩余。3、已知p,q是兩個(gè)不同的質(zhì)數(shù)，且ap-1≡1(modq),aq-1≡1(modp),證明：apq≡a(modpq)。證明：由p,q是兩個(gè)不同的質(zhì)數(shù)知（p，q）=1。于是由Fermat定理ap≡a(modp),又由題設(shè)aq-1≡1(modp)得到：apq≡(aq)p≡ap(aq-1)p≡ap≡a(modp)。同理可證：apq≡a(modq)。故：apq≡a(modpq)。4、證明：若m,n都是正整數(shù)，則(mn)=（m,n）([m,n])。證明：易知mn與[m,n]有完全相同的質(zhì)因數(shù)，設(shè)它們?yōu)閜i(1≤i≤k)，則又mn=（m,n）[m,n]故n)[m

1p1

1) p2

1)(m,n)([m,n])。pkm=m1m2，m1與m由相同的質(zhì)因數(shù)，證明：(m)=m2(m1)。初等數(shù)論練習(xí)題六一、填空題1、為了驗(yàn)明2011是質(zhì)數(shù)，只需逐個(gè)驗(yàn)算質(zhì)數(shù)2，3，5，…p都不能整除2011，此時(shí)質(zhì)數(shù)p至少是_43 。2、最大公因數(shù)(4n+3,5n+2)的可能值是_1,7 。33∣40!3α+|40340，則α=_18_。43n+18的一個(gè)完全系的最小那些數(shù)是{1,4,7,10,13,16,19，22}。5、不定方程x2+y2=z2,2|x,(x,y)=1,x,y,z>0的整數(shù)解是且僅是x2==ab0，(a1，a與b有不同的奇偶性。6、21x≡9(mod43)的解是x≡25(mod43)。 7、73=-1 199二、計(jì)算題1173，57。105解：設(shè)17

xyz

，即35x21y15z=17，因(35,21)=7，(7,15)=1，117，故有解。

105 3 5 7分別解5x3y=t 7t15z=17得 x=t=2tt=1115v，z=4消去t得 x=1115vy=2230vz4。u=0，v=-1x=4，y=-8，z=3。即：

4

83105 3 5 72、若3是質(zhì)數(shù)p的平方剩余，問p是什么形式的質(zhì)數(shù)？3

p1

p， (1) p p

3p

p4)p>3，pp

1(mod3)且 3

p4)∴3p

pp1只能下列情況p4) p1 ∴pp12。3、判斷不定方程x2+23y=17是否有解？解：只要判斷x2≡17(mod23)是否有解即可?！?7≡1(mod4)

172362331721 23 17 17 1717 17 3 3∴x2≡17(mod23)無解，即原方程無解。三、論證題1、試證對(duì)任何實(shí)數(shù)x,恒有〔x〕+〔x+1〕=〔2x〕2證明：設(shè)x=[x]+α,0≤α<1

1時(shí),[x+1]=[x],[2x]=2[x] ∴等式成立2 2②當(dāng)11時(shí),[x+1]=[x]+1,[2x]=2[x]+1 ∴等式成立2 2故對(duì)任何實(shí)數(shù)x,恒有[x]+[x+1]=[2x]。22、證明：（1）當(dāng)n為奇數(shù)時(shí)，3∣（2n+1）；（2）當(dāng)n為偶數(shù)時(shí)，3|（2n+1）。證明：由2n+1≡（-1）n+1（mod3）立得結(jié)論。3、證明：1）3∣n（n為正整數(shù)）時(shí)，7∣（2n-1）；（2）無論n為任何正整數(shù)，7|（2n+1）。證明：1）n=3m，2n-1=m-1≡0mod7），即：7∣（2-1）；（2）23m≡1（mod7）得23m

+1≡2（mod7），23m+1

+1≡3（mod7），23m+2+1≡5（mod7）。n為任何正整數(shù)，7（2n+1）。4、設(shè)m＞0，n＞0，且m為奇數(shù)，證明：（2m-1，2n+1）=1。證明一：由m為奇數(shù)可知：2n+1︱2mn+1，又有2m-1︱2mn-1，x,y使得：（2n+1）x=2mn+1,(2m-1)y=2mn-1。從而（2n+1）x-(2m-1)y=2。這表明：（2m-1，2n+1）︱2由于2n+1，2m-1均為奇數(shù)可知：（2m-1，2n+1）=1。證明二：設(shè)（2m-1，2n+1）=d，則存在s,t∈Z,使得2m=sd+1,2n=td-1。由此得到：2mn=(sd+1)

n,

=(td-1)m于是2mn=pd+1=qd–。所以：（q=2。從而d=12md=1即（2m-1，2n+1）=1。n a b (a,注：我們已證過：記M=2n1，對(duì)于正整數(shù)a，b，有(M,Mn a b (a,b顯然當(dāng)a≠b，a,b為質(zhì)數(shù)時(shí)，(Ma,M)=1。b初等數(shù)論練習(xí)題七一、單項(xiàng)選擇題1、設(shè)a和b是正整數(shù)，則([a,b],[a,b])=（ A ）a bB．a(chǎn) C．b D．(a,b)2、176至545的正整數(shù)中，13的倍數(shù)的個(gè)數(shù)是（B ）A．27 B．28 C．29 D．303、200!中末尾相繼的0的個(gè)數(shù)是（ A ）A．49 B．50 C．51 D．524、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡(jiǎn)化剩余系的是（B ）的倍數(shù) B．3的倍數(shù)C．4的倍數(shù) D．5的倍5、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（A ）A．4

B．n1 C．2n

D．n114n3二、填空題

2n1 5n2

11、314162被163除的余數(shù)_1 。（歐拉定理）2、同余方程3x≡5(mod13)的解是x≡5(mod13)。3、(365)=1。18474、［-π］＝-4。5、為使n-1與3n的最大公因數(shù)達(dá)到最大的可能值，則整數(shù)n應(yīng)滿足條件n=3k+1,k∈Z。6、如果一個(gè)正整數(shù)具有21個(gè)正因數(shù)，問這個(gè)正整數(shù)最小是26×32=576。7、同余方程x3+x2-x-1≡0(mod3)的解是x≡1,2(mod3)。三、計(jì)算題1x2y3z=41的所有正整數(shù)解。x2y=tt3z=41得 x=t2uy=uuZ，t=413vz=vvZ，消去t得x=413v2uy=uz=v 。(x,y,z)=(413v2u,u,v)，u>0，v>0，413v2u>0。2、有一隊(duì)士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3人。已知這隊(duì)士兵不超過170人，問這隊(duì)士兵有幾人？解：設(shè)士兵有x人，由題意得x1(mod3)，x2(mod5)，x3(mod11)。在孫子定理中，取m1

=3，m2

=5，m3

=11，m=3511=165，M=55，M1 2

=33，M3

=15，M=1，M1 2

=2，M3

=3，則 x1551（-2）332315358(mod165)，因此所求的整數(shù)x=52+165t，tZ。由于這隊(duì)士兵不超過170人，所以這隊(duì)士兵有58人。3、判斷同余方程x

?解：286=2×143，433是質(zhì)數(shù)，(143，443)=1奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號(hào)計(jì)算的勒讓德符號(hào)1431 7114311433

11

8 2

7 3

∴原方程有解。四、證明題

7

1、設(shè)(a,m)=1，d0

是使ad1(mod(ⅰ)d(m)；0i，j，0jd0

1，i，有aiaj(mod（1）證明：(ⅰ)由Euler定理，d0

，因此，由帶余數(shù)除法，有(m)=qd0

r，qZ，q>0，0r<d。0因此，由上式及d0

的定義，利用歐拉定理得到1a(m)aqd0

ar(modm)，即整數(shù)r滿足ar1(modr<d。0d的定義可知必是r=0，即d0 0(ⅱ)若式(1)不成立，則存在i，j，0jd0

1，iaiaj(mod不妨設(shè)i>1，所以j0(mod<ij<d。0這與d0

的定義矛盾，所以式(1)必成立。2、證明：設(shè)a，b，c，m是正整數(shù)，m>1，(b,m)=1，并且ba1(modm)，bc1(modd1(modaxcy=，顯然xy<0。若x>0，y<0，由式(1)知：1bax=bdbcy=bd(bcybd(mod若x<0，y>0，由式(1)知：1bcy=bdbax=bd(ba)xbd(modm)。3、設(shè)p是素?cái)?shù)，pbn1，nN，則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：(ⅰ)pbd1對(duì)于n的某個(gè)因數(shù)d<n成立；(ⅱ)p1(modn)。若2>2，則(ⅱ)中的modn可以改為mod。證明：dp1)，由bn1，bp11(modp)，及第2bd1(modd<d=np1，即p1(mod若2|n，p>2，則p1(mod2)。由此及結(jié)論(ⅱ)，并利用同余的基本性質(zhì)，p1(mod2n)。初等數(shù)論練習(xí)題八一、單項(xiàng)選擇題1n>1，則n為素?cái)?shù)是(n1)!1(mod（C）。A.必要但非充分條件 B.充分但非必要條C.充要條件 D.既非充分又非必要條2、小于545的正整數(shù)中，15的倍數(shù)的個(gè)數(shù)是（C）3、500!的標(biāo)準(zhǔn)分解式中7的冪指數(shù)是（D ）410的簡(jiǎn)化剩余系的是（D）,9,－3,－1 ,－1,7,9 ,7,11,13 D.－1,1,－3,35n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（A）1

n1

2n1

n15n2 2n1 5n2 1二、填空題1、σ（120）=360。2、7355的個(gè)位數(shù)字是3。3、同余方程3x≡5(mod14)的解是x≡11(mod14)。4、（17）=1。2325、［- ］＝-2。26、如果一個(gè)正整數(shù)具有6個(gè)正因數(shù)，問這個(gè)正整數(shù)最小是12。7、同余方程x3+x2-x-1≡0(mod5)的解是x≡±1(mod5)。三、計(jì)算題1、已知563是素?cái)?shù)，判定方程x2429(mod563)是否有解。563解：把429Jacobi符號(hào)563 429563563134 2 6767-）. .563

2 2 429

429

429

429429

8 429

67(1)671429429276767..429

2.2

67

67

67

2 227

27

13(1)2711312711，..27 2 2 13 13 故方程x2429(mod563)有解。2、求出模23的所有的二次剩余和二次非剩余。解：模23的所有的二次剩余為x1,2,3,4,6,8,9,12,13,16,18(mod23)；模23的所有的二次非剩余為x5,7,10,11,14,15,17,19,20,21,22(mod23)。3、試求出所有正整數(shù)n，使得1n＋2n＋3n＋4n能被5整除。解：若n為奇數(shù)，則1n＋2n＋3n＋4n1n＋2n＋（-2）n＋（-1）n0(mod5)；若n=2m，m∈Z，則1n＋2n＋3n＋4n12m＋22m＋（-2）2m＋（-1）2m2+2×22m=2+2×4m=2+2×(-1)m(mod5)；當(dāng)m為奇數(shù)時(shí)，1n＋2n＋3n＋4n0(mod5)；當(dāng)m為偶數(shù)時(shí)，1n＋2n＋3n＋4n4(mod5)。4|n時(shí)，5∣1＋2n＋3n＋n。四、證明題1、p>2，則的質(zhì)因數(shù)一定是2pk+1形。q2p-12p-1q≠2，（2，q）=12p≡1（mod。h2x≡1（mod這與ph=p,p|q-1q-1為偶數(shù)，2|q-1，2p|q-1，q-1=2pk, q=2pk+1。2、設(shè)（m,n）=1,證明：m(n)+n(m)≡1(modmn)。證明：因?yàn)椋╩,n）=1，所以由歐拉定理知：n(m)≡1(modm)，m(n)≡1(modn)于是m(n)+n(m)≡1(modm)m(n)+n(m)≡1(modn)。又因?yàn)椋╩,n）=1，所以m(n)+n(m)≡1(modmn)。注：此題也可這樣表述：若兩個(gè)正整數(shù)a,b互質(zhì)，則存在正整數(shù)m,n，使得am+bn≡1(mod)3、設(shè)（a,b）=1,a+b≠0,p(abapbp)或p。ab說明：事實(shí)上，設(shè)(ab,apbp)d，只需證明：d|p即可。aba+b≡0(moda+b)，即a≡-b(moda+b)，知ak≡(-b)k(moda+b)。其 中 0 ≤ k ≤ 。 又apbpap1ap2babp2bp1bp1bp1bp1pbp1(modab)。ab令(ab,apbp)d，則d|pbp-1。又（a,b）=1，d|（a+b）知（d,b）=1。ab（否則設(shè)（d,b）=d′＞1d′︱a和d′︱b，這與（a,b）=1矛盾。）于是（d。故d|即 d=1或。初等數(shù)論練習(xí)題九一、單項(xiàng)選擇題1、以下Legendre符號(hào)等于-1的30被-1是(D )A.3

B.4

C.5

D.611

11

11

11 2、100至500的正整數(shù)中，能被17整除的個(gè)數(shù)是(B )A.23 B.24 C.25 D.263、設(shè)3|500!，但31500！，則α=( C )A.245 D.2484、以下數(shù)組中，成為模7的完全剩余系的是(C )A.－14，－4，0，5，15，18，19C.－4，－2，8，13，32，35，135

B.7，10，14，19，25，32，40D.－3，3，－4，4，－5，5，05、設(shè)n是正整數(shù)，則以下各式中一定成立的是(B )A.(n+1，3n＋1)=1C.（2n，n＋1）=1二、填空題1、25736被50除的余數(shù)是1。

B.（2n－1，2n＋1）=1D.（2n＋1，n－1）=12、同余方程3x≡5(mod16)的解是x≡7(mod16)。3、不定方程9x－12y=15的通解是x=-1+4t，y=-2+3t，tZ。4、323

=1。 415、實(shí)數(shù)的小數(shù)部分記為{x}，則{－5}＝。46、為使3n與4n＋1的最大公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=3k+2，k∈Z。7、如果一個(gè)正整數(shù)具有35個(gè)正因數(shù)，問這個(gè)正整數(shù)最小是26×34=5184。三、計(jì)算題1、解不定方程9x＋24y－5z=1000。解：解因（9，24）=3，（3，-5）=1知原方程有解。原方程化為9x24y=3t， 即 3x8y=(1)3t-5z=1000 3t-5z=1000， (2)解(2

t5uz200

，uZ，再解3x8y=5u

xu8v，u，vZ。yuxu8v故 yu，。z2002A={x,x,,x}是模mx,)=1，求

1 2 m{}axb{}i 。mi1解：當(dāng)x通過模m的完全剩余系時(shí)，ax b也通過模m的完全剩余系，因此對(duì)于任意的i（1 i i

b一定與且只與某個(gè)整數(shù)j（1 j 同余，即存在整數(shù)k，使得axi

b=kmj。從而：3n2，

i。即在數(shù)列1,2,,n中，與n互素的整數(shù)之和。1in(i,n)1解：設(shè)在1,2,,n中與n互素的(n)個(gè)數(shù)是a,a,,a，(a,n)=1，1a

n1，1i1 2 (n) i i則 (na,=1，1nan1，1ii i因此，集合{a,a,,anana,,na

}是相同的，于是1 2 (n) 1 2 a a a =(na)(na) (na)，1 2 (n) 1 2 (n)2(a a1 2

a

)=因此：a a1 2

a(n)

=1n(n)。24m1，(a1，xxx

是模m(m{ax}。1 2

imi1其中{x}表示x的小數(shù)部分。解：設(shè)ax=mq r，0 r<由x通過模m的簡(jiǎn)化剩余系知：ax也通過模m的簡(jiǎn)化i i i i i i剩余系，從而r通過模m的最小非負(fù)簡(jiǎn)化剩余系，于是：i(m{ax}(mqr}(m)r

1(m)r

1m(m)1(m)。i im i

im m

2m 2i1 i1 i1四、證明題

i11、a是有理數(shù)，bbaccab∣c。(提示：利用帶余數(shù)除法解決。)證明：設(shè)c=bq+r，0≤r＜b，q∈Z，則ca=(ba)q+ra。ca，ba∈Z，ra∈Z，ra=0a≠0r=0b∣c。2、設(shè)p是素?cái)?shù)，證明：(ⅰ)對(duì)于一切整數(shù)11(x1)(x2)(xp1)(mod(ⅱ)(p1)! 1(modp)。證明：(ⅰ)110(modx1，2，，p1(mod11(x1)(x2)(xp1)(mod(ⅱ)在(ⅰ)中令x=。n a32n，p

-1,則 1。p pp∣an-1an1(modp)。又（p，a）=1an+1a(modp)。n1

2 a2n，所以(a

)2a(modp

a(modp)

1。p4p=4m+1（1。pmm(1ppp

)

p12 1)2m1。p15、設(shè)p是奇質(zhì)數(shù)，p1(mod4(p1)!)22

1(modp)解由Wilson定理有：注：（1）設(shè) p 為質(zhì)數(shù)且 p＝，則同余方程x2p)的解是x12 (2m)(modp。pp＝4m+1aa2≡1(modp)。初等數(shù)論練習(xí)題十一、單項(xiàng)選擇題p1、設(shè)p是大于1的整數(shù)，如果所有不大于 的質(zhì)數(shù)都不能整除p，則p一定是p（A）。A.素?cái)?shù) B.合數(shù) C.奇數(shù) D.偶數(shù)2、兩個(gè)質(zhì)數(shù)p，q，滿足p+q=99，則pq的值是（B ）B.9413

q pC.9413

D.9413194 99 1113、2010！的標(biāo)準(zhǔn)分解式中，7的最高冪