初等数论试题库

1、初等数论一、填空741、d (1000) = 。小(1000) =。 (101 )= 02、ax+bY=c有解的充要条件是。2002.3、2002 被3除后余数为一。4、X=3 , Y=4 , Z=2 ,则X 2Y+3Z可能的值为 。5、小(1) + 小(P) + 小(Pn) =。6、高斯互反律是7、两个素数的和为31,则这两个素数是 。8、带余除法定理是 。9、d (37) = 。 (T (37) =。10、小(1) + 小(P) + 小(Pn) =。11、不能表示成5X+3Y (X、Y非负)的最大整数为 。12、7在2004!中的最高幕指数是 。13、(1501 , 300) = 。14、

2、ax b(m0dm)有解的充要条件是 015、威尔逊定理是。16、写出6的一个绝对值最小的简化系 。888 88 666 6617、5050 被7除后的余数为。18、d (31) = 。(3600) =。19、四位数3AA1被9整除，则A=。20、 17X+2Y=3 通解为。21、费尔马大定理是。22、写出12的一个简化系，要求每项都是5的倍数。23、2.4 = 024、0.428571化为分数是。25、15!的标准分解是 。26、1000到2003的所有整数中13的倍数有 个。27、(29) =.28、不能表示成5x 4y(x,y为非负整数)的最大整数为 一.29、7在2008!的标准分解式

3、中的最高幕指数是 .30、2005和2006的最小公倍数是 一.31、威尔逊定理是32、设x 1为整数且被4、5、7除后的余数都为3,则最小的x是.33、已知(a, b) =1,贝U (5a+3b, 13a+8b) =.34、1, 4, 9, 16, 1000(® 100个平方数中是3的倍数的平方数有 个.35、若今天是星期日，则1010天后的那一天是星期 .36、32005的末二位数是.37、d (1200) = 。38、梅森数Mn是素数，则n是。39、不能表示成7X+6Y (X、Y非负)的最大整数为。40、1 X3X5X7X 1999X2001的标准分解中13的幕指数是。41、(

4、13a+21b , 34a+55b) = 。已知(a , b) =1。42、费尔马猜想是。43、写出12的一个简化系，要求每项都是7的倍数。44、aX.= b (mod m)有解的充要条件是 。45、20022002被3除后余数为。46、X=3 , Y=4 , Z=2 ,则X 2Y+Z可能的值为。47、d (1000) = 。 (T (1000) =。小(1000) =48、n 若" 1) 1 030d 必则口 为o49、不能表示成5X+3Y (X、Y非负)的最大整数为 。50、7在2003!中的最高幕指数是 。51、(1515 , 600) = 。52、ax "mod m

5、)有解的充要条件是 053、威尔逊定理是。54、写出6的一个简化系，要求每项都是5的倍数。55、2 2003的末位数是 。56、-2.3= 。57、小(1) + 小(P) + 小(Pn) =。58、x 1且能被4、5、7整除，则最小的x是069、两个素数的和为31,则这两个素数是。60、带余除法定理是。61、d (1001) = 。 (T ( 2002) =62、a1x1 a2x2 .anxn C有解的充要条件是 一。63、不能表示成5X+6Y(X、Y非负)的最大整数为 。64、2003!中末尾连续有 个零。65、(21a+4, 14a+3) =。66、两个素数的和是39,这两个素数是。67、

6、从1001到2000的所有整数中，13的倍数有。68、p,q是小于是100的素数，pq- 1=x为奇数，则x的最大值是69、n>1,若(门1)! 1 030d 切则口 为o70、7在2003!中的最高幕指数是 。71、(1515 , 600) = 。72、ax "mod m)有解时有个解。73、0.32化为分数是。74、-0.3= 。4>888 8875、50 被7除后的余数为。答案1、2、3、4、5、16. 2340, 1(a, b) |c110, 113, 4, 5, 6, 7, 8, 9,npp 1q 16、（9）（ 1）"2"（_p） , p,

7、 q 为奇素数 pq7、 2, 298、a, b是两个整数，b>0,则存在两个惟一的整数q, r使得a bq r，0 r b 9、 2, 38 n10、p11、712、 33113、114、 (a,m)|b15、P为素数，(p 1)! 1 0(m0d p)16、 1, 517、518、2, 1249319、720、x 1 2t,y 2 17t,t Z n n n21、x y z(n 3)无正整数解22、 5, 25, 35, 5523、 0. 6324、725、211 36 53 72 11 1326、7827、3028、1129、 33530、 402203031、P为素数，则有(p

8、1)! 1 0(mod p)32、14333、134、3335四36 4337 24，38素数39 2940 8341 142 xn yn zn (n 3) 无正整数解43 7， 35， 49， 7744(a,m) |b45 146 -5， -4， -3， -247 16， 2340， 936048素数49 750 33151 1552(a,m) | b53( p 1)! 1 0(mod p)54 5， 2555 856 -3 n57 p58 14059 2， 2960、a, b是两个整数，b>0,则存在两个惟一的整数q, r使得a bq r，0 r61 6， 403262(a1,a2,

9、.an) |c63 1964 49965 166 2， 3767 7768 19369素数70 3171 1572(a,m)73、74、75、2990-14、解同余方程组x 2(mod 12)1、 x 6(mod 10) 3x 1(mod 15)2、x 3(mod4)3、 x 2(mod5)x 6(mod7)x 1(mod7)5、x 2(mod 8)x 3(mod 9)x 1(mod4)6、 x 1(mod5)x 5 2 mod 7)4、7、x 2(mod5)x 3(mod8)x 1(mod7)x3(mod 5)x 5(mod8)x 1(mod7)x 2(mod5)x 3(mod 8)x 6(

10、mod9)答案(12, 15) |1- (-2)(1)解：因为(12, 10) |6- (-2), (10, 15) |6-1, 所以同余式组有解x2(mod 4)x2(mod 3)x 6(mod 2)x 6(mod 5)x 1(mod 3)原方程等价于方程x 1 (mod 5)x 2(mod4)x2(mod 3)即 x 1(mod5)由孙子定理得x 46(mod 60)(2)解：因为5,7,8两两互素，所以可以利用孙子定理.M156, M 235, M340, m 2803解同余式56M 1, 1(mod 5) 35M 2, 1(mod 8) 40M3, 1(mod 7) ,得到 M 1,1

11、,M ,23,M ,33.于是所求的解为x 56 1 2 35 3 3 40 3 1(mod140)267(mod280)所以 x 267(mod 280).( 3)证：因为4,5,7 两两互素 , 所以可以利用孙子定理求解.M 135, M 228, M 320, m 140.解同余式35M 1, 1(mod4), 28M 2, 1(mod 5) , 20M 3,1(mod 7),得到 M1,1,M ,2 2,M ,31 .于是所求的解为x 35 ( 1) 3 28 2 2 20 ( 1) 6(mod 140)97(mod 140)( 4)解：因为 5, 8, 7 两两互素, 所以有解利用孙

12、子定理求得M 156, M 2 35, M 3 40. m 280解同余方程56M1, 1(mod 5) , 35M 2,1(mod 8), 40M3, 1(mod 7) , 得到M 1, 1,M ,2 3, M ,3 3 .于是所求的解为x 56 1 ( 3) 35 3 ( 5) 40 3 1(mod 280)得 x 267(mod280).( 5)解因为 7,8,9 两两互素 , 所以可以利用孙子定理.M 172,M 263, M 356,m 494解同余式72M1, 1(mod 7) , 63M 2, 1(mod 8), 56M 3,1(mod 9) ,得到 M 1, 4,M ,21,M

13、 ,34 . 于是所求的解为( 6)解：因为4,5,7 两两互素 , 所以可以利用孙子定理求解1(mod 4)1(mod5)原方程即为M 135, M 2解同余式28, M 3 20, m 1403mod7)35M 1, 1(mod4), 28M 2, 1(mod 5) , 20M 3, 1(mod 7)得到 M；1,M ,22,M ,31 .于是所求的解为x 35 ( 1) 1 28 2 1 20 ( 1) ( 3)(mod140) 81(mod 280)所以 x 81(mod140).(7)解：因为5, 8, 9 两两互素,所以有解利用孙子定理求得M172 M 2 45，M 3 40. m

14、 360解同余方程 72M1, 1(mod 5), 45M 2 1(mod 8), 40M 3 1(mod9), 得到M1,3, M ,25，M ,32.于是所求的解为x 72 3 2 45 3 5 40 ( 2) ( 6)(mod 360)得 x 147(mod 360).三、证明(1) A、叙述威尔逊定理。B,证明若(m 1)! 1 0(m0dm)，则m为素数(2)证明当n是奇数时，有3(2n 1).(3)叙述并且证明欧拉定理。(4)解同余方程17x 2(mod 25)(5)叙述并且证明带余除法定理。(6)叙述并且证明费尔马小定理。(7)证明：若m砌则当k通过模播的完全剩余系时，则 会+七

15、也通过模相的完全剩余系.答案(1) A.(威尔逊定理)整数9是素数，则(HI五7觥则证：若 m不是素数，则 m=ab 1abm，则 a|(m 1)!,a|(m 1)1,则有 a|1 不可能，所以m是素数。 证明：因为21(m0d 3),所以2n 1 ( 1)n 1(mod 3)于是，当n是奇数时，我们可以令n 2k 1. 从而有 2n 1 （ 1）2k1 1 0（mod3）,即 3（2n 1）.（3）欧拉定理）若则明13、证明：设 生火玛却是模 陶的一组互素剩余系.二（%.）=1由§ 2.2定理知徵1，期,，与你）是模m的一组 互素剩余系.叼”。/叫XmQd啕即产*也-讨网）又: a

16、i 。三12仍（阿），©骨尸陶e.1.，做'三 l（mod题） 解：因为（17, 25） =1,所以同余方程17x230d 25）有一解（5）带余除法定理：，出咯且上。，则也昨贪使得"酎"尸（0"<与成立，并且中产是惟一的.证明：（存在性）作整数序列：3瓦-2瓦一瓦。，瓦瓦,3&对于就必存在一个整数才使得华小9+i）b成立令厂“一的即"班+七.<&r的惟一性）：若明$曰名使得广阻飞a- bq- r - bq., 6（0一外）.个一尸q-=rL-r,1,0 4 h -小 方'.1.0 & q -

17、 gj< 1又7名b-媚口即从而有“ ="一久是惟一的.（6）费尔马定理：对任意的素数p有aP a（m0d P）证明：设 p|a,则有 Plap,有 ap a（m0d P）,若（a, p） =1,由欧拉定理有aP1（m0d p）两边同乘a即有 证明：当K通过模 脸的完全剩余系 的色时，令4三口马十B 1三掰则，一一一，否则，八刑10使得占广药的那陶)，即鼻4小二口%十方(mod制)aat =«(modp«)又二.,. I 1、一 ',)这与冬，是模 脸的一组完全剩余系矛盾.:瓦同也构成模一的完全剩余系.即五十B也通过模酒的完全剩余系四、综合应用(1)

18、解方程 x4 7x 4m0 (mod 2 7)(10分)解：由 x4 7x 4 三0 (mod3)彳3 x 130d 3)得 x=1+3t 代入x4 7x 4=0 ( mod9)有 11t1(m0d 3)有 t 1 3t1代入 x=1+3t 得x 4 9ti代入 x4 7x 4 =0 (mod27)有 ti 2(mod 3) ti 2 3t2代入有x 22 27t2即 x 22(mod 27)(2)设 2P+1 为素数试证(P!)2 ( 1)P 0(mod 2 P 1) (10 分)答案证：因n=2P+1为素数，由威尔逊定理(nn1 0(modn”ht(n 1)! 1 (n 1)(n 2) 3

19、 2 1 1 (n 1) 2 (n 2) p(n p) 1(mod n)(p!)2( 1)P 1 0(mod 2p 1)即证P(3)设P=4n+3是素数，证明当q=2p+1也是素数时，梅森数M p 21不是素数。(10分)答案2(一)1(mod q)证：因q=8n+7,由性质2是q=8n+7的平方剩余，q即94n 3q|24n3 1P所以梅森数M P 21 不是素数。333( 4)证x 3y 9z 无正整数解。( 8分)答案333证：假设x3y9z有解，设(x, y, z)是一组正整数解，则有x是3的倍333数，设x=3xi,又得到y为3的倍数，设y 3yi,又有z 34，xi 3yi9zi则

20、有解(x1 , y1 ,z1) 且 z>z1这样可以一直进行下去， Z>Z1>Z2> Z3>Z4>-但是自然数无穷递降是不可能的，于是产生了矛盾( 5)设n 是大于 2的整数，证明(n) 为偶数(10 分)答案证：因为(-1， n) =1，由欧拉定理有( 1) (n) 1(mod n) ，因为 n 大于2，只有(n) 为偶数。(6)如果整系数的二次三项式P(x) x2 bx c当x 0，1时的值都是奇数，证明p(x) 0没有整数根(8分)答案 :证：由条件可得c 为奇数， b 为偶数2如果p (x) =0有根q,右q为偶数，则有qbq c为奇数，而p (q)

21、 =0为偶2数，不可能，若q为奇数，则有qbq c为奇数，而p (q) =0为偶数，也不可能，所以p(x) 0没有整数根( 7)解方程45x 21(mod132) .( 10分)答案 :解 因为 (45,132)=3|21, 所以同余式有3个解 .将同余式化简为等价的同余方程15x 7(mod44) . 我们再解不定方程15x 44y 7 , 得到一解(21,7).因此同余式的3 个解为x 21(mod 132)10132x 21 (mod132) 65(mod132)3,132x 21 2 (mod132) 109(mod132)3(8)证明：用算术基本定理证明 J百是无理数。(10分)答案

22、：P证：假设43是有理数，则存在二个正整数 p, q,使得V3= q ,由对数定义可 22 .一 .得有3q = p，则同一个数左边含奇数个因子，右边含偶数个因子，与算术基本 定理矛盾。内为无理数。(9)、证明：对任何正整数n ，若n不能被4整除，则有511n 2n 3n 4n (10 分)答案：证：则题意知 n=4q+r, r=1, 2, 3。因为。=1,i=1,2,3,4所以有1 (mod 5)当 r=1 时有 1 2 3 4 0(mod 5)当 r=2 时有 12 22 32 42 0(mod 5)当 r=3 时有 13 23 33 43 0(mod 5)从而证明了结论。(10)、解不定

23、方程4x 5y 10(10分)答案：x=0, y=2 x 5t, y 2 4t,t Z(10 分)=1,所以同余式有解。3(mod11)解：因为(4, 5) =1,所以方程有解，由观察得有特解所以方程的解为(11)8x 9(mod 11)答案解：因为(8, 11) 由形式分数有99x -8 8 1111P ,(12)证明梅森数Mp 21的素因子q p. (io分)答案证：设q是2 p-1的质因数，由于2 p-1为奇数， qw2, (2, q) =1,由条件 q|2p-1,即 2 p =1 (modq)又丁 (q,2) =1, 2 P m1 (mod q)设i是使得2 xm1 (mod p)成立

24、最小正整数若1<i<p,则有i|p则与p为素数矛盾i=p, p|q-1,从而证明了结论。(13)试证若p 2,5且是素数，则p99 9p 1（9分）答案证：因为p 2,5且是素数所以(p, 10) =1,由欧拉定理有 p 110 1(mod p) ,从而有p99 9p 1(14)证明：对任何的正整数 a, 5a+2不可能是平方数(9分)答案证：因为平方数被5除后的余数为1, 4,而5a+2被5除后的余数为2,2不同余1, 4关于5,所以不相等2(15)判断方程xm3 (mod 8 3)是否有解，右有解则有几解(答案加(旦)1解：因为83,所以有解，由性质知有解就有两解。2(16).

25、求4x xy 3 0的整数解.(10分)答案8分）12y 4x 解：因为x 0,所以x,因为y为整数，所以X只能取-1,-3,1,3X1 1x21从而原方程的解为y1 1,y21,x33y311x4V43112(17) .判断同余万程xm73(mod137)是否有解，若有解，有几解.(8分)答案73 ()12解：因为137,所以同余万程x三73(mod137)有解由定理有解则有两解。22(18) .证明：不存在整数x，y使等式x y =1995成立.(10分)答案证：假设有整数x, y存在，使x2+y2=1995成立。x2, y2被4除余数为0或1 .；x2 + y2被4除余数为0 , 1或2

26、 .又; 1995被4除余数为3 .得出矛盾，假设不成立.故没有整数x, y存在，使x2+y2= 1995成立.(19) .设 721a673b,试求 a, b 的化 (10 分)答案解 72 =8X9,且(8, 9)=1. 8| a673b ,且 9| a673b8| 73b b=6且 9|a +6+7+3 + 6即9|22 +a,即a=5,所以a=5, b=6(20) .用1, 2,ooo 8, 9不重复地写出被11整除最大的九位数(10分)答案13因为被11整除的数的特征是奇数位数码之和减去偶数位数码之和为11的倍数,要写最大的九位数，前面可用98765,然后对后面的数字进行调整，此时奇

27、数位数码和比偶数位数码之和大7,只要后面最大4或小7即可，小卖7不行，只能大4,刚好4,3之和比1,2之和大4,为 了最大，后4位为2413,所以所求数为987652413.2(21)解万程 x 2x 2 m0 (mod 12 5) (10 分)答案解：由 x2 2x 2 m0 (mod5)彳# x 12mod5)x 1(mod 5) 得 x=1+5t 代入x2 2x 2 = 0 (mod25)有 4t 1(mod5)有 t 1 5t1 代入 x=1+5t 得x 6 25t1代入 x2 2x 2=0 (mod125)有 14t12(mod 5) t1 2 5t2 代入有x 56 125t 2,

28、 x 56(mod125),同理另一解为x 67(mod125)(22)设P为素数，试证对任整数a ,都有P |(P1)! aP+a。(10分)答案证：由威尔逊定理(p 1)! 1(mod p)由欧拉定理ap a(mod P),两式相乘即得 p (p 1)! a a(mod p) II ，P即有P | (P 1 ) ! a +a(23)证明不定方程x2-2xy2+5z+3=0无整数解答案证:若不定方程有解，则x y2 'y4 5z 3但 y4m0, 1(mod5), 对 y,zy4-5z-3三 2, 3(mod5)而一个平方数三0,1,4 (mod 5)y4-5z-3不可能为完全平方，

29、即 .4也3不是整数,所以原不定方程无解。14P ,(24)证明梅森数Mp 21的素因子q一定为2 p t + 1型。(p>2为素数)。(10 分)答案证：设q是2 p-1的质因数，由于2 p-1为奇数， qw2,. (2q) =1,由条件 q12P-1,即 2 P 三1 (mod q)又丁 (q,2) =1, 2 P m1 (mod q)设i是使得2 xm1 (mod p)成立最小正整数若1<i<P,则有i|P则与P为素数矛盾i=P, P|q-1又二 q-1为偶数，2q-1, 2P|q-1,q-1=2Pk,即 q=2Pk+1(25)证明形如4m+1的素数有无穷多个(10分)

30、答案证：假设形如4m+1的素数只有有限个，设为P1Pk,显然(2P1 Pk)2+1的最小素因数p是奇数，且p与P1Pk不同，设p为4m+3 形的素数，但p整除(2p1 pk)2+1,表明(2p1 pk)2+1m0 (mod p)1 E22 1 一 ( 1) 2( 1产1即x三(-1)(mod P)有解，即p ，但 p矛盾，；p为4m+1形，这与4m+1的素数只有k个矛盾。(26)如果整系数的二次三项式P(x) x2 bx c当x 01 时的值都是奇数，证明 P(x) 0没有整数根(6分)答案证：由条件可得c为奇数，b为偶数如果p (x) =0有根q,若q为偶数，则有q bq c为奇数，而p (

31、q) =0 2为偶数，不可能，若q为奇数，则有q bq c为奇数，而p (q) =0为偶 数，也不可能，所以p(x) 0没有整数根(27)设P为奇素数，则有(8分)(1) 1p 1 2P 1 (p 1)p1 1(mod p)(2) 1p 2P (p 1)P 0(mod p)15答案 证：由欧拉定理1P 12P 1(p1)p1111 p1 1(modp)由费尔马定理1P 12P 1(p1)p112p 10(mod p)(28)证明：对任何正整数k, m, n5k 24 5m 4 八5n 3,有 11|543(6 分)答案 证：(5, 11) =1, (4, 11) =1, (3, 11) =1

32、由欧拉定理得10-101051(mod11), 310 1(mod11), 4 1(mod 11),进一步有5. 555 1(mod 11)3 1(mod 11)41(mod11)对任何正整数k, m, n有5k 2 5m 4 o5n 324 c35435430(mod11)即有5k 2, 5m 4-5n 31 1 | 543(29)证明： 内是无理数。(8分)答案 证：假设 出是有理数，则存在自数数a,b使得满足x2 3y2即a2 3b22 2知道a是3的倍数，设a=3a1，代入得b3a1 ,又得到b为3的倍数，a122设 b 3b1,则 a13b1 ,这里 b2 a1这样可以进一步求得 a

33、2, b2且有 a>b>a1>b1> a2>b2>但是自然数无穷递降是不可能的，于是产生了矛盾，几为无理数.、 2（30）试证：对任何的正整数n,n 2不能被4整除。（6分）答案 证：n=2k时有n2 2= 4k2 2 ,不能被4整除当n=2k+1时有n2 2= 4k2 4k 3,不能被4整除所以有2 八对任何的正整数n，n 2不能被4整除（31）解不定方程4x 5y 10（6分）16答案解：因为(4, 5) =1,所以不定方程有解，由观察得有特解x 0 5t所以不定方程的解为y 2 4t t为整数x=0, y=5(32)明：设d是自然数n的正因子，则有d n2d|n答案1 d(n)(10 分)证：设d是n的因子，则d也是n的因子，而n的因子数为1n2 d (n)2d( d) nd n2所以ddln d ,所以dn即有dnd (n)(33) P为奇素数，则有(10分)a p b p (a b)p(mod p)答案证：由费尔马小定理知对一切整数有apa (p)bhb(P),由同余性质知有ap+bp=a+b( p