初等数论练习题答案

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(mod 37)的解是 x三 11 (mod 37)。5、不定方程 18x-23y=100 的通解是 x=900+23t, y=700+18t t Z。.6、分母是正整数m的既约真分数的个数为(山)_。7、18100被172除的余数是_殛。9、若p是素数，则同余方程L 1 l(modp)的解数为p-1。二、计算题1、解同余方程：3疋 11X 200 (mod l

2、O5)o解：因105 =3 57,同余方程3x211X200 (mod 3)的解为x1 (mod 3),同余方程3x211X380 (mod 5)的解为x0, 3 (mod 5),同余方程3x211X200 (mod 7啲解为x2, 6 (mod 7),故原同余方程有4解。作同余方程组：x (mod 3), x b2 (mod 5), x b3 (mod 7),其中 =1, b2 = 0, 3, b3 = 2, 6,由子定理得原同余方程的解为x13, 55, 58, 100 (mod 105)o2. 判断同余方程/三42(mod 107)是否有解?42*3x7237107)=(二)(一)(-)

3、107107107107=(一1)呼(凹107723I。，2v( ) = -1,( ) = (-1) 22 (ArL) = -) = L10710733.-.() = 1107故同余方程x2三42(mod 107)有解。3、求(12715C+34) 23除以ill的最小非负余数。解：易知 1271 = 50 (mod 111)0由 502 =58 (mod 111) , 503 三58X50三 14 (mod 111), 509=143=80 (mod111)知 502G = (509)彳x50三803X50三803x50三68x50三70 (mod 111) 从而 505C =16 (mod

4、 11 l)o故(12715C+34) 2c= (16+34) 20 =502G=70 (mod 111)三、证明题1、已知p是质数，(a,p) =1,证明：(1) 当 Q 为奇数时,ap l+(p-l)A=O (mod p);(2) 当a为偶数时,衣三(mod p)。证明：由欧拉定理知右】三1 (mod p)及(p-1广三-1 (mod p)立得(1)和(2)成立。2n2、设Q为正奇数，n为正整数，试证a =l(mod 2n+2)0 (1)证明设n = 2m 1,当22=1时，有= 2/nI)2 = 4m(/n1)11 (mod 23),即原式成立。2*设原式对于n = &成立，则有 a 1

5、 (mod 2k+2)a21 = 1 吐,其中 q Z,所以 er = (1+2)2= 1 q 2+31 (mod 2i+3),其中q 是某个整数。这说明式(1)当n = k 1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数，且1 k 1,并且(力1)!证明：假设R是合数，即n = ny 1 z?! n,由题设易知(m 1)!1 (mod nJ,01 (mod nJ,矛盾。故n是素数。3、证明：设R表示全部由1组成的s位十进制数，若R是素数，则s也是一个素数。 证明：假设s是合数，即s=ab, la, b1是正整数。999由R1也是正整数知。，是合数，这与题设矛盾。故s也是一个素

6、数。4、证明：若 2p 1 是奇素数，则(pl)2( l)y, 0 (mod 2p l)o证明：由威尔逊定理知 1(2p)!=p!(p1) (2p)( l)7，(p!)2(mod 2p1),由此得(pF ( l)p 0 (mod 2p l)o5、设p是大于5的质数，证明：p4l(mod 240)o (提示：可由欧拉定理证明)证明：因为 24O=23X3X5,所以只需证：p4=l(mod 8), p4=l(mod 3), p4=l(mod5)即可。事实上，由(8)=4,=2,(5)=4以及欧拉定理立得结论。初等数论练习题三f单项选勰1、若nl, (n)=n-l是n为质数的(C )条件。A.必要但

7、非充分条件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、使方程6x+5y=C无非负整数解的最大整数C是(A )。A.19B.24C.25D.304、不是同余方程28x=21(mod 35)的解为(D )。A.x=2(mod 35) B. x=7(mod 35) C. x=17(mod 35) D. x=29(mod 35)5、设 Q 是整数，(l)a=0(mod9)(2)a=2010(mod9)(3

8、) a的十进位表示的各位数字之和可被9整除(4) 划去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(mod34)程三30(mod34)_。5、整数nl,且(nl)!+l三0(modn),则n为素数。6、3回被11除所得余数是7、徑卜。【.97丿-一-三、

9、计算题判定(i) 2a3 a2 3x 10 (mod 5)是否有三个解；(ii)2a54a2 30 (mod 5)是否有六个解?解：(i ) 2a3 a23x10 (mod 5)等价于 A3 3a24x 30 (mod5),又a5 x= (a33a24x 3)(a2 3x 5) + (Gx212x15),其中”卅=6a212x15的系数不都是5的倍数，故原方程没有三个解。(ii)因为这是对模5的同余方程，故原方程不可能有六个解。2、设n是正整数，求,CM的最大公约数。解：设(cn,cL，-,c-,)= j,由c；“+q+C釘=2心知 d 珂 设 2kn 且即 2&+11 | n ,则由 27-

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

11、+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(mod 24)o证明：因为24=3X8, (3,8) =1,所以只需证明:p2=q2(mod 3) p2=q2(mod 8)同时成立事实上，由于(p, 3) =1, (q, 3) =1,所以 p2=l(mod 3) , q2=l(mod 3),于是 p2=q2(mod 3),由于 p, q 都是奇数，所以 p2=l(mod 8) , q2=l(mod8),

12、于是 p?三qVmod 8)0 故 p2=q2(mod 24)。3、若 x,y R+ ,(1) 证明：xy】Axy;(2) 试讨论xy与xy啲大小关系。注：我们知道，氐 刃a凶+M,此题把加法换成乘法又如何呢？证明：(1)设 x=x+a,Oal, y=y+0,OW0 xy。(2) xy与y之间等于、大于、小于三种关系都有可能出现。当x=y=i时，xy冃衬&=扌；3131当 x=y , y=-时，xy= - , xKy=-,此时xyxXy;当 x=-i , y=-| 时，xy=； , xKy= | ,此时xyvxy。23634、证明：存在一个有理数?，其中d 100,能使k-L=k21dd L

13、100J对于2,，99均成立。证明：由(73, 100) =1以及裴蜀恒等式可知：存在整数c, d,使得73d-100c=l由k 100可知:从而JI-竺(73-呃)=丄100 d 100100100 d03,证明：6p I x-x0证明：(1)因为 2730=2X3X5X7X13, 2,3,5, 7,13 两两互质，所以：由 x13-x=x (x12-l)=0 (mod 2)知：2 I x13-x; 13 I x13-x;由 x13-x=x (x12-l)=x(x21)氐2+1)(云+芒+1)三0 (mod 3)知：3 I x13-x;由 x13-x=x (x12-1) =x(x4-1) (

14、x+x4+1)=0 (mod 5)知：5 | x13-x;由 x13-x=x (x12-1) =x(x6-1) (xc+1)=0 (mod 7)知：7 I x13-x0故有 2730 | x13-xo同理可证、(3)、(4)o初等数论练习题五一、单项选择题1、设況、y分别通过模m、n的完全剩余系，若(C )通过模nrn的完全剩余系。A. m、n 都是质数，则 my nx B mHn，则 my nxC(m, n) =1,贝Imy nxD. (m, n) =1,贝ij mx ny2、1 X 3 X 5 X X 2003 X 2005 X 2007 X 2009 X 2011 标准分解式中 11 的

15、幕指数是 (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的最小非负简化剩余系中元素的个数是(C )0A.100B.10C.40D.4二、填空题1、同余方程如b三O(modm)有解的充分必要条件是| b。2、高斯称反转定律是数论的酵母，反转定律是指设“与a是不相同的两个奇质数，(-)=(-nTT(-)pq3、20122012被3除所得的余数为_丄_。4、设n是大于2的整数，则(-l)n)=_l_

16、o5、单位圆上的有理点的坐标是住輕.=)或住二.士二)，其中次与b是不全为a- +lr” +b cr +2r零的整数。6、若3258xa恰好是一个正整数的平方，则Q的最小值为362。7、已知2011是一素数，则|三J已丄。(2011 丿一三、计算题1. 求 32oog X 72009 X 132010 的个位数字。解:32OOSX72OO9X !32010=32oocx (.3)2009X 32010三-2003+2009*2010=-3C027 =-3X (32) 3013 =3(mod 10)c2、求满足(mn)=(山)+ S)的互质的正整数m和n的值。解：由(m, n) =1 知，(mn

17、)= (ziz) (n)0 于是有：(创 + (n)= (ziz) (n)设(m)=Q,(n)=b,即有：a+b=abo 显然 a I b,且 b I a,因此 Q=b。于是由 2a=a2 得 a=2,即(zzz)=(切=2。故 m=3,n=4 或 m=4，n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100 斤，问各买几斤？解：设买甲物X斤，乙物y斤，丙物N斤，则5x 3y -z= 100,3x y z= 100o消去勺得到7x 4y= 100o(1)显然x=0, y=25是方程(1)的解，因此，方程(1)的一般解是 x = 4/,t Zy = 25-7

18、t因为 x0, y0,所以Ovr 3o即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 (mod 2011)02010 个2. 设p是4n+l型的质数，证明若a是p的平方剩余，则p%也是p的平方剩余。证明：因为质数p=4n+l, q是p的平方剩余，所以= 、一 a=(p-i-=(-!)-/ 、 a1 p )0的整数解是且仅是x= 2虻，y= a2 叽z= WZA其中方0, (7 = 1,

19、占与乃有不同的奇偶性。6、21x=9 (mod 43)的解是 x三25 (mod 43)。7、73199=-lo15z= 17,因(35, 21) = 7, (7, 15) = 1,1、将存写成三个既约分数之和，它们的分母分别是3, 5和7。 解：设i = I+5+7 即 35*21y117,故有解。分别解5x3y= t7t 15n =173n, y= 2t5n, u Z,t= 1115r, z= 47r, r Z,11y= 2230 r 5u,w, v Zo174 -X 3令“0,心1得釦X=4, y=-8,歹3。即：丽行+了+宁2、若3是质数p的平方剩余，问p是什么形式的质数?解：由二次互

20、反律”一|&卜i宁尉注意到p3, p只能为p三土 l(mod 3)且I y 三p 三 l(mod 4) p = -l(mod 4)=1只能下列情况| p = l(mod 3)|p = l(mod4)p 三-l(mod3) p = -l(mod4).p = l(mod 12)或 p 三-l(mod!2) 0 3、判断不定方程疋+23尸17是否有解?解：只要判断疋三17(mod23)是否有解即可。17=1 (mod 4)总卜信卜脩卜闫信卜G卜俘卜(I)=一1疋三17(mod 23)无解，即原方程无解。三、论证题1、试证对任何实数兀恒有X+ X+i = 2x证明：设 X=x + (7,O(71 当

21、03 时，x+*, 2x=2x.等式成立 当la0, 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,tZ,使 2m=sd+l,2n=td-lo 由此得到:2lnn=(sd+l)n, 2nm=(td-l)m于是 2

22、mn=p+ l=qd - ,p,qZ。所以：(q-p) d=2o从而d2f就有 =1或2。由因为m为奇数，所以d = l0即(2m-l, 2n+l) =lo注：我们已证过：记Mn = 2n 1,对于正整数勺b,有(必，胚) =显然当ab, lb为质数时，(胚，胚)=1。初等数论练习题七一、单项选择题1、设2和b是正整数，则(凹!.!)=( A )a bA. 1E QC. bD(比b)2、176至545的正整数中，13的倍数的个数是(B )A 27B. 28C. 29D 303、200!中末尾相继的0的个数是(A )A. 49B. 50C. 51D. 524. 从以下满足规定要求的整数中，能选取

23、出模20的简化剩余系的是(B )A. 2的倍数 B. 3的倍数 C. 4的倍数 D. 5的倍数5. 设n是正整数，下列选项为既约分数的是(A )A.岂凹B.上也14/7 + 32n -1C.心D.出5n + 23/1 + 1二、填空题1、314心被163除的余数是丄_。(欧拉定理)2、同余方程3x=5(modl3)的解是x三5(modl3)。3、(亜)= 1。18474、-k =-4。5、为使n-1与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+l,kZ。6、如果一个正整数具有21个正因数，问这个正整数最小是2叹32=576。7、同余方程x3+x2-x-1 =0(mod 3)的

24、解是x三l,2(mod 3)。三.计算题4求不定方程*2y 3z= 41的所有正整数解。解：分别解Xt2y= t3z= 41得x= t2uy = uut= 413vZ = VV消去得x= 413v2 az= Vu9 V Zo由此得原方程的全部正整数解为(x, y, -g) = (41 3v 2u, q 功，u 0, r 0, 41 3v 2u 0o2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余 3人。已知这队士兵不超过170人，问这队士兵有几人？解：设士兵有 *人，由题意得* 1 (mod 3), x 2 (mod 5), x 3 (mod ll)o 在子定理中

25、，取-W21 = 3, in2= 5,= 11, in = 3 511 = 165,M = 55, M2 = 33, M3 = 15,M = 1, M2 = 2, M3 = 3,则 x 1551(-2)33 2315 358 (mod 165),因此所求的整数*= 52 + 165。t Zo由于这队士兵不超过170人，所以这队士兵有58人。3、判断同余方程%2 = 286(mod443)是否有解P解:286=2X143, 433 是质数，(143, 443)=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号原方程有解。286、443；143-1= (-!)7143卜(估四、证明题证明

26、：(i)由Euler定理,(山)，因此，由带余数除法，有(山)=qdoZ, Q 0, 0 r1、设(a, in) = 1, &是使/ 1 (mod zz2)成立的最小正整数，则(ii)对于任意的A /, 0d 1, i y,有(mod 122)0(1)因此，由上式及况的定义，利用欧拉定理得到1&旳)=/严三(modm),lZ2)o即整数厂满足/1 (mod w), 0r Jo因为(角山)=1,所以70 (mod zn), 0 / j 1, (Z?, in) = 1,并且bA 1 (mod zn), bc 1 (mod in)(1)记(迭 d,则 Z/ 1 (mod m)o证明：由裴蜀恒等式知，

27、存在整数，y,使得应 cy= d,显然刃 0, y 0,由式知：1bdb 纱=ybd (mod nio若 x 0,由式(1)知：1bcy= bdbbd(lf (mod zz2)03、设p是素数，p厅 1, n N,则下面的两个结论中至少有一个成立：(1) P bd 1对于力的某个因数d 2,则(ii冲的mod力可以改为mod 2/2o证明：记d=(n,p 1),由， 1,1 (modp),及第2题有bd 1 (mod p)o若d2,则p 1 (mod 2)o由此及结论(ii),并利用同余的基本性质,得到 Z? 1 (mod 2n)o初等数论练习题八一、单项选择题1、设 n 1,则 n为素数是(

28、a1)11 (mod n)的(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二.填空题1 o (120) =36Oo2、7355的个位数字是

29、3。3、同余方程3x=5(modl4)的解是x三1 l(modl4)。4、() =10235、- -206、如果一个正整数具有6个正因数，问这个正整数最小是旦7、同余方程 x3+x2-x-l=0(mod 5)的解是 x三 土 1 (mod5)。1、解：把429 右淆成Jacobi符号,我们有429、5634冲 5641=(一1) 2伽韵侣H訓)429?_1= (-!)67429；6742967-1 429-1= (1)2 2429丫 27、67丿27-1 67-127)/厲零(67)(67)已知563是素数，判定方程芒 429 (mod 563)是否有解。13故方程x2429 (mod 563

30、)有解。2、求出模23的所有的二次剩余和二次非剩余。解：模23的所有的二次剩余为x 1,2,3,4,6,8,9,12,13,16,18 (mod 23);模23的所有的二次非剩余为x 5,7,10,11,14,15,17,19,20,21,22 (mod 23)。3.试求出所有正整数n，使得1“+2“+3“+彰能被5整除。解：若 n 为奇数，则 ln+2n+3n+4n ln+2n+ (-2) + (-1) n 0 (mod 5);若 n=2m, mZ,贝 ij 1”+2+3”+4“ 1 加+2 加 + (-2)加+ (-1)加2+2 X 2加=2+2 X 4山=2+2 X (- l)“(mod

31、 5);当 m 为奇数时，1+2”+3”+4” O(mod 5);当 m 为偶数时，121+2”+3”+421 4(mod 5)o故当 4jn 时，5 I ln+2n + 321+4n。四、证明题1、证明：若质数P2,则茁-1的质因数一定是2pk+l形。证明：设q是2。-1的质因数，由于2-1为奇数，歼2, (2, q) =1。由条件 q|2P-1,即 2三1 (mod g)。设方是使得2三1 (mod q)成立最小正整数，若lhpf则有方|p这与p为质数矛盾。从而h=p,于是p| q-l0又T g-1为偶数，2|q-l,2p| q-1 , q-l=2pk, 即 q=2plW &Z2、设(m,

32、n) =1,证明：in 1,立即得到d |次和d |b,这与(a,b) =1矛盾。)干是(d ,尸)=1。故d p9即 或卫。初等数论练习题九一.单项选择题1. 以下Legendre符号等于-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, 19 B. 7, 10,14,19,25, 32, 40C. 4, 2, 8, 1

33、3, 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除的余数是 2、同余方程3j5(modl6)的解是灼7(mod 16)。3、不定方程9x- 12尸15的通解是木+ 41, y=-2+3F, t Z。4、单=loI 41 J 5、实数的小数部分记为卅，则2 = 0.75。46、为使3力与4n+ 1的最大公因数达到最大可能值，整数n应满足条件科3,kZ。7、如果一个正整数具有3

34、5个正因数，问这个正整数最小是20X3-5184。三、计算题1、解不定方程 9x+24y-5=lOOOo解：解因(9, 24) =3, (3, -5) =1知原方程有解c原方程化为9x 24jz= 3 厶3t-5z= 10003x 8y= ty3t -5z= 1000,(1)解得t = 5uZ = 一200 + 3iiAT I *4再解 8y =5u 得到,u, r Zoy = i4 一 3vx = -h + 8v故y = - 3v , uy v ZoZ = -200 + 3m2、设力=蜀，盖，也是模加的一个完全系,以乂表示*的小数部分，若(%Z22)= 1,求护解：当”通过模山的完全剩余系时，axb也通过模山的完全剩余系，因此对于任意的i （1 i in）,6定与且只与某个整数/ （1 j 山）同余，即存在整数