初等数论练习题及答案

1、初等数论练习题一、填空题1、(2420)=27;(2420)=8802、设a,n是大于1的整数,假设an-1是质数,那么a=_2.3、模9的绝对最小完全剩余系是-4,-3,-2,-1,0,1,2,3,4.4、同余方程9x+12三0(mod37)的前犁是xm11(mod37).5、不定方程18x-23y=100的通解是x=900+23t,y=700+18ttZ.6、分母是正整数m的既约真分数的个数为(m).7、18100被172除的余数是256.8、65103=-1o9、假设p是素数,那么同余方程xp"(modp)的解数为p-1二、计算题1、解同余方程：3x211x200(mod105

2、>解：因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、判断同余方程x2m42(mod107)是否有解解：(为107()107/42、(一)1107/237、()1071,()1072、/3、一)(一)107107311

3、071、丁F/107、D22()3)10727j丝J1072(2)1,()(1)22(107)(-)310777故同余方程x2m42(mod107)有解.3、求(127156+34)28除以111的最小非负余数解：易知1271m50(mod111).由502三58(mod111),503m58X50m14(mod111),509三143三80(mod111)知5028三(509)3X50m803X50m803X50m68X50m70(mod111)从而5056m16(mod111).故(127156+34)28三(16+34)28三5028三70(mod111)三、证实题1、p是质数,(a,p

4、)=1,证实：(1)当a为奇数时,ap-1+(p-1)am0(modp)；(2)当a为偶数时,ap-1-(p-1)am0(modp).证实：由欧拉定理知ap-1=1(modp)及(p-1)am-1(modp)立得(1)和(2)成立.2n2、设a为正奇数,n为正整数,试证am1(mod2n+2).(1)证实设a=2m1,当n=1时,有a2=(2m1)2=4m(m1)11(mod23),即原式成立.一,2kkjc设原式对于n=k成立,那么有a1(mod2k2)a=1q2k2,k1其中qZ,所以a=(1q2k+2)2=1q2k+31(mod2k+3),其中q是某个整数.这说明式(1)当n=k1也成立

5、.由归纳法知原式对所有正整数n成立.3、设p是一个素数,且1&k&p-1.证实：Cp1(-1)k(modp)京口日Ack(p1)(p2)(pk)小证实：设A=Cp1得：k!A=(p-1)(p-2)(p-k)三(-1)(-2)(-k)(modp)又(k!,p)=1,故人=或1(-1)k(modp)4、设p是不等于3和7的奇质数,证实：p6m1(mod84).说明：由于84=4X3X7,所以,只需证实：p6=1(mod4)p6=1(mod3)p6=1(mod7)同时成立即可.证实：由于84=4X3X7及p是不等于3和7的奇质数,所以(p,4)=1,(p,3)=1,(p,7)=1.由

6、欧拉定理知：p(4)=p2=1(mod4),从而p6三1(mod4).同理可证：p6=1(mod3)p6=1(mod7).故有p6=1(mod84).注：设p是不等于3和7的奇质数,证实：p6三1(mod168).(见赵继源p86)初等数论练习题二一、填空题1、(1000)=16;(除数函数：因数的个数)(T(1000)=2340.(和函数:所有因数的和)2、2021!的标准分解式中,质数11的次数是199.3、费尔马(Fermat)数是指Fn=220+1,这种数中最小的合数Fn中的n=5.4、同余方程13xm5(mod31)的解是x三29(mod31)5、分母不大于m的既约真分数的个数为(2

7、)+(3)+-+(m).6、设7I(80n-1),那么最小的正整数n=6.7、使41x+15y=C无非负整数解白最大正整数C=_559_.8、也=1.10119、假设p是质数,np1,那么同余方程xn1(modp)的解数为n_二、计算题1、试求200220032004被19除所得的余数.解：由2002三7(mod19)20022三11(mod19)20023m1(mod19)又由三22004三(22)1002m1(mod3)可得：200420022003三20023n+1三(20023)nx2002m7(mod19)2、解同余方程3x144x106x180(mod5).解：由Fermat定理,

8、x5x(mod5),因此,原同余方程等价于2x2x30(mod5)将x0,1,2(mod5历别代入上式进行验证,可知这个同余方程解是x1(mod5).3、a=5,m=21,求使ax1(modm)成立的最小自然数x.解：由于(5,21)=1,所以有欧拉定理知5(21)三1(mod21).又由于(21)=12,所以x|12,而12的所有正因数为1,2,3,4,6,12.于是x应为其中使5x1(mod12)成立的最小数,经计算知：x=6o三、证实题1、试证13|(54m+46n+2000).(提示：可取模13进行计算性证实)证实：54m+46n+2000252m+642n+2000(-1)2m+(-

9、1)2n+0(mod13).2、证实Wilson定理的逆定理：假设n>1,并且(n1)!1(modn),那么n是素数.证实：假设n是合数,即n=mn2,1<n1<n,由题设易知(n1)!1(modm),得01(modm),矛盾.故n是素数.3、证实：设ps表示全部由1组成的s位十进制数,假设ps是素数,那么s也是一个素数.证实：假设s是合数,即s=ab,1<a,b<s.那么Ps111也(O-M,其中M>1是正整数.s999由Pa>1也是正整数知ps是合数,这与题设矛盾.故s也是一个素数.4、证实：假设2p1是奇素数,那么(p!)2(1)p0(mod2p

10、1).证实：由威尔逊定理知1(2p)!=p!(p1)(2p)(1)p(p!)2(mod2p1),由此得(p!)2(1)p0(mod2p1).5、设p是大于5的质数,证实：p4m1(mod240).(提示：可由欧拉定理证实)证实：由于240=23X3X5,所以只需证：p4=1(mod8),p4=1(mod3),p4=1(mod5)即可.事实上,由(8)=4,(3)=2,(5)=4以及欧拉定理立得结论.初等数论练习题三一、单项选择题1、假设n>1,(n)=n-1是n为质数的(C)条件.A.必要但非充分条件B.充分但非必要条件C充要条件D既非充分又非必要条件2、设n是正整数,以下各组a,b使台

11、为既约分数的一组数是(D).a=n+1,b=2n-1=2n-1,b=5n+2C.a=n+1b=3n+1=3n+1,b=5n+23、使方程6x+5y=C无非负整数解的最大整数C是(A).24C4、不是同余方程28x三21(mod35)的解为(D).三2(mod35)B.x7(mod35)C.217(mod35)D.x29(mod35)5、设a是整数,(1)am0(mod9)(2)a三2021(mod9)(3)a的十进位表示的各位数字之和可被9整除划去a的十进位表示中所有的数字9,所得的新数被9整除以上各条件中,成为91a的充要条件的共有(C).个个个个、填空题1、(r(2021)=4896;(2

12、021)=5282、数C200的标准分解式中,质因数7的指数是_33、每个数都有一个最小质因数.所有不大于10000的合数的最小质因数中,最大者是974、同余方程24xm6(mod34)的解是xi三13(mod34)也三30(mod34).5、整数n>1,且(n-1)!+1m0(modn),那么n为素数.6、3103被11除所得余数是57、6097三、计算题1、判定(i)2x3x23x10(mod5混否有三个解；(ii)x62x54x230(mod5)是否有六个解解：(i)2x3x23x10(mod5)等价于x33x24x30(mod5),又x5x=(x33x24x3)(x23x5)+(

13、6x212x15),其中r(x)=&212x15的系数不都是5的倍数,故原方程没有三个解.(ii)由于这是对模5的同余方程,故原方程不可能有六个解.2、设n是正整数,求C12n,C2n,C2n1的最大公约数.解：设(C2n,C2n,C2n1)d,由C2nC2n/22n1知d22n1,设2k|n且2k+1|n,即2k+1|n,2n那么由2k+1|C12n及2k1|Ci2n丁Ci2n11,i=3,5,2n1得d=2k+1.3、a=18,m=77,求使ax1(modm)成立的最小自然数x.解：由于(18,77)=1,所以有欧拉定理知18(77)三1(mod77).又由于(77)=60,所以x

14、|60,而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30,60.于是x应为其中使18x1(mod77)成立的最小数,经计算知：x=30.四、证实题1、假设质数p>5,且2p+1是质数,证实：4p+1必是合数.证实：由于质数p>5,所以(3,p)=1,可设p=3k+1或p=3k+2.当p=3k+1时,2p+1=6k+3是合数,与题设矛盾,从而p=3k+2,此时2p+1是形如6k+5的质数,而4p+1=12k+9=3(4k+3足合数.注：也可设p=6k+r,r=0,1,2,3,4,5.再分类讨论.2、设p、q是两个大于3的质数,证实：p2三q2(mod24).证

15、实：由于24=3X8,(3,8)=1,所以只需证实：p2=q2(mod3)p2=q2(mod8)同时成立.事实上,由于(p,3)=1,(q,3)=1,所以p2=1(mod3),q2m1(mod3),于是p2三q2(mod3),由于p,q都是奇数,所以p2=1(mod8),q2m1(mod8),于是p2=q2(mod8).故p2三q2(mod24).3、假设x,yCR+,(1)证实：xy)xy;(2)试讨论xypfxy的大小关系.注：我们知道,xy>x+y,x+y<x+y0此题把加法换成乘法又如何呢证实：(1)设x=x+a,0&a<1,y=y+B,0<B<1

16、.于是xy=xy+bx+ay+ap所以xy=xy+Bx+ay+a?>>xy.(2)xypfxy之间等于、大于、小于三种关系都有可能出现.,1一1当x=y=一时,xy=xy=-;24当x=3,y=1时,xy=W,xy=1,此时xy>xy;2244当x=-1,y=-1时,xy=1,xy=1,此时xy<xy.23634、证实：存在一个有理数,其中d<100,能使k&=k迫dd100对于k=1,2,.,99均成立.证实：由(73,100)=1以及裴蜀恒等式可知：存在整数c,d,使得73d-100c=1从而正k上=k(73d100c)=上,由k<100可知:1

17、00d100d100d0<追k&<2100dd设k-c-=n,贝(J蛆<n+1=n-Id,于是ddd100-d=n+1,d故啕=n=k?.初等数论练习题四、单项选择题,2n1、假设Fn=21是合数,那么最小的门是(D).A.2B.3C.4D.52、记号balla表示ba|a,但ba+1|a.以下各式中错误的一个是(B).A.21M20!B.1C5II50!C.11911100!D.1316II200!3、对于任意整数n,最大公因数(2n+1,6n-1)的所有可能值是(A).A.1B.4C.1或2D.1,2或44、设a是整数,下面同余式有可能成立的是(C).A.a2m2

18、(mod4)B.孑三5(mod7)C.3三5(mod11)D.a2m6(mod13)5、如果amb(modm),c是任意整数,那么以下错误的选项是(A)A.ac=bc(modmc)B.m|a-bC.(a,m)=(b,m)D.a=b+mt,tCZ二、填空题1、d(10010)=_32_M10010)=_2880一2、对于任意一个自然数n,为使自N起的n个相继自然数都是合数,可取N=(n+1)!3、为使3n-1与5n+7的最大公因数到达最大可能值,整数n应满足条件n=26k+9,kC乙4、在5的倍数中,选择尽可能小的正整数来构成模12的一个简化系,那么这组数是5.25.35,555、同余方程26x

19、+1m33(mod74)的解是X1三24(mod74)X2三61(mod74)6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10,y=4.7、54,=-189三、计算题1、设n的十进制表示是I3xy45z,假设792n,求x,y,z.解：由于792=8911,故792n8n,9n及11n.我们有8n845zz=6,以及9n913xy45z=19Xy9xy1,(1)11n11z54yx31=3yx113yx0(2)由于0x,y9,所以由式(1)与式(2)分别得出xy1=9或18,3yx=0或11.这样得到四个方程组:其中a取值9或18,b取值0或11.在0x,y9的条件下解这四个

20、方程组,得到：x=8,y=0,z=6.2、求3406的末二位数.解：V(3,100)=1,.3W00)三1(mod100),而帕00)=M2252)=40,.二340三1(mod100)；3406=(340)1036三(32)232m-19X关-171m29(mod100)末二位数为29.3、求(214928+40)35被73除所得余数.解：(214928+40)35三(3228+40)35三(32乂32)14+4035三(102414+40)35三(214+40)35三(210乂24+40)35三(25+40)35三7235三-1三72(mod73)四、证实题1、设a1,a2,am是模m的完

21、全剩余系,证实:(1)当m为奇数时,(2)当m为偶数时,a1+a2+am=0(modm)；a1+a2+am=m(modm).证实：由于1,2,ma1,2a2,am都是模m的完全剩余系,所以maii1mimm)(modm).i12(D当m为奇数时,由寸Z即得：m吗故：,汕尸0(modm)0当m为偶数时,由(m,m+1)=1即得：aim(m_1)m(modm).ii22(m)2、证实：假设m>2,ai,a2,a(m)是模m的任一简化剩余系,那么ai0(modm).i1证实：假设ai,a2,a(m)是模m的一个简化剩余系,那么m-ai,m-a2,m-a(m)也是模m(m)(m)(m)的一个简化

22、剩余系,于是：ai(mai)(modm).从而：2aim(m)(modm).又i1i1i1.一(m(m)由于m>2,(m)是偶数.故：aim0(modm).i123、设m>0是偶数,a1,a2,ampfb1,b2,bm都是模m的完全剩余系,证实：a1b1,a2b2,ambm不是模m的完全剩余系.证实：由于1,m同理bii12,m与a1,maii1m/一(modm)0a2,am都是模m的完全剩余系,所以mi吗m(modm).(1)如果ab1,a2b2,ambm是*Km的完全剩余系,那么也有(aibi)m(modm).联合上式与式和式,得到°三三mw卒这是不可能的,所以a1b

23、1,a2b2,ambm不能是模m的完全剩余系.4、证实：(1)2730Ix13-x;(2)24Ix(x+2)(25X-1);初等数论练习题五一、单项选择题1、设x、y分别通过模m、n的完全剩余系,假设(C)通过模mn的完全剩余系.、n都是质数,那么mywn,那么mynxC.(m,n)=1,贝UmynxD.(m,n)=1,贝Umxny2、1X3X5X-X2003X2005X2007X2021X2021标准分解式中11的幕指数是(A).101C3、n为正整数,假设2n-1为质数,那么n是(A).A.质数B.合数(k为正整数)4、从100至IJ500的自然数中,能被11整除的数的个数是(B).34C

24、5、模100的最小非负简化剩余系中元素的个数是(C).10C二、填空题1、同余方程ax+bm0(modm)有解的充分必要条件是(a,m)Ib.p1q12、高斯称反转定律是数论的酵母,反转定律是指设p与q是不相同的两个奇质数.(q)(1产至(p)3、被3除所得的余数为_1_.4、设n是大于2的整数,那么(-1)(n)=_1_02,22,25、单位圆上的有理点的坐标是(二0工匚)或(乌二),其中a与b是不全为22,2222,22abababab零的整数.6、假设3258Xa恰好是一个正整数的平方,那么a的最小值为36207、2021是一素数,那么=-102021一一三、计算题1、求32021X72

25、021X132021的个位数字.解.32021X72021X132021=32021乂(-3)2021x32021=-32021+2021+2021=-36027=-3X(32)3013m3(mod10).2、求满足(mn)=(m)+(n)的互质的正整数m和n的值解：由(m,n)=1知,(mn)=(m)(n).于是有：(m)+(n)=(m)(n)设(m)=a,(n)=b,即有：a+b=abo显然aIb,HbIa,因止匕a=b.于是由2a=a2得a=2,即(m)=(n)=2.故m=3,n=4或m=4,n=3.3、甲物每斤5元,乙物每斤3元,内物每三斤1元,现在用100元买这三样东西共100斤,问

26、各买几斤解：设买甲物x斤,乙物y斤,内物z斤,那么15x3y-z=100,3xyz=100o消去z,得到7x4y=100.(1)显然x=0,y=25是方程(1)的解,因此,方程(1)的一般解是x4ty257ttZ由于x>0,y>0,所以0Vt3.即t可以取值t1=1,t2=2,t3=3.相应的x,y,z的值是(x,y,z)=(4,18,78),(8,11,81),(12,4,84)四、证实题1、2021是质数,那么有2021|999.2021个证实：999=102021-1m0(mod2021).2021个2、设p是4n+1型的质数,证实假设a是p的平方剩余,那么p-a也是p的平方

27、剩余证实：由于质数p=4n+1,a是p的平方剩余,所以p1a1aza.=(1)=1pppp即：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(modp),又由题设aq-1=1(modp)得到：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有完全相同的质因数,设

28、它们为pi(1<i<k),那么/、111(mn)mn(1)(1)(1)PiP2Pk/、111(m,n)m,n(1)(1)(1)P1P2Pk又mn=(m,n)m,n“111、故(mn)(m,n)m,n(1一)(1一)(1)(m,n)(m,n).P1P2Pk类似的题：设m=m1m2,m1与m由相同的质因数,证实：(m)=m2(m.初等数论练习题六一、填空题1、为了验明2021是质数,只需逐个验算质数2,3,5,书都不能整除2021,此时,质数p至少是43.2、最大公因数(4n+3,5n+2)的可能值是_1/_.3、设3aI40!,而3a+1|40!,即3alI40!,贝Ua=18.4、

29、形如3n+1的自然数中,构成模8的一个完全系的最小那些数是1,4,7,10,13,16,19,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(mod43)的解是x三25(mod43).737、1991、将区写成三个既约分数之和,它们的分母分别是3,5和7.105一、117xyz解：设右o7二,即35x21y15z=17,因(35,21)=7,(7,15)=1,117,故有105357解.分别解5x3y=17t15z=17得x=

30、t3u,y=2t5u,uZ,t=1115v,z=47VvZ,消去t得x=1115v3u,y=2230v5u,z=47v,u,vZo令u=0,v=-1得到：x=4,y=-8,z=3o即：-171052、假设3是质数p的平方剩余,问p是什么形式的质数解：由二次互反律3p注意至p>3,p只能为pp1(mod3)且-31(mod4)1(mod4)31只能以下情况p1(mod3)p1(mod4)p1(mod3)1(mod4)p1(mod12)或p1(mod12)03、判断不定方程x2+23y=17是否有解解：只要判断x2m17(mod23)是否有解即可1723617三1(mod4)；23行行171

31、7317173,.x2=17(mod23)无解,即原方程无解.三、论证题1、试证对任何实数x,包有x+Cx+-=2x2证实：设x=x+a,0<a<1当0&a<:时,x+-1=x,2x=2冈.等式成立当工&a<1时,x+-=x+1,2x=2x+1.等式成立22故对任何实数x,恒有冈+x+1=2x.22、证实：(1)当n为奇数时,3I(2n+1);(2)当n为偶数时,3|(2n+1)0证实：由2n+1三(-1)n+1(mod3)立得结论3、证实：(1)当31n(n为正整数)时,71(2n-1);(2)无论n为任何正整数,7|(2n+1)0证实：(1)设n=3

32、m,那么2n-1=8m-1三0(mod7),即：7I(2n-1);(2)由于23mm1(mod7)得23m+1m2(mod7),23m+1+1三3(mod7),23m+2+1三5(mod7).故无论n为任何正整数,7|(2n+1)04、设m>0,n>0,且m为奇数,证实：(2m-1,2n+1)=1.证实一：由m为奇数可知：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=2o这说明：(2m-1,2n+1)|2由于2n+1,2m-1均为奇数可知:(2m-1,2n+1)=1

33、.证实二：设(2m-1,2n+1)=d,那么存在s,tCZ,使得2m=sd+1,2n=td-1.由此得到:2mn=(sd+1)n,2mn=(td-1)m于是2mn=pd+1=qd-1,p,qCZ.所以：(q-p)d=2.从而dI2,就有d=1或2.由由于m为奇数,所以d=1.即(2m-1,2n+1)=1.注：我们已证过：记Mn=2n1,对于正整数a,b,有(Ma,Mb)=M(a,b).显然当a*b,a,b为质数时,(Ma,Mb)=1.初等数论练习题七一、单项选择题1、设a和b是正整数,那么(叵旦,回以)=(A)abA.1B.aC.bD.(a,b)2、176至545的正整数中,13的倍数的个数是

34、(B)A. 27B. 28C.29D.303、200!中末尾相继的0的个数是(A)A.49B.50C.51D.524、从以下满足规定要求的整数中,能选取出模20的简化剩余系的是(B)A.2的倍数B.3的倍数C.4的倍数D.5的倍数5、设n是正整数,以下选项为既约分数的是(A)“21n4cn1仆2n1n1A.B.C.D.14n32n15n23n1二、填空题1、314162被163除的余数是10(欧拉定理)2、同余方程3x三5(mod13)的解是x6(mod13).3、(逵工1847,一4、-九=-4.5、为使n-1与3n的最大公因数到达最大的可能值,那么整数n应满足条件n=3k+1,kCZ6、如

35、果一个正整数具有21个正因数,问这个正整数最小是26义32=576.7、同余方程x3+x2-x-1=0(mod3)的解是x三1,2(mod3).三、计算题1、求不定方程x2y3z=41的所有正整数解.解：分别解x2y=tt3z=41得x=t2uy=uuZ,t=413vz=vvZ,消去t得x=413v2uy=uz=vu,vZo由此得原方程的全部正整数解为(x,y,z)=(413v2u,u,v),u>0,v>0,413v2u>0.2、有一队士兵,假设三人一组,那么余1人；假设五人一组,那么缺2人；假设十一人一组,那么余3人.这队士兵不超过170人,问这队士兵有几人解：设士兵有x人

36、,由题意得x1(mod3),x2(mod5),x3(mod11).在孙子定理中,取mi=3,m2=5,m3=11,m=3511=165Mi=55,M2=33,M3=15,M1=1,M2=2,M3=3,那么x1551(-2)332315358(mod165)因此所求的整数x=52+165,tZ.由于这队士兵不超过170人,所以这队士兵有58人.23、判断同余方程x286(mod443)是否有解解：286=2X143,433是质数,(143,443)=1奇数143不是质数,但可用判定雅可比符号计算的勒让德符号2862143(1)4(史3上义工443243443''''

37、;143143143143143171143114331(l) 8(1)227鼻1；原方程有解.773四、证实题1、设(a,m)=1,do是使ad1(modm)成立的最小正整数,那么(i)do(m);(ii)对于任意的i,j,0i,jdo1,ij,有aiaj(modm).(1)证实：(i)由Euler定理,do(m),因此,由带余数除法,有(m) =qdor,qZ,q>0,0r<do.因此,由上式及do的定义,利用欧拉定理得到(m)qdorr1 aaa(modm),即整数r满足ar1(modm),0r<do.由do的定义可知必是r=o,即do(m).(ii)假设式(1)不成立

38、,那么存在i,j,oi,jdo1,ij,使aiaj(modm).不妨设i>j.由于(a,m)=1,所以aijo(modm),o<ij<do.这与do的定义矛盾,所以式(1)必成立.2、证实：设a,b,c,m是正整数,m>1,(b,m)=1,并且ba1(modm),bc1(modm)(1)记d=a,c),那么bd1(modm)0证实：由裴蜀恒等式知,存在整数x,y,使得axcy=d,显然xy<0假设x>0,y<0,由式(1)知：1bax=bdbcy=bd(bc)ybd(modm).假设x<0,y>0,由式(1)知：1bcy=bdbax=bd(

39、ba)xbd(modm).3、设p是素数,pbn1,nN,那么下面的两个结论中至少有一个成立：(i)pbd1对于n的某个因数d<n成立；(ii)p1(modn).假设2|n,p>2,那么(ii)中的modn可以改为mod2n.证实：记d=(n,p1),由bn1,bp11(modp),及第2题有bd1(modp)0假设d<n,那么结论(i)得证.假设d=n,贝Unp1,即p1(modn),这就是结论(ii).假设2|n,p>2,那么p1(mod2).由此及结论(ii),并利用同余的根本性质,得至Up1(mod2n).初等数论练习题八一、单项选择题1、设n>1,那么n

40、为素数是(n1)!1(modn)的(C).A.必要但非充分条件B.充分但非必要条件C充要条件D既非充分又非必要条件2、小于545的正整数中,15的倍数的个数是(C).35C3、500!的标准分解式中7的幕指数是(D).80C4、以下各组数中,成为模10的简化剩余系的是(D),9,3,-1,1,7,7,11,13D.-1,1,3,35、设n是正整数,以下选项为既约分数的是(A)3n1n12n1n15n22n15n23n11、(T(120)=360o2、7355的个位数字是33、同余方程3x=5(mod14)的解是x11(mod14).4、()=-1o235、=-2.6、7、如果一个正整数具有6个

41、正因数,问这个正整数最小是同余方程x3+x2-x-1=0(mod5)的角犁是x三±1(mod5).12.三、计算题1、563是素数,判定方程x2429(mod563混否有解.解：把黑看成Jacobi符号,我们有42956342915631-o5635631)224294291344292429674291)42921678429674296714291(1)2242967429672767271671(1)226727672713272711311)222713工131,故方程x2429(mod563)有解.2、求出模23的所有的二次剩余和二次非剩余.解：模23的所有的二次剩余为18

42、(mod23);x1,2,3,4,6,8,9,12,13,16,模23的所有的二次非剩余为x5,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,mCZ,那么1n+2n+3n+4n12m+22m+(-2)2m+(-1)2m2+2X22m=2+2X4m=2+2X(-1)m(mod5);当m为奇数时,1n+2n+3n+4n0(mod5);当m为偶数时,1n+2n+3n+4n4(mod5).故当41n时,5I1

43、n+2n+3n+4n.四、证实题1、证实：假设质数p>2,那么2P-1的质因数一定是2pk+1形.证实：设q是2P-1的质因数,由于2P-1为奇数,.二qw2,(2,q)=1.由条件q|2P-1,即2Pm1(modq).设h是使得2xm1(modq)成立最小正整数,假设1<h<p,那么有h|p.这与p为质数矛盾.从而h=p,于是p|q-1o又=q-1为偶数,2|q-1,2p|q-1,q-1=2pk,即q=2pk+1kCZ.2、设(m,n)=1,证实：m+n(m)三1(modmn).证实：由于(m,n)=1,所以由欧拉定理知：n(m)三1(modm),m(n)=1(modn)于

44、是m+n(m)三1(modm),m+n(m)三1(modn).又由于(m,n)=1,所以m+n(m)三1(modmn).注：此题也可这样表述：假设两个正整数a,b互质,那么存在正整数m,n,使得am+bn三1(mdab)0apbp3、设(a,b)=1,a+bw0,p为一个奇质数,证实：(ab,)1或p.abpp说明：事实上,设(ab,a)d,只需证实：d|p即可.ab证实：由a+b4(moda+b),即a三b(moda+b),知ak汽-b)k(moda+b).pp甘vabp1p2,p2p1p1p1,p1,p1,另十00kap-l.乂aababbbbbpb(modab).abpp令(ab,a)d

45、,贝Ud|pbP-1.又(a,b)=1,d|(a+b)知(d,b)=1.ab(否那么设(d,b)=d'>1,立即得到d'|a和d'|b,这与(a,b)=1矛盾.)于是(d,bp-1)=1o故d|p,即d=1或p.初等数论练习题九、单项选择题1、以下Legendre符号等于-1的30被-1是DA.A1A_6、100至500的正整数中,能被17整除的个数是B11111111A.23B.24C.25D.263、设3|500!,但31|500!,那么a=(C)A.246.2484、以下数组中,成为模7的完全剩余系的是(C)A.14,4,0,5,15,18,19B.7,10

46、,14,19,25,32,40C.4,2,8,13,32,35,135D.3,3,4,4,5,5,05、设n是正整数,那么以下各式中一定成立的是(B)A.(n+1,3n+1)=1B.(2n-1,2n+1)=1C.(2n,n+1)=1D.(2n+1,n-1)=1、填空题1、25736被50除的余数是12、同余方程3x三5(mod16)的解是xm7(mod16)3、不定方程9x12y=15的通解是x=-1+4,y=-2+3,tZ.4、32341=15、实数的小数局部记为x,那么-5=4一6、为使3n与4n+1的最大公因数到达最大可能值,整数n应满足条件n=3k+2、kC乙7、如果一个正整数具有35

47、个正因数,问这个正整数最小是26X34=5184.三、计算题1、解不定方程9x+24y-5z=1000o解：解因(9,24)=3,(3,-5)=1知原方程有解.原方程化为9x24y=3t,即fx8y=t,(1)3t-5z=10003t-5z=1000,(2)解2得5u2003uuZ,再解3x8y=5u得到u8vu3vxu8v故yu3v,u,vZ.z2003u2、设A=xi,x2,xm是模m的一个完全系,以x表示x的小数局部,假设(a,m)=1,解：当x通过模m的完全剩余系时,axb也通过模m的完全剩余系,因此对于任意的i(1im),axb一定与且只与某个整数j(1jm)同余,即存在整数k,使得

48、axb=kmj,(0jm-1)0从而：mm1m1m1axibkjjj1m(m1)m_JoiJm'j0lm'jmj1mm223、设整数n2,求：i.即在数列1,2,n中,与n互素的整数之和.1in(i,n)1解：设在1,2,n中与n互素的(n)个数是a1,a2,a(n),(a,n)=1,1ain1,1i(n),那么(nai,n)=1,1nan1,1i(n),因此,集合a1,a2,a(n)与集合na1,na2,na(n)是相同的,于是a1?a2?a(n)=(na1)(na2)(na(n),12(a1?a2?a(n)=n(n),因此：a1？a2?a(n)=n(n).2)写(m4、设m

49、>1,(a,m)=1,x1,x2,x(m)是模m的简化剩余系,求：i1其中x表示x的小数局部.解：设ax=mqri,0ri<m,由xi通过模m的简化剩余系知：ax也通过模m的简化剩余系,从而ri通过模m的最小非负简化剩余系,于是：(m)(m)ii净iiqim1(m).2(),工()r,m(m)iimmii2m四、证实题1、证实：设a是有理数,b是使ba为整数的最小正整数,假设c和ca都是整数,那么bIco(提示：利用带余数除法解决.)证实：设c=bq+r,0<r<b,qCZ,贝Uca=(ba)q+ra由于ca,baCZ,所以raCZ,于是ra=0,由aw0得r=0.故b

50、Ic.2、设p是素数,证实：(i)对于一切整数x,xp11(x1)(x2)(xp1)(modp);(ii)(pi)!1(modp).证实：(i)xp110(modp)有解x1,2,p1(modp),故对于一切整数x,xp11(x1)(x2)(xp1)(modp);.(ii)在(i)中令x=p.a3、证实：右21n,p是奇质数,pIan-1,那么一1.p证实：由pIan-1知：an1(modp).又(p,a)=1得到an+1?a(modp).n1由于2|n,所以(a2)2a(modp),即x2?a(modp)有解.故1.p4、证实：假设p=4m+1是一质数,那么(m)1.p也一证实：(史)(竺)

51、()(1)2(1)2m1.ppp5、设p是奇质数,p1(mod4),那么：(-p2)!)21(modp)解由Wilson定理有：p1p11(p1)!(1)2(p1)!(1)2121p2-(p1)(-p2-)!)2(modp)注：(1)设p为质数且p=4m+1,那么同余方程x21(modp)的解是x12(2m)(modp).(2)设p为质数且p=4m+1,假设且唯假设存在一个正整数a,使得a2三1(modp)初等数论练习题十一、单项选择题1、设p是大于1的整数,如果所有不大于行的质数都不能整除p,那么p一定是AA.素数B.合数C奇数D.偶数2、两个质数p,q,满足p+q=99,那么E9的值是BqpB941394139413.19499.1113、2021!的标准分解式中,7的最高幕指数为CA.331B.332C.333D.3344、n为正整数,假设2n+1为质数,那么口是DA.质数B.合数C.1D.2kk为非负整数5、当n>2时,欧拉函数一定是B.A.奇数B.偶数C.1D.2二、填空题1、如果p是质数,a是整数,那么有a,p=1或者pIa.p12、设p是奇质数,a,p=1,那么a是模p的平方非剩余的充要条件是a"2"1modp3、从1