初等数论练习题答案（精编版）

1、初等数论练习题一一、填空题1、d(2420)=12; (2420)=_880_ 2、设 a,n是大于 1 的整数，若 an-1 是质数，则 a=_2. 3、模 9 的绝对最小完全剩余系是 _-4 ，-3，-2，-1,0,1,2,3,4. 4、同余方程 9x+120(mod 37)的解是 x11(mod 37)。5、不定方程 18x-23y=100 的通解是 x=900+23t，y=700+18t t z。. 6、分母是正整数 m的既约真分数的个数为 _ (m ) _。7、18100被 172除的余数是 _256。8、10365=-1。9、若 p 是素数，则同余方程xp 11(mod p) 的解

2、数为 p-1 。二、计算题1、解同余方程： 3x211x 20 0 (mod 105) 。解：因 105 = 35 7，同余方程 3x211x 20 0 (mod 3) 的解为 x 1 (mod 3) ，同余方程 3x211x 38 0 (mod 5) 的解为 x 0 ，3 (mod 5) ，同余方程 3x211x 20 0 (mod 7) 的解为 x 2 ，6 (mod 7) ，故原同余方程有 4 解。作同余方程组： x b1 (mod 3) ，x b2 (mod 5) ，x b3 (mod 7) ，其中 b1 = 1 ，b2 = 0 ，3，b3 = 2 ，6，由孙子定理得原同余方程的解为x

3、 13 ，55，58，100 (mod 105) 。2、判断同余方程 x242(mod 107)是否有解？11074217271071107713231071107311072107710731072107732107422110721721107213)(?）（）（）（）（），（）（）（）（），（）（）（）（）（解：故同余方程 x242(mod 107)有解。3、求（ 127156+34）28除以 111的最小非负余数。解：易知 127150（mod 111） 。由 50258（mod 111）, 503585014（mod 111） ，50914380（mod 111）知 5028（509

4、）3508035080350685070（mod 111）从而 505616（mod 111） 。故（127156+34）28（16+34）28502870（mod 111）三、证明题1、已知 p 是质数， （a,p）=1，证明：（1）当 a 为奇数时， ap-1+(p-1)a0 (mod p)；（2）当 a 为偶数时， ap-1-(p-1)a0 (mod p)。证明：由欧拉定理知ap-11 (mod p) 及(p-1)a-1 (mod p) 立得（ 1）和（ 2）成立。2、设 a 为正奇数， n 为正整数，试证n2a1(mod 2n+2)。 （1）证明设 a = 2m 1，当 n = 1 时

5、，有a2 = (2m 1)2 = 4m(m 1) 1 1 (mod 23)，即原式成立。设原式对于 n = k 成立，则有ka2 1 (mod 2k + 2) ka2= 1 q2k + 2，其中 q z，所以12ka= (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3)，其中 q 是某个整数。这说明式 (1)当 n = k 1 也成立。由归纳法知原式对所有正整数n 成立。3、设 p 是一个素数，且 1kp-1。证明：kp 1c（-1 ）k(mod p)。证明：设 a=!)()2(1c1kkpppkp）（得： k!a =（p-1）(p-2) （p-k ）（ -1）(

6、-2) （-k ）(mod p) 又（k! ，p）=1，故 a = kp 1c（-1 ）k(mod p)4、设 p 是不等于 3 和 7 的奇质数，证明： p61(mod 84)。说明：因为 84=437，所以，只需证明：p61(mod 4) p61(mod3) p61(mod 7) 同时成立即可。证明：因为 84=437 及 p 是不等于 3 和 7 的奇质数，所以（p，4）=1， （p，3）=1， （p，7）=1。由欧拉定理知： p(4)p21(mod 4)，从而 p61(mod 4)。同理可证： p61(mod3) p61(mod 7)。故有 p61(mod 84)。注：设 p 是不等于

7、 3 和 7 的奇质数，证明： p61(mod 168)。 （见赵继源 p86）初等数论练习题二一、填空题1、d(1000)=_16_；(1000)=_2340_. 2、2010!的标准分解式中，质数11的次数是 199_. 3、费尔马 (fermat)数是指 fn=n22+1,这种数中最小的合数fn 中的 n=5。4、同余方程 13x5(mod 31)的解是 x29(mod 31)_ 5、分母不大于 m的既约真分数的个数为(2)+(3)+ +( m ) 。6、设 7(80n-1),则最小的正整数 n=_6_. 7、使 41x+15y=c 无非负整数解的最大正整数c=_559_. 8、1014

8、6=_1_. 9、若 p 是质数， n p 1，则同余方程 xn 1 (mod p) 的解数为 n . 二、计算题1、试求200420032002被 19除所得的余数。解：由 20027 (mod 19) 2002211(mod 19) 200231 (mod 19) 又由 22004（22）10021 (mod 3) 可得：20042003200220023n+1(20023)n20027(mod 19) 2、解同余方程 3x14 4x10 6x 18 0 (mod 5)。解：由 fermat定理， x5x (mod 5)，因此，原同余方程等价于2x2x 3 0 (mod 5) 将 x 0，

9、 1， 2 (mod 5)分别代入上式进行验证，可知这个同余方程解是x 1 (mod 5)。3、已知 a=5，m=21,求使 a x 1 (mod m) 成立的最小自然数x。解：因为（ 5,21）=1，所以有欧拉定理知5(21)1(mod 21)。又由于 (21)=12 ，所以 x|12，而 12 的所有正因数为1,2,3,4,6,12 。于是 x 应为其中使5x 1 (mod 12) 成立的最小数，经计算知：x=6。三、证明题1、试证 13|(54m+46n+2000)。(提示：可取模 13 进行计算性证明 ) 证明： 54m+46n+2000 252m+642n+2000（-1）2m+（-

10、1）2n+2000 2002 0(mod 13) 。2、证明 wilson 定理的逆定理：若n 1，并且 (n 1)! 1 (mod n)，则 n 是素数。证明：假设 n 是合数，即 n = n1n2，1 n1 n，由题设易知 (n 1)! 1 (mod n1)，得0 1 (mod n1)，矛盾。故 n 是素数。3、证明：设ps表示全部由 1 组成的 s 位十进制数，若ps是素数，则 s也是一个素数。证明：假设 s 是合数，即 s=ab，1a，b1，且(n-1)!+10(mod n),则 n 为素数。6、3103被 11除所得余数是 _5_。7、9760=_-1_。三、计算题1、判定 () 2

11、x3x2 3x 1 0 (mod 5)是否有三个解；() x6 2x5 4x2 3 0 (mod 5)是否有六个解？解：() 2x3x2 3x 1 0 (mod 5)等价于 x3 3x2 4x 3 0 (mod 5)，又 x5x = (x33x2 4x 3)(x2 3x 5) + (6x2 12x 15)，其中 r(x) = 6x2 12x 15 的系数不都是 5 的倍数，故原方程没有三个解。() 因为这是对模 5 的同余方程，故原方程不可能有六个解。2、设 n 是正整数，求1223212c,c,cnnnn的最大公约数。解：设12122321212232122ccc)c,c,(cnnnnnnn

12、nnd，由知 d 22n 1，设 2k|n 且 2k+1|n，即 2k +1|n ，则由 2k +1|1122112c2c2c|ininknin及，i = 3, 5, , 2n 1 得 d = 2k + 1。3、已知 a=18,m=77,求使 ax 1 (mod m) 成立的最小自然数x。解：因为（ 18,77）=1，所以有欧拉定理知18(77)1(mod 77)。又由于 (77)=60 ，所以 x|60，而 60 的所有正因数为1,2,3,4,5,6,10,12,15,20,30, 60 。于是 x 应为其中使 18x 1 (mod 77) 成立的最小数，经计算知：x=30。四、证明题1、若

13、质数 p5, 且 2p+1是质数，证明： 4p+1必是合数。证明：因为质数 p5, 所以（ 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 的质数，证明： p2q2(mod 24)。证明：因为 24=38， （3,8 ）=1，所以只需证明：p2q2(mod 3) p2q2(mod 8)同时成立。事实上，由于（ p，3）=1， （q，3

14、）=1，所以 p21(mod 3) ， q21(mod 3)，于是 p2q2(mod 3)，由于 p，q 都是奇数，所以 p21(mod 8) ， q21(mod 8)，于是 p2q2(mod 8)。故 p2q2(mod 24)。3、若 x,yr+ ，（1）证明： xy xy；（2）试讨论 xy 与xy的大小关系。注：我们知道， xy x+ y，x+y x+ y 。此题把加法换成乘法又如何呢？证明： （1）设 x=x+ ,0 1，y=y+ ,0 1。于是xy=xy+x+ y+ 所以xy= xy+ x+ y+ xy。（2）xy 与xy之间等于、大于、小于三种关系都有可能出现。当 x=y=21时，

15、xy=xy=41；当 x=23， y=21时，xy=43，xy=41，此时 xy xy；当 x=-21，y=-31时，xy=61，xy=31，此时 xy xy。4、证明：存在一个有理数dc，其中 d 100,能使dck=10073k对于 k=1，2，.，99 均成立。证明：由（ 73，100）=1 以及裴蜀恒等式可知：存在整数c，d，使得73d-100c=1 从而k10073-dkc=dcdk100)10073(=dk100，由 k 0 是偶数，a1, a2, , am 与b1, b2, , bm都是模 m的完全剩余系， 证明：a1b1, a2b2, , ambm 不是模 m的完全剩余系。证明

16、：因为 1, 2, , m 与 a1, a2, , am都是模 m的完全剩余系，所以mimiimmmia1122)1(mod m)。(1) 同理miimb12(mod m)。(2) 如果a1b1, a2b2, , ambm是模 m 的完全剩余系，那么也有miiimba12)(mod m)。联合上式与式 (1)和式(2)，得到0222mmm(mod m)，这是不可能的，所以 a1b1, a2b2, , ambm不能是模 m的完全剩余系。4、证明： （1）2730 x13-x；（2）24x(x+2)(25x2-1)；（3）504x9-x3；（4）设质数 p3，证明： 6pxp-x。证明： （1）因

17、为 2730=235713，2,3,5 ，7,13 两两互质，所以：由 x13-x=x (x12-1)0 (mod 2)知：2x13-x；13x13-x；由 x13-x=x (x12-1)=x(x2-1)(x2+1)(x8+x4+1)0 (mod 3)知：3x13-x；由 x13-x=x (x12-1)=x(x4-1)(x8+x4+1)0 (mod 5)知：5x13-x；由 x13-x=x (x12-1)=x(x6-1)(x6+1)0 (mod 7)知：7x13-x。故有 2730 x13-x。同理可证（ 2） 、 （3） 、 （4） 。初等数论练习题五一、单项选择题1、设 x、y 分别通过模

18、 m、n 的完全剩余系，若（c ）通过模 mn 的完全剩余系。a. m、n 都是质数，则 my nx b. mn，则 my nx c. （m，n）=1，则 my nx d. （m，n）=1，则 mx ny 2、135 20032005200720092011标准分解式中 11 的幂指数是 ( a)。3、n 为正整数，若 2n-1 为质数，则 n 是( a)。a.质数b.合数(k 为正整数 ) 4、从 100 到 500 的自然数中，能被11整除的数的个数是 ( b)。5、模 100 的最小非负简化剩余系中元素的个数是( c)。二、填空题1、同余方程 ax+b0(modm)有解的充分必要条件是

19、(a,m) b。2、高斯称反转定律是数论的酵母，反转定律是指设p 与 q 是不相同的两个奇质数，)()(2121) 1(qppqqp3、被 3 除所得的余数为 _1_。4、设 n 是大于 2 的整数，则 (-1)(n)=_1_。5、单位圆上的有理点的坐标是)()(2222222222222,2baabbababababaab或，其中 a 与 b 是不全为零的整数。6、若 3258a 恰好是一个正整数的平方，则a 的最小值为 362。7、已知 2011是一素数，则201172=_-1_。三、计算题1、求 3200872009132010的个位数字。解：320087200913201032008（

20、-3）200932010-32008+2009+2010-36027 -3（32）3013 3(mod 10)。2、求满足 (mn)= (m)+ (n)的互质的正整数 m 和 n 的值。解：由（ m，n）=1 知， (mn)= (m) (n)。于是有：(m)+ (n)= (m) (n) 设 (m)=a，(n)=b，即有： a+b=ab 。 显然 ab，且 ba，因此 a=b。于是由 2a=a2 得 a=2，即 (m)=(n)=2。 故m=3,n=4 或 m=4,n=3。3、甲物每斤 5 元，乙物每斤 3 元，丙物每三斤1 元，现在用 100 元买这三样东西共100斤，问各买几斤 ? 解：设买甲

21、物 x 斤，乙物 y 斤，丙物 z 斤，则5x 3y31z = 100，xyz = 100。消去 z，得到7x 4y = 100。(1) 显然 x = 0，y = 25 是方程 (1)的解，因此，方程 (1)的一般解是tytx7254， t z因为 x0，y0，所以0t 3。即 t 可以取值 t1 = 1，t2 = 2，t3 = 3。相应的 x，y，z 的值是(x, y, z) = (4, 18, 78)，(8, 11, 81)，(12, 4, 84)。四、证明题1、已知 2011是质数，则有 2011|个2010999。证明：个2010999=102011-10 (mod 2011)。2、设

22、 p 是 4n+1 型的质数，证明若a是 p 的平方剩余，则 p-a 也是 p 的平方剩余。证明：因为质数 p=4n+1，a是 p 的平方剩余，所以pap=pa=p1pa=21) 1(ppa=1 即：p-a也是 p 的平方剩余。3、已知 p,q 是两个不同的质数，且ap-11 (mod q), aq-11 (mod p), 证明： apqa (mod pq)。证明：由 p,q 是两个不同的质数知（ p，q）=1。于是由 fermat定理 apa (mod p), 又由题设 aq-11 (mod p)得到： apq(aq)pap (aq-1)papa (mod p)。同理可证： apqa (mo

23、d q)。故：apqa (mod pq)。4、证明：若 m,n 都是正整数，则(mn)=（m,n） (m,n)。证明：易知 mn 与m,n有完全相同的质因数，设它们为pi (1i k)，则)11 ()11)(11(21kpppmnmn）（)11()11)(11(,21kpppnmnm）（又 mn=（m,n）m,n 故),(),()11()11)(11(,),21nmnmpppnmnmmnk（）（。类似的题：设 m=m1m2，m1与 m 由相同的质因数，证明：(m)=m2(m1)。初等数论练习题六一、填空题1、为了验明 2011 是质数，只需逐个验算质数2，3，5，p 都不能整除 2011，此时

24、，质数 p 至少是 _43_。2、最大公因数 (4n+3,5n+2)的可能值是 _1,7_。3、设 340!,而 3+1|40!，即 340!，则 =_18_。4、形如 3n+1 的自然数中， 构成模 8 的一个完全系的最小那些数是1,4,7,10,13,16,19，22。5、不定方程x2+y2=z2,2|x, (x,y)=1, x,y,z0 的整数解是且仅是x = 2ab，y = a2b2，z = a2b2，其中a b 0，(a, b) = 1，a 与 b 有不同的奇偶性。6、21x9 (mod 43)的解是 x25 (mod 43)。7、19973= -1。二、计算题1、将10517写成三

25、个既约分数之和，它们的分母分别是3，5 和 7。解：设75310517zyx，即 35x 21y 15z = 17，因(35, 21) = 7，(7, 15) = 1，1 17，故有解。分别解 5x 3y = t7t 15z = 17 得x = t 3u，y = 2t 5u，u z，t = 11 15v，z = 4 7v，v z，消去 t 得x = 11 15v 3u，y = 22 30v 5u，z = 4 7v，u，v z。令 u =0，v =-1 得到：x =4，y =-8，z=3。即：735834105172、若 3 是质数 p 的平方剩余，问 p 是什么形式的质数？解： 由二次互反律3

26、)1(321ppp，注意到 p3，p 只能为 p1(mod 3) 且113p)4(mod1)4(mod1pp13p只能下列情况)(mod)(mod4131pp)4(mod1)3(mod1pp)(mod 121p或)(mod 121p。3、判断不定方程 x2+23y=17 是否有解？解：只要判断 x217(mod 23) 是否有解即可。 171(mod 4) 13231717317317217617232317 x217(mod 23) 无解，即原方程无解。三、论证题1、试证对任何实数x,恒有 x+x+21=2x证明：设 x=x+ ,01 当 0 21时, x +21=x, 2x=2x 等式成立

27、当21 0，v 0，41 3v 2u 0。2、有一队士兵，若三人一组，则余1 人；若五人一组，则缺2 人；若十一人一组，则余3人。已知这队士兵不超过170 人，问这队士兵有几人？解：设士兵有 x 人，由题意得 x 1 (mod 3)，x2 (mod 5)，x 3 (mod 11)。在孙子定理中，取m1 = 3， m2 = 5， m3 = 11，m = 3 5 11 = 165，m1 = 55，m2 = 33，m3 = 15，m1 = 1，m2 = 2，m3 = 3，则x 1 55 1 （-2） 33 2 3 15 3 58 (mod 165)，因此所求的整数 x = 52 + 165t，t z

28、。由于这队士兵不超过170 人，所以这队士兵有58 人。3、判断同余方程)(mod 4432862x是否有解 ? 解：286=2143，433 是质数， (143，443)=1 奇数 143 不是质数，但可用判定雅可比符号计算的勒让德符号1437143214314143443)1() 1(443143243244328621443211432144327143)1()1(211432178114313173原方程有解。四、证明题1、设(a, m) = 1，d0是使 ad 1 (mod m)成立的最小正整数，则() d0(m)；()对于任意的 i，j，0 i, j d0 1，i j，有 aiaj

29、 (mod m)。 （1）证明：() 由 euler 定理， d0(m)，因此，由带余数除法，有(m) = qd0r，q z，q 0，0 r d0。因此，由上式及 d0的定义，利用欧拉定理得到1 rrqdmaaa0)(mod m)，即整数 r 满足ar 1 (mod m)，0 r j。因为 (a, m) = 1，所以aij 0 (mod m)，0 ij 1，(b, m) = 1，并且ba 1 (mod m)，bc 1 (mod m) （1）记 d = (a, c)，则 bd 1 (mod m)。证明：由裴蜀恒等式知，存在整数x，y，使得 axcy = d，显然 xy 0，y 0，由式 (1)知

30、：1bax = bdbcy = bd(bc)ybd (mod m)。若 x 0，由式 (1)知：1bcy = bdbax = bd(ba)xbd (mod m)。3、设 p 是素数， p bn 1，n n，则下面的两个结论中至少有一个成立：() p bd 1 对于 n 的某个因数 d 2，则()中的 mod n 可以改为 mod 2n。证明：记 d = (n, p 1)，由 bn 1，bp 1 1 (mod p)，及第 2 题有bd 1 (mod p)。若 d 2，则 p 1 (mod 2)。由此及结论 ()，并利用同余的基本性质，得到 p 1 (mod 2n)。初等数论练习题八一、单项选择题

31、1、设 n 1，则 n 为素数是 (n 1)! 1 (mod n)的（ c ） 。 a. 必要但非充分条件 b.充分但非必要条件 c. 充要条件 d.既非充分又非必要条件2、小于 545 的正整数中， 15 的倍数的个数是（c）3、500!的标准分解式中 7 的幂指数是（d ）4、以下各组数中，成为模10 的简化剩余系的是（d）,9,3,1 ,1,7,9 ,7,11,13 d.1,1,3,3 5、设 n 是正整数，下列选项为既约分数的是（a）a.2n51n3b.1n21nc.2n51n2d.1n31n二、填空题1、（ 120）=360。2、7355的个位数字是 3。3、同余方程 3x5(mod

32、14)的解是 x11(mod14)。4、 （2317）=1。5、 -2-2。6、如果一个正整数具有6 个正因数，问这个正整数最小是12。7、同余方程 x3+x2-x-10(mod 5)的解是 x1(mod5)。三、计算题1、已知 563 是素数，判定方程x2 429 (mod 563) 是否有解。解：把563429看成 jacobi 符号, 我们有42967)1(429674292429134429563429563) 1(5634298142921563.214292-）27672767)1(67276742967429)1(429672167.212721429.216711311327)

33、 1(27132113.2127，故方程 x2 429 (mod 563) 有解。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 ，使得 1n2n3n4n 能被 5 整除。解：若 n 为奇数，则 1n2n3n4n1n2n（-2）n（-1）n 0 (mod 5)；若 n=2m，m z，则 1n2n3n4n12m22m（-2）2m（-1）2m2+222m=2

34、+24m =2+2(-1)m(mod 5)；当 m 为奇数时， 1n2n3n4n0(mod 5)；当 m 为偶数时， 1n2n3n4n4(mod 5)。故当 4|n 时，51n2n3n4n。四、证明题1、证明：若质数 p2，则 2p-1 的质因数一定是 2pk+1 形。证明：设 q 是 2p-1 的质因数，由于 2p-1 为奇数，q2， （2，q）=1。由条件 q|2p-1, 即 2p1（mod q） 。设 h 是使得 2x1（mod q）成立最小正整数，若1h 1，(a, m) = 1，x1, x2, , x(m)是模 m 的简化剩余系，求：)(1miimax。其中 x 表示 x 的小数部分。解：设 axi = mqiri，0 ri 3，p 只能为 p1(mod 4) 且113p)3(mod1)3(mod1pp13p，只能是下列情况)4(mod1) 3(mod1pp)4(mod1)3(mod1pp)(mod 121p或)(mod 121p。2、求使 12347!被 35k整除的最大的 k值。解：k=2054. 四、证明题1、证明：设7p是一个质数，则存在唯一的一个正整数x，使得：1,2,1!0 modxpxpl且120 p-6证明：存在性：因为7p是一个素数，由 wilson 定理我们有：1 ! 10 modpp ，然而1