初等数论练习题答案

1、初等数论练习题一一、填空题1、d(2420)=12;0(2420)=_880_2、设比n是大于1的整数，若是质数，则a=_2.3、模9的绝对最小完整节余系是_卜4,-3,-2,-1,0,1,2,3,4.4、同余方程9x+12=0(mod37)的解是x三11(mod37)。5、不定方程18x-23y=100的通解是x=900+23t,y=700+18ttZ。.6、分母是正整数m的既约真分数的个数为(山)_。7、18100被172除的余数是_殛。9、若p是素数，则同余方程L1l(modp)的解数为p-1。二、计算题0(modlO5)o1、解同余方程：疋11X203解：因105=357,同余方程3x

2、211X20的解为x1(mod3),0(mod3)同余方程3x211X380(mod5)的解为x0,3(mod5),同余方程3x211X200(mod7啲解为x2,6(mod7),故原同余方程有4解。作同余方程组：x(mod3),xb2(mod5),xb3(mod7),此中?=1,b2=0,3,b3=2,6,由子定理得原同余方程的解为x13,55,58,100(mod105)o2.判断同余方程/三42(mod107)能否有解?42*3x7237)=(二)(一)(-)10710710710710723I。，2=(一1)呼(凹1077v()=-1,()=(-1)22(ArL)=-)=L107107

3、33.-.()=1107故同余方程x2三42(mod107)有解。3、求(12715C+34)23除以ill的最小非负余数。解：易知1271=50(mod111)0由502=58(mod111),503三58X50三14(mod111),509=143=80(mod111)知502G=(509)彳x50三803X50三803x50三68x50三70(mod111)从而505C=16(mod11l)o故(12715C+34)2c=(16+34)20=502G=70(mod111)三、证明题1、已知p是质数，(a,p)=1,证明：当Q为奇数时,apl+(p-l)A=O(modp);当a为偶数时,衣

4、三(modp)。证明：由欧拉定理知右】三1(modp)及(p-1广三-1(modp)立得(1)和(2)成立。2n2、设Q为正奇数，n为正整数，试证a=l(mod2n+2)0.(1)证明设n=2m1,当22=1时，有=2/nI)2=4m(/n1)11(mod23),即原式成立。2*设原式对于n=&成立，则有a1(mod2k+2)a21=1吐,此中qZ,所以er=(1+2)2=1q2+31(mod2i+3),此中q是某个整数。这说明式(1)当n=k1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数，且1k1,而且(力1)!1(modn),则力是素数。证明：假设R是合数，即n=ny1z?

5、!n,由题设易知(m1)!1(modnJ,01(modnJ,矛盾。故n是素数。3、证明：设R表示所有由1构成的s位十进制数，若R是素数，则s也是一个素数。证明：假设s是合数，即s=ab,la,b1是正整数。999由R1也是正整数知。，是合数，这与题设矛盾。故s也是一个素数。4、证明：若2p1是奇素数，则(pl)2(l)y,0(mod2pl)o证明：由威尔逊定理知1(2p)!=p!(p1)(2p)(l)7，(p!)2(mod2p1),由此得(pF(l)p0(mod2pl)o5、设p是大于5的质数，证明：p4l(mod240)o(提示：可由欧拉定理证明)证明：因为24O=23X3X5,所以只要证：

6、p4=l(mod8),p4=l(mod3),p4=l(mod5)即可。事实上，由(8)=4,=2,(5)=4以及欧拉定理立得结论。初等数论练习题三单项选勰1、若nl,(n)=n-l是n为质数的(C)条件。A.必需但非充分条件B充分但非必需条件C.充要条件D.既非充分又非必需条件2、设n是正整数，以下各组去b使殳为既约分数的一组数是(D)oA.a=n+1,b=2n-1B.a=2n-1,b=5n+2C.a=n+l,b=3n+lD.a=3n+1,b=5n+23、使方程A.196x+5y=C不过负整数解的最大整数B.24C.25C是(A)。D.304、不是同余方程28x=21(mod35)的解为(D)

7、。A.x=2(mod35)B.x=7(mod35)C.x=17(mod35)D.x=29(mod35)5、设Q是整数，(l)a=0(mod9)(2)a=2010(mod9)a的十进位表示的各位数字之和可被9整除划去a的十进位表示中所有的数字9,所得的新数被9整除以上各条件中，成为9心的充要条件的共有(C)0A.1个B2个C.3个D.4个二、填空题1、u(2010)=_4896_;(p(2Q10)=528o2、数C亂的标准分解式中，质因数7的指数是_色。3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是9704、同余方程24x=6(mod34)的解是谊三13(mod

8、34)程三30(mod34)_。5、整数nl,且(n?l)!+l三0(modn),则n为素数。6、3回被11除所得余数是7、徑卜。.97丿-一-三、计算题判断(i)2A3A2X0(mod5)能否有三个解；31(ii)A5A230(mod5)能否有六个解?24解：(i)2A3A23x10(mod5)等价于A33A24x30(mod5),又A5x=(A3A24XA2X5)+(Gx2X15),此中33)(312”卅=6A212X15的系数不都是5的倍数，故原方程没有三个解。因为这是对模5的同余方程，故原方程不行能有六个解。2、设n是正整数，求,CM的最大公约数。解：设(c?n,cL，-,C-,)=J

9、,由c；“+q+C釘=2心知d珂设2kn且即2&+11|n,则由27-11|C,及2心IG“，3,5,2/21得d=2k+103、已知Q=18,m=77,求使衣l(modm)成立的最小自然数x。解：因为(18,77)=1,所以有欧拉定理知1877,=l(mod77)0又因为(77)=60,所以x|60，而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30,60。于是x应为此中使181(mod77)成立的最小数，经计算知：x=30o四、证明题1、若质数P5,且2p+l是质数，证明：4p+l必是合数。证明：因为质数p5,所以(3,p)=1,可设p=3k+l或p=3k+2。当p=

10、3k+1时，2p+l=6k+3是合数，与题设矛盾，从而p=3k+2,此时2p+l是形如6k+5的质数，而4p+l=12k+9=3(4k+3)是合数。注:也可设p=6k+r,r=0,1,2,3,4,5。再分类谈论。2、设p、q是两个大于3的质数，证明：p2=q2(mod24)o证明：因为24=3X8,(3,8)=1,所以只要证明:p2=q2(mod3)p2=q2(mod8)同时成立事实上，因为(p,3)=1,(q,3)=1,所以p2=l(mod3),q2=l(mod3),于是p2=q2(mod3),因为p,q都是奇数，所以p2=l(mod8),q2=l(mod8),于是p?三qVmod8)0故p

11、2=q2(mod24)。3、若x,y?R+,证明：xy】Axy;试谈论xy与xy啲大小关系。注：我们知道，氐刃a凶+M,此题把加法换成乘法又如何呢？证明：(1)设x=x+a,Oal,y=y+0,OW0 xy。xy与y之间等于、大于、小于三种关系都有可能出现。当x=y=i时，xy冃衬&=扌；3131当x=y,y=-时，xy=-,xKy=-,此时xyxXy;当x=-i,y=-|时，xy=；,xKy=|,此时xyvxy。23634、证明：存在一个有理数?，此中d100,能使k-L=k21ddL100J对于2,?，99均成立。证明：由(73,100)=1以及裴蜀恒等式可知：存在整数c,d,使得73d-

12、100c=l从而JI-竺(73-呃)=丄由k100可知:100d10010003,证明：6pIx-x0证明：(1)因为2730=2X3X5X7X13,2,3,5,7,13两两互质，所以：由x13-x=x(x12-l)=0(mod2)知：2Ix13-x;13Ix13-x;由x13-x=x(x12-l)=x(x2?1)氐2+1)(云+芒+1)三0(mod3)知：3Ix13-x;由x13124413-x=x(x-1)=x(x-1)(x+x+1)=0(mod5)知：5|x-x;由x13-x=x(x12-1)=x(x6-1)(xc+1)=0(mod7)知：7Ix13-x0故有2730|x13-xo同理可

13、证、(3)、(4)o初等数论练习题五一、单项选择题1、设況、y分别经过模m、n的完整节余系，若(C)经过模nrn的完整节余系。A.m、n都是质数，则mynxBmHn，则mynxC?(m,n)=1,贝ImynxD.(m,n)=1,贝ijmxny2、1X3X5X?X2003X2005X2007X2009X2011标准分解式中11的幕指数是(A)oA.100B.101C.99D.1023、n为正整数，若2匸1为质数，则门是(A)oA.质数B合数C.3D.2k(k为正整数)4、从100到500的自然数中，能被11整除的数的个数是(B)oA.33B.34C.35D.365、模100的最小非负简化节余系中

14、元素的个数是(C)0A.100B.10C.40D.4二、填空题1、同余方程如b三O(modm)有解的充分必需条件是|b。2、高斯称反转定律是数论的酵母，反转定律是指设“与a是不同样的两个奇质数，(-)=(-nTT(-)pq3、20122012被3除所得的余数为_丄_。4、设n是大于2的整数，则(-l)n)=_l_o5、单位圆上的有理点的坐标是住輕.=)或住.二士二)，此中次与b是不全为a-+lr”+b?cr+2r零的整数。6、若3258xa刚巧是一个正整数的平方，则Q的最小值为362。7、已知2011是一素数，则|三J已丄。(2011丿一三、计算题1.求32OOGX72009X132010的个

15、位数字。解:2OOCX(.3)2009X32010三-2003+2009*201032OOSX72OO9X!32010=3=-3C027=-3X(32)3013=3(mod10)c2、求满足(mn)=(山)+S)的互质的正整数m和n的值。解：由(m,n)=1知，(mn)=(ziz)(n)0于是有：(创+(n)=(ziz)(n)设(m)=Q,(n)=b,即有：a+b=abo明显aIb,且bIa,所以Q=b。于是由2a=a2得a=2,即(zzz)=(切=2。故m=3,n=4或m=4，n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，此刻用100元买这三样东西共100斤，问各买几斤？解：设买甲

16、物X斤，乙物y斤，丙物N斤，则5x3y-z=100,3xyz=100o消去勺获取7x4y=100o(1)明显x=0,y=25是方程(1)的解，所以，方程(1)的一般解是x=4/,tZy=25-7t因为x0,y0,所以Ovr3o即r可以取值=1,=t3=3o相应的x、y.n的值是ky,=(4,18,78),(8,11,81),(12,4,84)。四、证明题1、已知2011是质数，则有2011199-Jo2010个证明：999=102O11-1=0(mod2011)02010个设p是4n+l型的质数，证明若a是p的平方节余，则p%也是p的平方节余。证明：因为质数p=4n+l,Q是p的平方节余，所以

17、、(PI/、a=一a=-=(-!)-(P0的整数解是且仅是x=2虻，y=a2叽z=WZA此中方0,(7=1,占与乃有不一样的奇偶性。6、21x=9(mod43)的解是x三25(mod43)。7、73=-lo1991、将存写成三个既约分数之和，它们的分母分别是=+即35*3,5和7。解：设iI57?21y15z=17,因(35,21)=7,(7,15)=1,17,故有解。分别解5x3y=t7t15=17N3n,y=2t5n,uZ,t=1115r,z=47r,rZ,11y=2230r5u,w,vZo174-X3令“0,心1得釦X=4,y=-8,歹3。即：丽行+了+宁2、若3是质数p的平方节余，问p

18、是什么形式的质数?”一|解：?由二次互反律&卜i宁尉3注意到p3,p只好为p三土l(mod3)且Iy三p三l(mod4)p=-l(mod4)=1只好以下情况|p=l(mod3)|p=l(mod4)三-l(mod3)p=-l(mod4)?.p=l(mod12)或p三-l(mod!2)03、判断不定方程疋+23尸17能否有解?解：只要判断疋三17(mod23)能否有解即可。17=1(mod4)总卜信卜脩卜闫信卜G=一卜1俘卜(I)?疋三17(mod23)无解，即原方程无解。三、论证题1、试证对任何实数兀恒有X+X+i=2x证明：设X=x+(7,O(71当03时，x+*,2x=2x.?.等式成立当l

19、a0,n0,且m为奇数，证明：(2m-l,2n+l)=lo证明一：由m为奇数可知：2n+l|2lun+l,又有2山-1|2-1,于是存在整数x,y使得：(2n+l)x=2um+l,(2m-l)y=2nm-lo从而(2n+l)x-(2m-l)y=2o这表示:(2m-l,2n+l)|2因为2n+l,2也1均为奇数可知：(2m-l,2n+l)=lo证明二：设(2ra-l,2n+l)=d,则存在s,t?Z,使2m=sd+l,2n=td-lo由此获取:2lnn=(sd+l)n,2nm=(td-l)m于是2mn=p+,p,q?Z。所以：(q-p)d=2o从而d2f就有=1或2。由因为m为奇数，所以d=l0

20、即(2m-l,2n+l)=lo注：我们已证过：记Mn=2n1,对于正整数勺b,有(必，胚)=明显当ab,lb为质数时，(胚，胚)=1。初等数论练习题七一、单项选择题1、设2和b是正整数，则(凹!.!)=(A)abA.1E?QC.bD?(比b)2、176至545的正整数中，13的倍数的个数是(B)A?27B.28C.29D?303、200!中末端接踵的0的个数是(A)A.49B.50C.51D.52从以下满足规定要求的整数中，能选取出模20的简化节余系的是(B)A.2的倍数B.3的倍数C.4的倍数D.5的倍数设n是正整数，以下选项为既约分数的是(A)A.岂凹.上也心D.出BC.5n+23/1+1

21、4/7+32n-1二、填空题11、314心被163除的余数是丄_。(欧拉定理)2、同余方程3x=5(modl3)的解是x三5(modl3)。3、(亜)=1。1847-4、-K=-4。5、为使n-1与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+l,k?Z。6、假如一个正整数拥有21个正因数，问这个正整数最小是2叹32=576。7、同余方程x3+x2-x-1=0(mod3)的解是x三l,2(mod3)。三.计算题4求不定方程*2y3z=41的所有正整数解。解：分别解X2y=tt3z=41得x=t2uy=uut=413vZ=VV消去得x=413v2az=Vu9VZo由此得原方程的所

22、有正整数解为(x,y,-g)=(413v2u,q功，u0,r0,413v2u0o2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超出170人，问这队士兵有几人？解：设士兵有*人，由题意得*1(mod3),x2(mod5),x3(modll)o在子定理中，取-W21=3,in2=5,=11,in=3511=165,M=55,M2=33,M3=15,M=1,M2=2,M3=3,则x1551(-2)332315358(mod165),所以所求的整数*=52+165。tZo因为这队士兵不超出170人，所以这队士兵有58人。23、判断同余方程%=286(

23、mod443)能否有解P解:286=2X143,433是质数，(143,443)=1奇数143不是质数，但可用判断雅可比符号计算的勒让德符号286卜7、143443(估143-1=(-!)?原方程有四、证明题1、设(a,in)=1,&是使/1(modzz2)成立的最小正整数，则(ii)对于随便的A/,0d1,iy,有(mod122)0(1)证明：(i)由Euler定理,(山)，所以，由带余数除法，有(山)=qdoZ,Q0,0r所以，由上式及况的定义，利用欧拉定理获取1&旳)=/?严三(modm),lZ2)o即整数厂满足/1(modw),0rJo因为(角山)=1,所以70(modzn),0/j1

24、,(Z?,in)=1,而且bA1(modzn),bc1(modin)(1)记(迭d,则Z/1(modm)o证明：由裴蜀恒等式知，存在整数，y,使得应cy=d,明显刃0,y0,由式知：1bdb纱=ybd(modnio若x0,由式(1)知：1bcy=bdbbd(lf(modzz2)03、设p是素数，p厅1,nN,则下边的两个结论中最少有一个成立：(1)Pbd1对于力的某个因数d2,则(ii冲的mod力可以改为mod2/2o证明：记d=(n,p1),由，1,1(modp),及第2题有bd1(modp)o若d2,则p1(mod2)o由此及结论(ii),并利用同余的基天性质,获取Z?1(mod2n)o初

25、等数论练习题八一、单项选择题1、设n1,则n为素数是(a1)11(modn)的(C)。A?必需但非充分条件B充分但非必需条件C.充要条件D.既非充分又非必需条件2、小于545的正整数中，15的倍数的个数是(C)A.34B.35C.36D.373.500!的标准分解式中7的無指数是(D)A.79B.80C.81D.824、以下各组数中，成为模10的简化节余系的是(D)A.1,9,-3,-1B.1,-1,7,9C.5,7,11,13D.-l,l,-3,35、设n是正整数，以下选项为既约分数的是(A)A业B.JULcdD.JUL5n+22n-15n+23n+1二.填空题1o(120)=36Oo2、7

26、355的个位数字是3。3、同余方程3x=5(modl4)的解是x三1l(modl4)。4、()=1023-5、-206、假如一个正整数拥有6个正因数，问这个正整数最小是旦7、同余方程x3+x2-x-l=0(mod5)的解是x三土1(mod5)。1、429解：把右淆成Jacobi符号,我们有4294冲5641H訓)429?_167、=(一1)2伽韵侣=(-!)42956367-1429-127-167-1；6727)丫=(1)22429/厲零(67)(67)42927、已知563是素数，判断方程芒67429(mod563)能否有解。13故方程x2429(mod563)有解。2、求出模23的所有的

27、二次节余和二次非节余。解：模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.试求出所有正整数n，使得1“+2“+3彰“+能被5整除。解：若n为奇数，则ln+2n+3n+4nln+2n+(-2)+(-1)n0(mod5);若n=2m,m?Z,贝ij1”+2+3”+4“1加+2加+(-2)加+(-1)加2+2X2加=2+2X4山=2+2X(-l)“(mod5);当m为奇数时，1+2”+3”+4O(mod”5);当m为偶数时，121”21+2+3+44

28、(mod5)o故当4jn时，5Iln+2n+321+4n。四、证明题1、证明：若质数P2,则茁-1的质因数必定是2pk+l形。证明：设q是2。-1的质因数，因为2-1为奇数，歼2,(2,q)=1。由条件q|2P-1,即2三1(modg)。设方是使得2三1(modq)成立最小正整数，若lhpf则有方|p这与p为质数矛盾。从而h=p,于是p|q-l0又Tg-1为偶数，2|q-l,2p|Q-1,q-l=2pk,即&?Z2、设(m,n)=1,证明：in1,马上获取d|次和d|b,这与(a,b)=1矛盾。)干是(d,尸)=1。故dp9即或卫。初等数论练习题九一.单项选择题1.以下Legendre符号等于

29、-1的30被-1是(D)A.B.D.6E丿2、100至500的正整数中，能被17整除的个数是(A.23B.24C.25D.263、设3a|500!,但3曲/500!，则a=(A.245B.246C.247D.2484、以下数组中，成为模7的完整节余系的是(CA.-14,-4,0,5,15,18,19B.7,10,14,19,25,32,40C.4,2,8,13,32,35,135D?一3,3,4,4,5,5,05、设力是正整数，则以下各式中必定成立的是(B)A.(n+1,3n+l)=lB(2nl,2n+l)=1C?(2zz,n+1)=1D?(2n+l,n-1)=1二、填空题1、25730被50

30、除的余数是2、同余方程3j5(modl6)的解是灼7(mod16)。3、不定方程9x-12尸15的通解是木+41,y=-2+3F,tZ。4、单=loI41J5、实数的小数部分记为卅，则2=0.75。4-6、为使3力与4n+1的最大公因数达到最大可能值，整数n应满足条件科3,k?Z。7、假如一个正整数拥有35个正因数，问这个正整数最小是20X3-5184。三、计算题1、解不定方程9x+24y-5=lOOOo解：解因(9,24)=3,(3,-5)=1知原方程有解c原方程化为9x24jz=3厶3x8y=ty(1)3t-5z=10003t-5z=1000,t=5u解得Z=一200+3ii?ATI*4再

31、解8y=5u获取,u,rZoy=i4一3vx=-H+8v故y=-3v,uyvZoZ=-200+3M2、设力=蜀，也是模加的一个完整系,以乂表示*的小数部分，若(%Z22)=盖，1,求护解：当”经过模山的完整节余系时，axb也经过模山的完整节余系，所以对于任意的i（1iin）,6定与且只与某个整数/（1j山）同余，即存在整数&使得啓b=kinj、（0jn2-l）o从而：I0m気IfJ,n3、设整数n2,求：工即在数列1,2,/2中，与n互素的整数之和。lin（5=1解：设在1,2，中与n互素的（切个数是角，怂，、耳（勺n）=1,11,（zzz）=1,系,求：壬竺。此中佃表示“的小数部分。（/是同

32、样的，于是（力a（，M=n（22）。x仙）是模in的简化节余/-Im解：设RXi=mqi昭0r,iny由疋经过模山的简化节余系知：咎也经过模山的简化节余系，从而厂经过模加的最小非负简化节余系，于是:（2/7mp（in=四、证明题0（?）o?1、证明：设Q是有理数，b是使ba为整数的最小正整数，若c和CR都是整数，则bICo（提示：利用带余数除法解决。）证明：c=bq+r,0r2时，欧拉函数（刃必定是（B)oA.奇数C.1D.2二、填空题1、假如P是质数，忍是整数，则有3,p）=1也许plH2、设p是奇质数,（Q,p）=l,则2是模p的平方非节余的充要条件是訐三-l（modp）3、从1000开始

33、到2010结束的所有整数中13的倍数有坐个。4、2750539-1的末位数是d5、不定方程ax+by=c有解的充要条件是（紀，?c。6、写出模12的一个最小非负简化系，要求每项都是7的倍数，此简化系为7,35,49,777、已知563是质数，则1563丿三.计算题1、若3是质数p的平方节余，问p是什么形式的质数?解:由二次互反律只好是以下状况Si(mod3)注意到p3,p只好为p=土l(mod/?=l(mod4)p=l(mod3)p=_l(mod3)p?=-I(mod3)三-l(mod4)?.p=l(modl2)或p三-l(mod12)0求使12347!被35*整除的最大的R值。解：k=2054.四、证明题1、证明：设P7是一个质数，则存在独一的一个正整数小使得:xe1,2,?一1且120(p-6)!+x=0(modp)证明：存在性：因为P7是一个素