初等数论练习题及答案

初等数论练习题一一、填空题1、（2420）=27；（2420)=_880_2、设a，n是大于1的整数，若an—1是质数,则a=_2.3、模9的绝对最小完全剩余系是_{-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、分母是正整数m的既约真分数的个数为_(m)_.7、18100被172除的余数是_256。8、65

=—1。 103p-1.9、若p是素数,则同余方程xp11(modp）的解数为p-1.二、计算题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的最小非负余数.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为奇数时,p-1+(p-）≡0(modp；(2）当a为偶数时，ap—1—（p-1）a≡0（modp)。证明：由欧拉定理知ap-1≡1(modp）及（p-1)a≡—1(modp)立得（1)和（2）成立。2、设a为正奇数，n为正整数，试证aa2m1n1时，有

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是某个整数。这说明式（1）n=k1也成立n成立。3p1≤k≤p—1Ckp1

（-1）k（mod。证明：设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的奇质数，证明：p6≡1（mod84=4×3×7，所以,只需证明:p6≡1（mod4) p6≡1（mod3) p6≡1（mod7） 84=4×3×7p37的奇质数,所以（p，4)=，(，3）=1（p,7）=1.(4）≡p2≡1(mod4，从而p≡1（mod4）.同理可证p6≡1（mod） p6≡1（mod7。故有p6≡1(mod8。p37的奇质数，证明：p61（mod168（p86）初等数论练习题二一、填空题1、(1000）=_16_;（除数函数：因数的个数）σ(1000)=_2340_.（和函数：所有因数的和）2、2010！的规范分解式中,质数11的次数是199 .3、费尔马（Fermat）数是指Fn=22n+1,这种数中最小的合数Fn中的n=5。4、同余方程13x≡5（mod31）的解是x≡29（mod31) 5、分母不大于m的既约真分数的个数为（2）+(3）+…+（m)。6、设7∣（80n-1)，则最小的正整数n=_6 。7、使41x+15y=C无非负整数解的最大正整数C= 559 。8、46=_1 。1019p是质数，np1,xn1（modp）n。二、计算题1、试求20022003200419除所得的余数.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)分别代入上式进行验证,1(mod。3a=5,m=21,1(modm）x.解：因为（5，21）=1,所以有欧拉定理知5（21）≡1（mod21）.又由于(21）=12，所以x|12，而12的所有正因数为1，2，3，4，6，12.x5x1(mod12)成立的最小数，经计算知：x=6。三、证明题113｜（54m+6+200（13进行计算性证明）证明：54m+46n+2000252m+642n+2000(—1)2m+（—1）2n+200020020（mod13)。2Wilson:n>1并且（n1）1(modnn是素数.nnn1n2，1n1，由题设易知（n1)!1（modn1，得01(modn1),矛盾。故n是素数。3ps1s位十进制数,pss证明:ss=ab，1<a，b〈s。则p110s110a)b110a1MM＞1s 9 9 9spa＞1pss也是一个素数。42p1是奇素数，则（p21）p0（mod2p1。证明：由威尔逊定理知1（2p！p（p1）(p）1pp!)2(modp1，由此得p）21p0（mod2p1。5p5的质数,证明：p4≡1(mod24（提示:可由欧拉定理证明)240=23×3×5，所以只需证:p4≡1(mod8）,p4≡1(mod3)，p4≡1（mod5）即可。事实上,由（8)=4，（3)=2,(5)=4初等数论练习题三一、单项选择题1、若是n为质数的（ C）条件.A.必要但非充分条件B.充分但非必要条件C.充要条件D.既非充分又非必要条件2na,b使b为既约分数的一组数是（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无非负整数解的最大整数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的十进位表示的各位数字之和可被9整除（4）划去a的十进位表示中所有的数字9,所得的新数被9整以上各条件中,成为9|a的充要条件的共有( C）.A。1。2C。3D.4二、填空题1、σ（2010）=_4896 ；(2010)=528。2、数C20100

的规范分解式中，质因数7的指数是_3。3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。4、同余方程24x≡6(mod34）的解是x1≡13(mod34)x2≡30(mod34)_。5、整数n>1，且（n—1)！+1≡0(modn)，则n为素数。6、3103被11除所得余数是_5_。7、60=_—1_。 97三、计算题1、判定(ⅰ） 2x3x23x10（mod5)是否有三个解；（ⅱ)x62x54x230(mod5)是否有六个解？ⅰ232310（mod532430（mod55x33243（235)（621215r)=6212155的倍数，故原方程没有三个解。(ⅱ） 5的同余方程,故原方程不可能有六个解.2n是正整数,求C12n

,C32n

C2n12n解：设(C1

,

,C2n1d，由

C2n1

22n1知d22n1，2n 2n 2n 2n 2n 2n设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。解：因为(18,77）=1，77)又由于6030，60。x18x1(mod77)成立的最小数,经计算知:x=30四、证明题1、若质数p≥5，且2p+1是质数，证明：4p+1必是合数.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、设p、q是两个大于3的质数，证明:p2≡q2(mod24）.证明：因为24=3×8,（3，8)=1，所以只需证明：p2≡q2（mod3)p2≡q2（mod8)同时成立。p,3=（q3=1p≡（mod3）2（mod3，都是奇数，所以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｝之间等于、大于、小于三种关系都有可能出现。1 1

时，{xy}=｛x}{y}= ；2 43 1 3 1当x= ，y= 时，{xy}= ，{x｝{y｝=，此时{xy}＞｛x}{y}；2 2 4 41，y=-1，y=-1时,{xy｝=1｛x｝{y｝=123634c

,d100，能使

，此时{xy｝＜{x}{y｝.c]=[k73]d d 100对于k=1，2，….,99均成立。证明：由（73，100）=1以及裴蜀恒等式可知：存在整数c，d，使得73d-100c=1从而73k-kc

=k(73d100c)

k= ,k〈100可知：100 d 100d 100d0＜73k-kc＜1设[k

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

c]=n=[kd 。]初等数论练习题四一、单项选择题1、若Fn=是合数，则最小的n是( D )。A。2 B.3 C.4 D。52、记号ba‖a表示ba｜a,但ba+1a。以下各式中错误的一个是（B )。A.218‖20! B.105‖50！ C。D。1316‖200！3、对于任意整数n，最大公因数(2n+1,6n-1）的所有可能值是（ A 。A.1 B.4 C.1或2 D。1，2或44、设a是整数,下面同余式有可能成立的是（C 。A.a2≡2（mod4） 。a2≡5(mod7) C。a2≡5(modD.a2≡6(mod5、如果≡b（modm，c是任意整数,则下列错误的是（）A．ac≡bc（modmc）B．m｜a-bC．(a,m）=(b，m) D．a=b+mt，t∈Z二、填空题1、d(10010)=_32 ，（10010)=_2880 。2nNnN=(n+！33n—15n+7的最大公因数达到最大可能值,nn=26k+9，k∈Z。4512的一个简化系,则这组数是35，55}526x+1≡33（mod74）x1≡24(mod74)x2≡61(mod74）_。6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10，y=4.7、54=_—1_。 89三、计算题1、设n的十进制表示是13xy45z，若792n，求x，y，z。解：因为792=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的末二位数。解：∵（3，100)=1，∴3φ(100)≡1（mod100）,而φ（100)=φ(22·52)=40，∴340≡1(mod100∴3406（34010·36（32)·32≡-19×9≡—171≡29(mod100）∴末二位数为29。3、求(214928+40)35被73除所得余数.解:（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、设a1，a2，，am是模m的完全剩余系，证明：(1）当m为奇数时，a1+a2++am≡0（modm)；（2）m

aam（modm。1 2 m 2证明:因为｛1,2，,m｝与｛a1,a2，，am}都是模m的完全剩余系，所以mai

im(m)(mod。2i1 i1m(m2当m为奇数时，由m1m(m22

，故maii1

m(m1)2

0（mod。(）m为偶数时，由（m,m+1)=1m

m(m1)

m(modm)。ii1

2 2（m）2、证明：若m＞2,a1，a2，，am)是模m的任一简化剩余系，则 a0(modm).（ ii1a1,m)m

m)也（（m）

（(m)是模m 的一个简化剩余系，于是：

a (ma)(mod

从而：i ii1 i1（m）

（m）2 aii1

(m)(modm

(m）

aii1

0(modm).23、设m>0是偶数，{a1，a2，，am}与{b1,b2，，bm｝都是模m的完全剩余系，证明:｛a1b1，a2b2，，ambm}不是模m的完全剩余系。证明：因为｛1，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联合上式与式（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。初等数论练习题五一、单项选择题1、设x、y分别通过模m、n的完全剩余系，若(C）通过模mn的完全剩余系.A.m、n都是质数，则mynxB。m≠n，则mynxC。(m,n）=1，则mynx D.（m，n）=1，则mxny2、1×3×5×…×2003×2005×2007×2009×2011规范分解式中11的幂指数是(A )A。100 。101 C.99 D。1023、n为正整数,若2n—1为质数，则n是（A )。质数B.合数C。3 D。2k(k为正整数)4、从100到500的自然数中，能被11整除的数的个数是(B )A。33 B.34 C。35 D.365、模100的最小非负简化剩余系中元素的个数是（C )。A.100 。10 C。40 D。4二、填空题1、同余方程ax+b≡0（modm)有解的充分必要条件是（a，m）∣b。2、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数,

p

p1q1 ( q3、20122012被3除所得的余数_1 。4、设n是大于2的整数，则（—1）n)= 1 。5、单位圆上的有理点的坐标是(

2ab

,a2b2)或(a2b2, 2ab

)ab是不全为零的整数。

a2b2

a2b2

a2b2

a2b26、若3258×a恰好是一个正整数的平方，则a的最小值为362.20117、已知2011是一素数，则 72 2011 三、计算题1、求32008×72009×132010的个位数字.解：32008×72009×132010≡32008×(-3）2009×32010≡-32008+2009+2010≡—36027≡-3×（32)3013≡3（mod10)。2、求满足(mn)=（m)+(n)的互质的正整数m和n的值.:由（m,n）=1知，(m）（m（n。于是有：（）(n）（)n）设(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元，现在用100元买这三样东西共100斤，问各买几斤？解：设买甲物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。相应的x，y,z的值是，，z）=(4，18，78，(8,1，81（12,4，84。四、证明题120112011|92010个:9=1201—1≡0（mod201。2010个2p4n+1型的质数,app—app=4n+1，ap的平方剩余，所以= =pa a 1= = p p pp

p2

a=1p=1 即：p-a也是p的平方剩余。3、已知p，q是两个不同的质数,且ap-1≡1(modq)，aq—1≡1(modp),证明:apq≡a(modpq).p,q是两个不同的质数知（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都是正整数,则(mn)=（m，n)([m，n］)。证明:易知mn与［m，n]有完全相同的质因数，设它们为pi（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类似的题：设m=m1m2，m1与m由相同的质因数，证明：(m）=m2（m1).初等数论练习题六一、填空题120112，3，5,…p,p至少是_43 .2、最大公因数（4n+3，5n+2)的可能值是_1，7 。33∣403α+|403‖40α=_18。43n+18的一个完全系的最小那些数是1，22。5、不定方程x2+y2=z2，2｜x，(x，y）=1，x，y,z〉0的整数解是且仅是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 二、计算题1173，57。105解：设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是质数p的平方剩余，问p是什么形式的质数？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)是否有解即可。∵17≡1（mod4）∴172362331721 23 17 17 1717 17 3 3∴x2≡17（mod23)无解，即原方程无解。三、论证题1、试证对任何实数x，恒有〔x〕+〔x+1〕=〔2x〕2证明：设x=［x]+α,0≤α〈1①当0≤α<1时，［x+1］=[x]，［2x]=2[x]∴等式成立2 2②当1≤α〈1时，［x+1]=[x]+1，[2x]=2［x]+1∴等式成立2 2故对任何实数x，恒有[x]+[x+1]=[2x]。22、证明:（1）当n为奇数时，3∣（2n+1）;（2)当n为偶数时，3|（2n+1)。证明：由2n+1≡（-1）n+1（mod3）立得结论。3(）3∣n（n为正整数）时，7∣（2n—1；（2）无论n为任何正整数，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为任何正整数，7|(2n+1).4m＞0，n＞0，m2m—1，2n+1）=1。证明一:m为奇数可知：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+）=。证明二：设（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。初等数论练习题七一、单项选择题A1、设a和b是正整数，则([a,b],[a,b])=( ）Aa bA．1B．aC．bD．(a，b）2、176至545的正整数中，13的倍数的个数是（A．27 B．28C．29 D．303、200！中末尾相继的0的个数是（ A）A．49 B．50C．51 D．52B4、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是( )BA．2的倍数B．3的倍数C．4的倍数D．5的倍数5、设n是正整数，下列选项为既约分数的是（A）A．4B．n1C．2n1D．n114n3 2n1 5n2 1二、填空题1、314162被163除的余数_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。三、计算题1x2y3z=41x2ytt3z=41得x=t2uy=t=413vz=vvZ,消去t得x=413v2uy=uz=vu,vZ。由此得原方程的全部正整数解为（x，y,z)=（413v2u,u，v),u〉0，v>0,413v2u>0。2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人,问这队士兵有几人?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)，因此所求的整数x=52+165t，tZ。由于这队士兵不超过170人，所以这队士兵有58人.3、判断同余方程x

?解:286=2×143，433是质数，(143，443）=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号286 2 143

44321

443 14 27 443 243443

2 2

143 143 1431431431 7114311433

11

8 2 2

7 3

∴原方程有解。四、证明题

7

1、设（a，m）=1，d0是使ad1（modm)成立的最小正整数，则（)d0；（ⅱ）i，j,0i，jd01ijai

（modm)。（1）证明：(ⅰ) 由Euler定理，d0（m)，因此，由带余数除法，有（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。因为（a,m）=1aij0(modm),0ij〈d0。这与d0的定义矛盾，所以式（1）必成立。2、证明：设a，b，c，m是正整数，m〉1，(b，m）=1，并且ba1（mod，bc（mod（1）d（a，bd1（mod。证明:由裴蜀恒等式知，存在整数x，y，使得axcy=d,显然xy〈0.〉0，<0由式（1）知：1baxbdcybd（bc）yd（mod。x〈0，y〉0,由式(1）知：1bcybdbaxbd（ba）xbd（mod。3、设p是素数,pbn1,nN，则下面的两个结论中至少有一个成立：（ⅰ)pbd1对于n的某个因数d<n成立；(ⅱ)p1(modn）.若2|n，p>2，则(ⅱ)中的modn可以改为mod2n。证明：dn，p1bn1，b1（modp2题有bd1（modp）.若d<n，则结论(ⅰ）得证。若d=n，则np1，即p1(modn）,这就是结论(ⅱ)。2|n，p〉2p1（mod2。由此及结论ⅱ，并利用同余的基本性质，得到p1（mod2n)。初等数论练习题八一、单项选择题1、设n>1，则n为素数是(n1)！1(modn)的（C）.A。必要但非充分条件 B.充分但非必要条C。充要条件 D。既非充分又非必要条件2、小于545的正整数中，15的倍数的个数是（C)A.34 B.35 C.36 D。37D3、500！的规范分解式中7的幂指数是（ ）DA.79 B。80 C.81 D。82D4、以下各组数中，成为模10的简化剩余系的是（ ）DA.1，9，－3,－1 B。1，－1,7,9C。5,7，11，13 D.－1，1,－3，3A5、设n是正整数,下列选项为既约分数的是（ ）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、如果一个正整数具有6个正因数,问这个正整数最小是12.x≡±1（mod5)。7、同余方程x3+x2—x-1x≡±1（mod5)。三、计算题1、已知563是素数，判定方程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、试求出所有正整数n，使得1n＋2n＋3n＋4n能被5整除。解:若n为奇数，则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为奇数时，1n＋2n＋3n＋4n0（modm为偶数时，1n＋2n＋3n＋4n4(mod。故当4|n时,5∣1n＋2n＋3n＋4n.四、证明题1、证明：若质数p〉2，则2P-1的质因数一定是2pk+1形。q2p-12p—1q≠2（2，q）=q|2p-12p≡1(mod设h是使得2x≡1（mod成立最小正整数，若〈则有这与p为数矛盾.从而h=p，于是 p|q-1。又∵q—1为偶数，2｜q—1，2p|q-1,q—1=2pk， q=2pk+1k∈Z.2、设m，n)=，证明：(+m≡1(modm。证明：因为（m，n）=1，所以由欧拉定理知:n（m)≡1（modm)，m(n)≡1(modn)于是m(n)+n（m）≡1（modm)，m(n）+n(m）≡1（modn)。又因为（m，n）=1，所以m(n)+n（m)≡1（modmn)。注：此题也可这样表述:若两个正整数a，b互质，则存在正整数m，n，使得+ndb。3、设（a，b）=1，a+b≠0，p为一个奇质数，证明:(ab,apbp)1或p。ab说明：事实上，设(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（否则设(d，b)=d′＞1，d′︱ad′︱b，这与（a，b）=1）于是（d故d|p，即 d=1或p。初等数论练习题九一、单项选择题1、以下Legendre符号等于—1的30被-1是(D）A.3

4C。5D.611

11

11

11 B2、100至500的正整数中，能被17整除的个数是( ）BA.23B.24C。25D.26C3、设3｜500，但31|500，则α（ ）CA。245B。246C.247D。248C4、以下数组中，成为模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、设n是正整数，则以下各式中一定成立的是(B )A.（n+1，3n＋1）=1C.（2n，n＋1)=1二、填空题1、25736被50除的余数是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、实数的小数部分记为{x}，则{－5｝＝0.75。4n=3k+2,k∈Z。63n4n＋1的最大公因数达到最大可能值n=3k+2,k∈Z。26×34=5184.26×34=5184.三、计算题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得到yu

，u，vZ.xu8v故yu,。z200m2、设A｝是模m{x}x的小数部分,若(a,m）m求

axb{}i 。{}mi1xm的完全剩余系时,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互素的整数之和.1in(i,n)1解：设在1,2，，n中与n互素的（n)个数是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的小数部分。i i i i i ax=mqr，0r<mxm的简化剩余系知:axm的简化剩余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、证明：设a是有理数，b是使ba为整数的最小正整数，若c和ca都是整数,则b∣c。(提示：利用带余数除法解决。）证明：设c=bq+r，0≤r＜b,q∈Z,则ca=（ba）q+ra。ca，ba∈Z，ra∈Z，ra=0a≠0r=0b∣c2p是素数，证明：（) 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是奇质数，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)。初等数论练习题十一、单项选择题1p1

Ap的质数都不能整除则p一定（ 。ApA.B.CD.偶数2p，qp+q=99,p

q的值是（B）A。9413 B