《初等数论练习题及答案》由会员分享，可在线阅读，更多相关《初等数论练习题及答案（27页珍藏版）》请在金锄头文库上搜索。
1、初等数论练习题一一、填空题1、(2420)=27；(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 tZ。.6、分母是正整数m的既约真分数的个数为_j(m)_。7、18100被172除的余数是_256。8、 =-1。9、若p是素数，则同余方程xp- 11(mod p)的解数为p-1。二、计算题1、解同余方程：3x2+11x-200 (mo
2、d 105)。解：因105 = 357，同余方程3x2+11x-200 (mod 3)的解为x1 (mod 3)，同余方程3x2+11x-38 0 (mod 5)的解为x0，3 (mod 5)，同余方程3x2+11x-200 (mod 7)的解为x2，6 (mod 7)，故原同余方程有4解。作同余方程组：xb1 (mod 3)，xb2 (mod 5)，xb3 (mod 7)，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孙子定理得原同余方程的解为x 13，55，58，100 (mod 105)。2、判断同余方程x242(mod 107)是否有解？ 故同余方程x242(mod 107)
3、有解。3、求（127156+34）28除以111的最小非负余数。解：易知127150（mod 111）。由50258（mod 111），503585014（mod 111），50914380（mod 111）知5028（509）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
4、(mod p)及(p-1)a-1 (mod p)立得（1）和（2）成立。2、设a为正奇数，n为正整数，试证1(mod 2n+2)。 （1）证明 设a = 2m+1，当n = 1时，有a2 = (2m+1)2 = 4m(m+1)+11 (mod 23)，即原式成立。设原式对于n = k成立，则有1 (mod 2k+2) = 1+q2k+2，其中qZ，所以= (1+q2k+2)2 = 1+q2k+31 (mod 2k+3)，其中q是某个整数。这说明式(1)当n = k+1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数，且1kp-1。证明： （-1 ）k(mod p)。 证明：设A=
5、得：k!A =（p-1）(p-2)（p-k）（-1）(-2)（-k）(mod p)又（k!，p）=1，故A= （-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。由欧拉定理知：pj(4)p21(mod 4)，从而 p61(mod 4)。同理可证：p61(mod3) p61(mod 7)。故有p61(mod 84)。注：设p是不等于3和7的奇
6、质数，证明：p61(mod 168)。（见赵继源p86）初等数论练习题二一、填空题1、(1000)=_16_；（除数函数：因数的个数）(1000)=_2340_.（和函数：所有因数的和）2、2010!的规范分解式中，质数11的次数是199_.3、费尔马(Fermat)数是指Fn=+1，这种数中最小的合数Fn中的n=5。4、同余方程13x5(mod 31)的解是x29(mod 31)_5、分母不大于m的既约真分数的个数为j(2)+j(3)+j(m)。6、设7(80n-1)，则最小的正整数n=_6_.7、使41x+15y=C无非负整数解的最大正整数C=_559_.8、=_1_.9、若p是质数，np
7、-1，则同余方程xn 1 (mod p) 的解数为n .二、计算题1、试求被19除所得的余数。解：由20027 (mod 19)2002211(mod 19)200231 (mod 19)又由2003200422004（22）10021 (mod 3)可得：20023n+1(20023)n20027(mod 19)2、解同余方程3x14+4x10+ 6x-18 0 (mod 5)。解：由Fermat定理，x5x (mod 5)，因此，原同余方程等价于2x2+x- 30 (mod 5)将x 0，1，2 (mod 5)分别代入上式进行验证，可知这个同余方程解是x 1 (mod 5)。3、已知a=5
8、，m=21，求使ax 1 (mod m)成立的最小自然数x。 解：因为（5，21）=1，所以有欧拉定理知5j(21)1(mod 21)。 又由于j(21)=12，所以x|12，而12的所有正因数为1，2，3，4，6，12。于是x应为其中使5x 1 (mod12)成立的最小数，经计算知：x=6。三、证明题1、试证13|(54m+46n+2000)。(提示：可取模13进行计算性证明) 证明：54m+46n+2000252m+642n+2000（-1）2m+（-1）2n+200020020(mod 13)。2、证明Wilson定理的逆定理：若n1，并且(n- 1)! -1(mod n)，则n是素数。
9、证明：假设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、=_-1_。三、计算题1、判定() 2x3-x2+ 3x-1 0 (mod 5)是否有三个解；() x6+2x5- 4x2+ 3 0 (mod 5)是否有六个解？解：() 2x3-x2+ 3x-1 0 (mod 5)等价于x3-3x2+
10、 4x-3 0 (mod 5)，又x5-x = (x3-3x2+ 4x-3)(x2+ 3x+5) + (6x2-12x+ 15)，其中r(x) = 6x2-12x+ 15的系数不都是5的倍数，故原方程没有三个解。 () 因为这是对模5的同余方程，故原方程不可能有六个解。2、设n是正整数，求的最大公约数。 解：设知d22n-1，设2k|n且2k+1n，即2k +1|n ，则由2k +1|，i = 3， 5，L， 2n - 1得d = 2k + 1。3、已知a=18，m=77，求使ax 1 (mod m)成立的最小自然数x。 解：因为（18，77）=1，所以有欧拉定理知18j(77)1(mod 7
11、7)。 又由于j(77)=60，所以x|60，而60的所有正因数为1，2，3，4，5，6，10，12，15，20，30， 60。于是x应为其中使18x 1 (mod77)成立的最小数，经计算知：x=30。四、证明题1、若质数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）=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）证明：xyxy；（2）试讨论xy与xy的大小关系。注：我们知道，x+
