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

初等數(shù)論練習(xí)題一一、填空題1、（2420）=27；（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}。49x+12≡（mod37）x11(mod3。5、不定方程18x—23y=100的通解是x=900+23t，y=700+18t 。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為_(m)_.7、18100被172除的余數(shù)是_256。8、65

=—1。 103p-1.9、若p是素?cái)?shù),則同余方程xp11(modp）的解數(shù)為p-1.二、計(jì)算題13x211x200（mod105105=357，3x211x200（mod3）1(mod3，3x211x380（mod5）x0，3(mod3x211x200（mod7）2，6(mod4作同余方程組：xb1

（mod3),xb2

(mod5)，xb3

(mod7)，其中b1

=1,b2

=0，3,b3

=2,6，x13,55，58，100(mod105。2、判斷同余方程x2≡42（mod107）是否有解？(42)（237

2

3）（7）107 107 107 107 107（2）1，（

3

311071

107 2

7

71107

107 2

12（22（2（（42107

）1故同余方程x2≡42(mod107）有解。3、求(127156+34）28除以111的最小非負(fù)余數(shù).PAGEPAGE26/25解：易知1271≡50（mod111)。502≡5（mod111503≡58×50≡1（mod111509≡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）三、證明題1p（a,）=，證明：（）a為奇數(shù)時(shí),p-1+(p-）≡0(modp；(2）當(dāng)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ù)，試證aa2m1n1時(shí)，有

n2≡1(mod2n+2)?！?（1）2a2=（2m1)2=4m（m1)11(mod23)，即原式成立。nka2

1(mod2k+2） a=1q2k+2,qZ,a1=（1q2k+2）2=1q2k+31（mod2k+3)，q是某個(gè)整數(shù)。這說明式（1）n=k1也成立n成立。3p1≤k≤p—1Ckp1

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

（p(p2) (pk) 得:k!k·A（p—1）(p-2）…(p—k)≡（-1)(-2）…（—k（mod)又（k!,p)=1，故A=Ck （—1）k（modp14p37的奇質(zhì)數(shù)，證明：p6≡1（mod84=4×3×7，所以,只需證明:p6≡1（mod4) p6≡1（mod3) p6≡1（mod7） 84=4×3×7p37的奇質(zhì)數(shù),所以（p，4)=，(，3）=1（p,7）=1.(4）≡p2≡1(mod4，從而p≡1（mod4）.同理可證p6≡1（mod） p6≡1（mod7。故有p6≡1(mod8。p37的奇質(zhì)數(shù)，證明：p61（mod168（p86）初等數(shù)論練習(xí)題二一、填空題1、(1000）=_16_;（除數(shù)函數(shù)：因數(shù)的個(gè)數(shù)）σ(1000)=_2340_.（和函數(shù)：所有因數(shù)的和）2、2010！的規(guī)范分解式中,質(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（modp）n。二、計(jì)算題1、試求20022003200419除所得的余數(shù).2002≡7(mod19）20022≡11（mod19)20023≡1（mod20032004≡22004≡(22）1002≡1(mod3）可得：200220032004≡20023n+1≡（20023)n×2002≡7(mod19）23144106180(mod。Fermat定理，x5x（mod5）,因此,2x2x30(mod5）012（mod5)分別代入上式進(jìn)行驗(yàn)證,1(mod。3a=5,m=21,1(modm）x.解：因?yàn)椋?，21）=1,所以有歐拉定理知5（21）≡1（mod21）.又由于(21）=12，所以x|12，而12的所有正因數(shù)為1，2，3，4，6，12.x5x1(mod12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題113｜（54m+6+200（13進(jìn)行計(jì)算性證明）證明：54m+46n+2000252m+642n+2000(—1)2m+（—1）2n+200020020（mod13)。2Wilson:n>1并且（n1）1(modnn是素?cái)?shù).nnn1n2，1n1，由題設(shè)易知（n1)!1（modn1，得01(modn1),矛盾。故n是素?cái)?shù)。3ps1s位十進(jìn)制數(shù),pss證明:ss=ab，1<a，b〈s。則p110s110a)b110a1MM＞1s 9 9 9spa＞1pss也是一個(gè)素?cái)?shù)。42p1是奇素?cái)?shù)，則（p21）p0（mod2p1。證明：由威爾遜定理知1（2p！p（p1）(p）1pp!)2(modp1，由此得p）21p0（mod2p1。5p5的質(zhì)數(shù),證明：p4≡1(mod24（提示:可由歐拉定理證明)240=23×3×5，所以只需證:p4≡1(mod8）,p4≡1(mod3)，p4≡1（mod5）即可。事實(shí)上,由（8)=4，（3)=2,(5)=4初等數(shù)論練習(xí)題三一、單項(xiàng)選擇題1、若是n為質(zhì)數(shù)的（ C）條件.A.必要但非充分條件B.充分但非必要條件C.充要條件D.既非充分又非必要條件2na,b使b為既約分?jǐn)?shù)的一組數(shù)是（D。aA。a=n+1，b=2n—1 B.a=2n-1,b=5n+2C。a=n+1,b=3n+1 D。3、使方程6x+5y=C無非負(fù)整數(shù)解的最大整數(shù)C是（A。A.19 。24 C.25 D.30428x≡21（mod35)的解為（D。A。x≡2(mod35） B.x≡7（mod35)C。x≡17（mod35)D。x≡29（mod35）5a（1）a≡0(mod）(）≡2010（mod9)（3）a的十進(jìn)位表示的各位數(shù)字之和可被9整除（4）劃去a的十進(jìn)位表示中所有的數(shù)字9,所得的新數(shù)被9整以上各條件中,成為9|a的充要條件的共有( C）.A。1。2C。3D.4二、填空題1、σ（2010）=_4896 ；(2010)=528。2、數(shù)C20100

的規(guī)范分解式中，質(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ì)算題1、判定(?。?2x3x23x10（mod5)是否有三個(gè)解；（ⅱ)x62x54x230(mod5)是否有六個(gè)解？ⅰ232310（mod532430（mod55x33243（235)（621215r)=6212155的倍數(shù)，故原方程沒有三個(gè)解。(ⅱ） 5的同余方程,故原方程不可能有六個(gè)解.2n是正整數(shù),求C12n

,C32n

C2n12n解：設(shè)(C1

,

,C2n1d，由

C2n1

22n1知d22n1，2n 2n 2n 2n 2n 2n設(shè)2k｜n且2k+1|n,即2k+1｜｜n，2n2k+1｜｜C12n1。

及2k1|Ci2n

i

i12n1

,i=3，5，，2n1得d=2k+3a=18，m=77,ax1（modm)x。解：因?yàn)?18,77）=1，77)又由于6030，60。x18x1(mod77)成立的最小數(shù),經(jīng)計(jì)算知:x=30四、證明題1、若質(zhì)數(shù)p≥5，且2p+1是質(zhì)數(shù)，證明：4p+1必是合數(shù).p≥5，所以（3，p）=1，p=3k+1p=3k+1，2p+1=6k+3p=3k+2,2p+16k+54p+1=12k+9=3（4k+3）注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（mod8)同時(shí)成立。p,3=（q3=1p≡（mod3）2（mod3，都是奇數(shù)，所以p2≡1(mod8)q2≡1(mod8),p2≡q2(mod8)。故p2≡q2（mod24).3、若x，y∈R+,（1）[x］≥[x］[y；(2）試討論｛xy}與｛x}｛y｝［]≥［］+[]，x+}≤{｝}。此題把加法換成乘法又如何呢？（1）x=[x］+，0≤〈1，y=［y]+，0≤<1。于是xy=[x][y]+β［x]+α［y]+αβ所以[x]=[x［y］+［［x］+[y］+α]≥［x］[y]。（2)｛xy}與｛x｛y｝之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。1 1

時(shí)，{xy}=｛x}{y}= ；2 43 1 3 1當(dāng)x= ，y= 時(shí)，{xy}= ，{x｝{y｝=，此時(shí){xy}＞｛x}{y}；2 2 4 41，y=-1，y=-1時(shí),{xy｝=1｛x｝{y｝=123634c

,d100，能使

，此時(shí){xy｝＜{x}{y｝.c]=[k73]d d 100對(duì)于k=1，2，….,99均成立。證明：由（73，100）=1以及裴蜀恒等式可知：存在整數(shù)c，d，使得73d-100c=1從而73k-kc

=k(73d100c)

k= ,k〈100可知：100 d 100d 100d0＜73k-kc＜1設(shè)[k

100 d dc] kc n1d =n,則d＜n+1=d d，于是73k＜kc1≤n1d=n+1，100 d d故[k73100

c]=n=[kd 。]初等數(shù)論練習(xí)題四一、單項(xiàng)選擇題1、若Fn=是合數(shù)，則最小的n是( D )。A。2 B.3 C.4 D。52、記號(hào)ba‖a表示ba｜a,但ba+1a。以下各式中錯(cuò)誤的一個(gè)是（B )。A.218‖20! B.105‖50！ C。D。1316‖200！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） 。a2≡5(mod7) C。a2≡5(modD.a2≡6(mod5、如果≡b（modm，c是任意整數(shù),則下列錯(cuò)誤的是（）A．a(chǎn)c≡bc（modmc）B．m｜a-bC．(a,m）=(b，m) D．a(chǎn)=b+mt，t∈Z二、填空題1、d(10010)=_32 ，（10010)=_2880 。2nNnN=(n+！33n—15n+7的最大公因數(shù)達(dá)到最大可能值,nn=26k+9，k∈Z。4512的一個(gè)簡(jiǎn)化系,則這組數(shù)是35，55}526x+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。解：因?yàn)?92=8911，故792n 8n，9n及8n845zz=6，以及9n913xy45z=19xy9xy1, （1)11n11z54yx31=3yx113yx。（2)由于0x，y9，所以由式(1)與式(2)分別得出xy1=918，3yx=0。xy1a y x ba918，b00x，y9得到：x=8，y=0，z=6.2、求3406的末二位數(shù)。解：∵（3，100)=1，∴3φ(100)≡1（mod100）,而φ（100)=φ(22·52)=40，∴340≡1(mod100∴3406（34010·36（32)·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è)a1，a2，，am是模m的完全剩余系，證明：(1）當(dāng)m為奇數(shù)時(shí)，a1+a2++am≡0（modm)；（2）m

aam（modm。1 2 m 2證明:因?yàn)椋?,2，,m｝與｛a1,a2，，am}都是模m的完全剩余系，所以mai

im(m)(mod。2i1 i1m(m2當(dāng)m為奇數(shù)時(shí)，由m1m(m22

，故maii1

m(m1)2

0（mod。(）m為偶數(shù)時(shí)，由（m,m+1)=1m

m(m1)

m(modm)。ii1

2 2（m）2、證明：若m＞2,a1，a2，，am)是模m的任一簡(jiǎn)化剩余系，則 a0(modm).（ ii1a1,m)m

m)也（（m）

（(m)是模m 的一個(gè)簡(jiǎn)化剩余系，于是：

a (ma)(mod

從而：i ii1 i1（m）

（m）2 aii1

(m)(modm

(m）

aii1

0(modm).23、設(shè)m>0是偶數(shù)，{a1，a2，，am}與{b1,b2，，bm｝都是模m的完全剩余系，證明:｛a1b1，a2b2，，ambm}不是模m的完全剩余系。證明：因?yàn)椋?，2，，m｝與｛a1，a2，，am}都是模m的完全剩余系，所以mai

im(mm2 2

(modm).(1）同理mbii1

i1 i1m（mod。 (）2如果｛a1b1，a2b2，，ambm}是模m的完全剩余系，那么也有m(aii1

b)i

m（modm）.2聯(lián)合上式與式（1）和式（2）,0mmm（mod，2 2 2這是不可能的,所以{a1b1,a2b2,，ambm}不能是模m的完全剩余系。4:（1）2730∣x13-x（2)2xx+2)(25x-1；(）504∣x9x3（4p＞3，證明x12730=2×3×5×7×13,2，3，5，7,13由x13—x=x（x12—1)≡0（mod2)知：2∣x13—x；13∣x13—x;x13—x=x（x12-1)=x(x2—1)（x2+1)(x8+x4+1）≡0（mod3)知:3∣x13-x;x13-x=x（x12-1）=x(x4-1）(x8+x4+1）≡0（mod5)知：5∣x13-x；x13x=xx12—1）x(6—x6+）≡0(mod7知：7∣x13x.2730∣x13—x。(、(（4。初等數(shù)論練習(xí)題五一、單項(xiàng)選擇題1、設(shè)x、y分別通過模m、n的完全剩余系，若(C）通過模mn的完全剩余系.A.m、n都是質(zhì)數(shù)，則mynxB。m≠n，則mynxC。(m,n）=1，則mynx D.（m，n）=1，則mxny2、1×3×5×…×2003×2005×2007×2009×2011規(guī)范分解式中11的冪指數(shù)是(A )A。100 。101 C.99 D。1023、n為正整數(shù),若2n—1為質(zhì)數(shù)，則n是（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ù)簡(jiǎn)化剩余系中元素的個(gè)數(shù)是（C )。A.100 。10 C。40 D。4二、填空題1、同余方程ax+b≡0（modm)有解的充分必要條件是（a，m）∣b。2、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個(gè)奇質(zhì)數(shù),

p

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

2ab

,a2b2)或(a2b2, 2ab

)ab是不全為零的整數(shù)。

a2b2

a2b2

a2b2

a2b26、若3258×a恰好是一個(gè)正整數(shù)的平方，則a的最小值為362.20117、已知2011是一素?cái)?shù)，則 72 2011 三、計(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知，(m）（m（n。于是有：（）(n）（)n）設(shè)(m)=a，(n）=b，即有：a+b=aba∣b，b∣a，a=b。于是由2a=a2得a=2，即(m）=(n)=2.故m=3，n=4或m=4，n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100斤，問各買幾斤？解：設(shè)買甲物x斤,乙物y斤，丙物z斤，則5x3y1z=100，3xyz=100。消去z，得到7x4y=100. （1)顯然x=0,y=25是方程（1）的解，因此，方程（1）的一般解是x4tx＞0，y＞00＜t3

y25

，tZ即t可以取值t1=1，t2=2，t3=3。相應(yīng)的x，y,z的值是，，z）=(4，18，78，(8,1，81（12,4，84。四、證明題120112011|92010個(gè):9=1201—1≡0（mod201。2010個(gè)2p4n+1型的質(zhì)數(shù),app—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(modaq-1≡1(mod得到：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),則1p1

1)(11)p p2 k[m,

1p1

1)(11)p p2 k又mn=（m，n）[m，n］故n)[m

1p1

1p2

1)(m,n)([m,n])。pk類似的題：設(shè)m=m1m2，m1與m由相同的質(zhì)因數(shù)，證明：(m）=m2（m1).初等數(shù)論練習(xí)題六一、填空題120112，3，5,…p,p至少是_43 .2、最大公因數(shù)（4n+3，5n+2)的可能值是_1，7 。33∣403α+|403‖40α=_18。43n+18的一個(gè)完全系的最小那些數(shù)是1，22。5、不定方程x2+y2=z2，2｜x，(x，y）=1，x，y,z〉0的整數(shù)解是且僅是x=2ab，y=a2b2，z=a2b2，其中a>b〉0，(a,b）=1，a與b有不同的奇偶性。6、21x≡9(mod4）的解是x≡25(mod4。7、73 =-1。199 二、計(jì)算題1173，57。105解：設(shè)17

xyz

352115z=17因35,21）=7（715)=1117，105 3 5 7故有解。分別解5x3y=t7t15z=17得x=t3u，y=2t5u，uZ，t=1115v，z=47v,vZ,消去t得x=1115v3u，y=2230v5u,z=47v，u，vZ.令u=0,v=—1得到：x=4,y=-8,z=3。即:174

83105 3 5 72、若3是質(zhì)數(shù)p的平方剩余，問p是什么形式的質(zhì)數(shù)？p解：∵由二次互反律3p

p1

p， (1)

3p

p4)p>3,pp1（mod3)且

31p1(mod4) p∴3p

只能下列情況pp(mod

p1(mod3)p4)pp。3x2+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①當(dāng)0≤α<1時(shí)，［x+1］=[x]，［2x]=2[x]∴等式成立2 2②當(dāng)1≤α〈1時(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(）3∣n（n為正整數(shù)）時(shí)，7∣（2n—1；（2）無論n為任何正整數(shù)，7|（2n+1）.（1)n=3m,2n—1=m—1≡0(mod，即：7∣（2n—）;（2）由于23m≡1(mod7)得23m+1≡2（mod7）,23m+1+1≡3(mod7)，23m+2+1≡5（mod7)。故無論n為任何正整數(shù)，7|(2n+1).4m＞0，n＞0，m2m—1，2n+1）=1。證明一:m為奇數(shù)可知：2n+1︱2mn+1，2m—1︱x，y（2n1）x=2m1（21）y=2m—1。從而（2n+1)x—（2m—1）y=2。這表明：（2m-1，2n+1）︱22n1，2—1（2—1，2+）=。證明二：設(shè)（2m—1，2n+1）=d，則存在s，t∈Z，使得2m=sd+1，2n=td-1。由此得到：2mn=(sd+1）n， 2mn=(td-1）m

=p+1=q–，∈Z（—）d=2.從而2m。即(2m—1，2n+1）=1。注：Mn=2n1a，b，有（Ma,Mb)=M（a，b).a≠b,a，b(Ma，Mb)=1。初等數(shù)論練習(xí)題七一、單項(xiàng)選擇題A1、設(shè)a和b是正整數(shù)，則([a,b],[a,b])=( ）Aa bA．1B．a(chǎn)C．bD．(a，b）2、176至545的正整數(shù)中，13的倍數(shù)的個(gè)數(shù)是（A．27 B．28C．29 D．303、200！中末尾相繼的0的個(gè)數(shù)是（ A）A．49 B．50C．51 D．52B4、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡(jiǎn)化剩余系的是( )BA．2的倍數(shù)B．3的倍數(shù)C．4的倍數(shù)D．5的倍數(shù)5、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（A）A．4B．n1C．2n1D．n114n3 2n1 5n2 1二、填空題1、314162被163除的余數(shù)_1 （歐拉定理)2、同余方程3x≡5(mod13）的解是x≡6（mod13)。3、(365)=1。18474［-π］＝—4。5n—13nnn=3k+1,k∈Z。26×32=576。26×32=576。x≡1,2(mod。7、同余方程x3+x2—xx≡1,2(mod。三、計(jì)算題1x2y3z=41x2ytt3z=41得x=t2uy=t=413vz=vvZ,消去t得x=413v2uy=uz=vu,vZ。由此得原方程的全部正整數(shù)解為（x，y,z)=（413v2u,u，v),u〉0，v>0,413v2u>0。2、有一隊(duì)士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3人。已知這隊(duì)士兵不超過170人,問這隊(duì)士兵有幾人?x1（mod3）,2(mod，3（mod1m1=3,m2=5，m3=3511=M1=55，M2=33，M3=15,M1=1，M2=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)286 2 143

44321

443 14 27 443 243443

2 2

143 143 1431431431 7114311433

11

8 2 2

7 3

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

7

1、設(shè)（a，m）=1，d0是使ad1（modm)成立的最小正整數(shù)，則（)d0；（ⅱ）i，j,0i，jd01ijai

（modm)。（1）證明：(ⅰ) 由Euler定理，d0（m)，因此，由帶余數(shù)除法，有（m）=qd0r，qZ，q〉0，0r<d0。因此，由上式及d0的定義,利用歐拉定理得到1a(m)aqd0

ar(modm)，ra1(mod，0r〈d0d0r=d0。ⅱ） 若式（1i，j,0i,j1,ijaij（mod。i>j。因?yàn)椋╝,m）=1aij0(modm),0ij〈d0。這與d0的定義矛盾，所以式（1）必成立。2、證明：設(shè)a，b，c，m是正整數(shù)，m〉1，(b，m）=1，并且ba1（mod，bc（mod（1）d（a，bd1（mod。證明:由裴蜀恒等式知，存在整數(shù)x，y，使得axcy=d,顯然xy〈0.〉0，<0由式（1）知：1baxbdcybd（bc）yd（mod。x〈0，y〉0,由式(1）知：1bcybdbaxbd（ba）xbd（mod。3、設(shè)p是素?cái)?shù),pbn1,nN，則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：（ⅰ)pbd1對(duì)于n的某個(gè)因數(shù)d<n成立；(ⅱ)p1(modn）.若2|n，p>2，則(ⅱ)中的modn可以改為mod2n。證明：dn，p1bn1，b1（modp2題有bd1（modp）.若d<n，則結(jié)論(?。┑米C。若d=n，則np1，即p1(modn）,這就是結(jié)論(ⅱ)。2|n，p〉2p1（mod2。由此及結(jié)論ⅱ，并利用同余的基本性質(zhì)，得到p1（mod2n)。初等數(shù)論練習(xí)題八一、單項(xiàng)選擇題1、設(shè)n>1，則n為素?cái)?shù)是(n1)！1(modn)的（C）.A。必要但非充分條件 B.充分但非必要條C。充要條件 D。既非充分又非必要條件2、小于545的正整數(shù)中，15的倍數(shù)的個(gè)數(shù)是（C)A.34 B.35 C.36 D。37D3、500！的規(guī)范分解式中7的冪指數(shù)是（ ）DA.79 B。80 C.81 D。82D4、以下各組數(shù)中，成為模10的簡(jiǎn)化剩余系的是（ ）DA.1，9，－3,－1 B。1，－1,7,9C。5,7，11，13 D.－1，1,－3，3A5、設(shè)n是正整數(shù),下列選項(xiàng)為既約分?jǐn)?shù)的是（ ）A15n2

n12n1

2n15n2

D。n13n1二、填空題1、σ（120）=360。3。2、73553。x≡11（mod14)。3、同余方程3xx≡11（mod14)。4（17）=—1。2325［- ］＝-2.212.6、如果一個(gè)正整數(shù)具有6個(gè)正因數(shù),問這個(gè)正整數(shù)最小是12.x≡±1（mod5)。7、同余方程x3+x2—x-1x≡±1（mod5)。三、計(jì)算題1、已知563是素?cái)?shù)，判定方程x2429(mod563）是否有解。 解：把429 563 429563563134..

2

67

67 - ）563

2 2 429

429

429

429429

8 429

67(1)671429429276767..429

2.2

67

67

67

2 227

27 13

27127

1

2.

1，27

13

13故方程x2429（mod563）有解.22323x1，2，3，4，6，8，9，12，13，16，18(mod23x5，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)2m22×22m=2+×4=2+2×—1(mod；m為奇數(shù)時(shí)，1n＋2n＋3n＋4n0（modm為偶數(shù)時(shí)，1n＋2n＋3n＋4n4(mod。故當(dāng)4|n時(shí),5∣1n＋2n＋3n＋4n.四、證明題1、證明：若質(zhì)數(shù)p〉2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。q2p-12p—1q≠2（2，q）=q|2p-12p≡1(mod設(shè)h是使得2x≡1（mod成立最小正整數(shù)，若〈則有這與p為數(shù)矛盾.從而h=p，于是 p|q-1。又∵q—1為偶數(shù)，2｜q—1，2p|q-1,q—1=2pk， q=2pk+1k∈Z.2、設(shè)m，n)=，證明：(+m≡1(modm。證明：因?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，使得+ndb。3、設(shè)（a，b）=1，a+b≠0，p為一個(gè)奇質(zhì)數(shù)，證明:(ab,apbp)1或p。ab說明：事實(shí)上，設(shè)(ab,apbp)d，只需證明:d｜p即可。aba+b0(moda+b）,a—b（moda+b）,a（-b）（moda+b。其 中 0 ≤ k ≤ p — 1 。 又apbpab

ap1ap2babp2bp1bp1bp1bp1pbp1(modab)。令(abapbpdd|pbp-1。又（a，b）=1，d｜（a+b)知（d，b）=1。ab（否則設(shè)(d，b)=d′＞1，d′︱ad′︱b，這與（a，b）=1）于是（d故d|p，即 d=1或p。初等數(shù)論練習(xí)題九一、單項(xiàng)選擇題1、以下Legendre符號(hào)等于—1的30被-1是(D）A.3

4C。5D.611

11

11

11 B2、100至500的正整數(shù)中，能被17整除的個(gè)數(shù)是( ）BA.23B.24C。25D.26C3、設(shè)3｜500，但31|500，則α（ ）CA。245B。246C.247D。248C4、以下數(shù)組中，成為模7的完全剩余系的是( ）CA。－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ù)是1x≡7(mod16)23x≡5(mod16)x≡7(mod16)x=—1+4t，y=—2+3tx=—1+4t，y=—2+3t，tZ.

B。(2n－1，2n＋1）=1D。(2n＋1，n－1）=14、323

=1。 415、實(shí)數(shù)的小數(shù)部分記為{x}，則{－5｝＝0.75。4n=3k+2,k∈Z。63n4n＋1的最大公因數(shù)達(dá)到最大可能值n=3k+2,k∈Z。26×34=5184.26×34=5184.三、計(jì)算題1、解不定方程9x＋24y－5z=1000.解:解因（9,24）=（3，—5）=1知原方程有解。原方程化為9x24y=3t， 即 3x8y=t,(1)3t—5z=1000 3t-5z=1000，(2）t5u解（2）得z200，uZ，xu3x8y=5u得到y(tǒng)u

，u，vZ.xu8v故yu,。z200m2、設(shè)A｝是模m{x}x的小數(shù)部分,若(a,m）m求

axb{}i 。{}mi1xm的完全剩余系時(shí),axbm的完全剩余系,iaib（1jaib=kj（0jm1。從而：m{ax} m{ j}m1 j m1j 1 m(m) m1i k { 。m m m m m 2 2i1 j0 j1 j13n2,

i1,2，，nn互素的整數(shù)之和.1in(i,n)1解：設(shè)在1,2，，n中與n互素的（n)個(gè)數(shù)是a1,a2,,an，ai,n)=，1ain1，1i，則 （nai，n)=1，1nain1，1）因此,集合｛a1，a2,，a(n)}與集合｛na1,na2，，na(n｝是相同的,于是））a1aan =na1)na2)（nan，）2（a

a

)=因此:aaa =1。1 2 （n）

1 2 （n) 24>（a，)=1,x,x，，x

m,m{ax}。1 2

imi1其中{x｝表示x的小數(shù)部分。i i i i i ax=mqr，0r<mxm的簡(jiǎn)化剩余系知:axm的簡(jiǎn)化剩余rimi i i i i (m{ax}(mqr}(m)r

1(m)r

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

im m

2m 2 。i1 i1 i1四、證明題

i11、證明：設(shè)a是有理數(shù)，b是使ba為整數(shù)的最小正整數(shù)，若c和ca都是整數(shù),則b∣c。(提示：利用帶余數(shù)除法解決。）證明：設(shè)c=bq+r，0≤r＜b,q∈Z,則ca=（ba）q+ra。ca，ba∈Z，ra∈Z，ra=0a≠0r=0b∣c2p是素?cái)?shù)，證明：（) x,p1（1）（2p1)（modp；ⅱ） p1）1(modp。證明：(?。?xp110(modp)有解x1，2，，p1（modp)，，p1（1)（2(p1）（modp（ⅱ) 在（ⅰ)x=p。n

a32n，p

—1,則 1。p p:p∣an—1n1（modp）.又（p，a)=1n+1（modp。n12

a2n,所以(a

)2a(modp

a（modp)有解.故pp

1。m4p=4m+1（1。mpm（m（4m(1ppp

)

p12 1)2m1。5p是奇質(zhì)數(shù)，p1(mod4)(p1)!)21（modp）2解Wilson定理有：p1

p1

p1p1

((

p1))1(p1)!(1)

2 (p1)!(1)

212

(p 2 2 2

2(modp)。1p＝4+1x2(modp)x12(2m)(modp)。pp＝4m+1aa2≡1（modp)。初等數(shù)論練習(xí)題十一、單項(xiàng)選擇題1p1

Ap的質(zhì)數(shù)都不能整除則p一定（ 。ApA.B.CD.偶數(shù)2p，qp+q=99,p

q的值是（B）A。9413 B