初等数论练习题答案

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的既约真分数的个数为_j(m)_。7、18100被172除的余数是_256。8、 =-1。9、假设p是素数，那么同余方程x p - 1 º1(mod p)的解数为 p-1 。二、计算题

2、1、解同余方程：3x2+11x-20 º 0 (mod 105)。解：因105 = 3×5×7，同余方程3x2+11x-20 º 0 (mod 3)的解为x º 1 (mod 3)，同余方程3x2+11x-38 º 0 (mod 5)的解为x º 0，3 (mod 5)，同余方程3x2+11x-20 º 0 (mod 7)的解为x º 2，6 (mod 7)，故原同余方程有4解。作同余方程组：x º b1 (mod 3)，x º b2 (mod 5)，x º b3 (mod

3、7)，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孙子定理得原同余方程的解为x º 13，55，58，100 (mod 105)。2、判断同余方程x242(mod 107)是否有解？ 故同余方程x242(mod 107)有解。3、求127156+3428除以111的最小非负余数。 解：易知127150mod 111。由502 58mod 111, 503 58×5014mod 111，50914380mod 111知5028 5093×50803×50803×5068×5070mod 111从而5056 16mod 111

4、。故127156+342816+3428 502870mod 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为正整数，试证1(mod 2n+2)。 1证明 设a = 2m + 1，当n = 1时，有a2 = (2m + 1)2 = 4m(m + 1) + 1 º 1 (mod 23)，即原式成立。设原式对于n = k成立，那么有 º 1 (mod

5、 2k + 2) Þ= 1 + q2k + 2，其中qÎZ，所以 = (1 + q2k + 2)2 = 1 + q ¢2k + 3 º 1 (mod 2k + 3)，其中q ¢是某个整数。这说明式(1)当n = k + 1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数，且1kp-1。证明： º -1 k(mod p)。 证明：设A= 得： 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(

6、mod 84)。 说明：因为84=4×3×7，所以，只需证明： p61(mod 4) p61(mod3) p61(mod 7) 同时成立即可。 证明：因为84=4×3×7及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的奇质数，证明：p61(mod 168)。见赵继源p86初等数论练习题二一、填空题1、d(1000)=_16_；(1000)=_2340_.

7、2、2021!的标准分解式中，质数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是质数，n½p - 1，那么同余方程x n º 1 (mod p) 的解数为n .二、计算题1、试求被19除所得的余数。 解：由20027 (mod 19) 200221

8、1(mod 19) 200231 (mod 19) 又由20032004220042210021 (mod 3)可得：20023n+1(20023)n×20027(mod 19)2、解同余方程3x14 + 4x10 + 6x - 18 º 0 (mod 5)。 解：由Fermat定理，x5 º x (mod 5)，因此，原同余方程等价于2x2 + x - 3 º 0 (mod 5)将x º 0，±1，±2 (mod 5)分别代入上式进行验证，可知这个同余方程解是x º 1 (mod 5)。3、a=5，m=21,求使

9、a x º 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应为其中使 5 x º 1 (mod 12)成立的最小数，经计算知：x=6。三、证明题1、试证13|(54m+46n+2000)。(提示：可取模13进行计算性证明) 证明：54m+46n+2000 º 252m+642n+2000 º-12m+-12n+2000 º 2002º 0(mod 13)。2、证明Wilson定理的

10、逆定理：假设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，1<a，b<s。那么 ，其中M1是正整数。由pa1也是正整数知ps是合数，这与题设矛盾。故s也是一个素数。4、证明：假设2p + 1是奇素数，那么 (p!)2 + (

11、-1)p º 0 (mod 2p + 1)。证明：由威尔逊定理知 -1 º (2p)! = p!(p + 1)L(2p) º (-1)p(p!)2(mod 2p + 1)，由此得(p!)2 + (-1)p º 0 (mod 2p + 1)。5、设p是大于5的质数，证明：p41(mod 240)。提示：可由欧拉定理证明 证明：因为240=23×3×5，所以只需证：p41(mod 8)，p41(mod 3)，p41(mod 5)即可。事实上，由j(8)=4，j(3)=2，j(5)=4以及欧拉定理立得结论。初等数论练习题三一、单项选择题1、

12、假设n1，j(n)=n-1是n为质数的 C 条件。 A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件2、设n是正整数，以下各组a，b使为既约分数的一组数是D。A.a=n+1,b=2n-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 D.a=3n+1,b=5n+23、使方程6x+5y=C无非负整数解的最大整数C是A。A.19B.24 C.25D.304、不是同余方程28x21(mod 35)的解为D。 A.x2(mod 35) B. x7(mod 35) C. x17(mod 35)D. x29(mod 35)5、设a是整数，(1)a0(mod

13、9) (2)a2021(mod9)(3)a的十进位表示的各位数字之和可被9整除(4)划去a的十进位表示中所有的数字9，所得的新数被9整除以上各条件中，成为9|a的充要条件的共有C。A.1个B.2个 C.3个 D.4个二、填空题1、(2021)=_4896_；(2021)=528。2、数的标准分解式中，质因数7的指数是_3。3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。4、同余方程24x6(mod34)的解是x113(mod34) x230(mod34)_。5、整数n>1，且(n-1)!+10(mod n),那么n为素数。6、3103被11除所得余数

14、是_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 + 4x - 3 º 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系数不都是5的倍数，故原方程没有三个解。 () 因

15、为这是对模5的同余方程，故原方程不可能有六个解。2、设n是正整数，求 的最大公约数。 解：设知d½22n-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 77)。 又由于j(77)=60，所以x|60，而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30, 60。于是x应为其中使18x º 1 (mod 77)成立的最小数

16、，经计算知：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=3×8，3,8=1，所以只需证明：p2q2(mod 3) p2q2(mod 8)同时成立。事实上， 由于p，3=1，q，3=

17、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 + y x+ y，x+yx+y。此题把加法换成乘法又如何呢？ 证明：1设x=x+,0<1，y=y+,0<1。于是xy=xy+x+y+所以xy= xy+ x+y+ xy。2xy与xy之间等于、大于、小于三种关系都有可能出现。当x=y=时，xy=xy=； 当x=， y=时，xy=，xy=

18、，此时xyxy； 当x=-，y=-时，xy=，xy=，此时xyxy。4、证明：存在一个有理数，其中d < 100,能使 = 对于k=1，2，.，99均成立。证明：由73，100=1以及裴蜀恒等式可知：存在整数c，d，使得 73d-100c=1从而-=，由k< 100可知：0-设=n，那么n+1=,于是=n+1，故 = n =。初等数论练习题四一、单项选择题 1、假设Fn=是合数，那么最小的n是( D )。A. 2 B. 3 C. 4 D. 52、记号baa表示baa,但ba+1a. 以下各式中错误的一个是( B )。A. 21820! B. 10550! C. 119100! D.

19、 1316200!3、对于任意整数n，最大公因数(2n+1，6n-1)的所有可能值是( A )。A. 1 B. 4 C. 1或2 D. 1，2或44、设a是整数，下面同余式有可能成立的是( C )。A. a22 (mod 4) B. a25 (mod 7) C. a25 (mod 11) D. a26 (mod 13)5、如果ab(mod m)，c是任意整数，那么以下错误的选项是AAacbc(mod mc)Bm|a-b C(a,m)=(b,m) Da=b+mt,tZ二、填空题 1、d(10010)=_32_，(10010)=_2880_。2、对于任意一个自然数n，为使自N起的n个相继自然数都是

20、合数，可取N=n+1！3、为使3n-1与5n+7的最大公因数到达最大可能值，整数n应满足条件n=26k+9，kZ。4、在5的倍数中，选择尽可能小的正整数来构成模12的一个简化系，那么这组数是5,25,35,555、同余方程26x+133 (mod 74)的解是x124(mod74) x261(mod74)_。6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10,y=4。7、=_-1_。三、计算题1、设n的十进制表示是，假设792½n，求x，y，z。 解：因为792 = 8×9×11，故792½n Û 8½n，9½

21、;n及11½n。我们有8½n Û 8½ Þ z = 6，以及9½n Û 9½1 + 3 + x + y + 4 + 5 + z = 19 + x + y Û 9½x + y + 1， (1)11½n Û 11½z - 5 + 4 - y + x - 3 + 1 = 3 - y + x Û 11½3 - y + x。 (2)由于0 £ x, y £ 9，所以由式(1)与式(2)分别得出x + y + 1 = 9或18，3 - y

22、 + x = 0或11。这样得到四个方程组：其中a取值9或18，b取值0或11。在0 £ x, y £ 9的条件下解这四个方程组，得到：x = 8，y = 0，z = 6。2、求3406的末二位数。解： 3，100=1，3(100)1mod 100，而(100)= (22·52)=40, 3401(mod 100) 3406=(340)10·36(32)2·32-19×9-17129(mod 100) 末二位数为29。3、求(214928+40)35被73除所得余数。 解：(214928+40)35(3228+40)35(32

23、5;32)14+4035 (102414+40)35 (214+40)35 (210×24+40)35 (25+40)35 7235 -172(mod 73)四、证明题1、设a1, a2, L, am是模m的完全剩余系，证明： 1当m为奇数时，a1+ a2+ L+ am 0mod m；2当m为偶数时，a1+ a2+ L+ am mod m。 证明：因为1, 2, L, m与a1, a2, L, am都是模m的完全剩余系，所以 (mod m)。1当m为奇数时，即得：，故(mod m)。2当m为偶数时，由m,m+1=1即得：(mod m)。2、证明：假设m2，a1, a2, L, aj(

24、m)是模m的任一简化剩余系，那么 证明：假设a1, a2, L, aj(m)是模m的一个简化剩余系，那么m-a1, m-a2, L, m-aj(m) 也是模m的一个简化剩余系，于是： 从而： 又由于m2，j(m)是偶数。故：3、设m > 0是偶数，a1, a2, L, am与b1, b2, L, bm都是模m的完全剩余系，证明：a1 + b1, a2 + b2, L, am + bm不是模m的完全剩余系。 证明：因为1, 2, L, m与a1, a2, L, am都是模m的完全剩余系，所以 (mod m)。 (1)同理 (mod m)。 (2)如果a1 + b1, a2 + b2, L,

25、 am + bm是模m的完全剩余系，那么也有(mod m)。联合上式与式(1)和式(2)，得到 0(mod m)，这是不可能的，所以a1 + b1, a2 + b2, L, am + bm不能是模m的完全剩余系。4、证明：12730x13-x； 224x(x+2)(25x2-1)；3504x9-x3； 4设质数p3，证明：6pxp-x。证明：1因为2730=2×3×5×7×13，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

26、)(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。故有2730x13-x。同理可证2、3、4。初等数论练习题五一、单项选择题 1、设x、y分别通过模m、n的完全剩余系，假设 C 通过模mn的完全剩余系。A. m、n都是质数，那么my + nx B. mn，那么my + nx C. m，n=1，那么my + nx D. m，n=1，那么mx + ny2、1×3×5×

27、×2003×2005×2007×2021×2021标准分解式中11的幂指数是( A )。A.100 B.101 C.99 D.1023、n为正整数，假设2n-1为质数，那么n是( A )。A.质数 B.合数 C.3 D.2k(k为正整数)4、从100到500的自然数中，能被11整除的数的个数是( B )。A.33 B.34 C.35 D.365、模100的最小非负简化剩余系中元素的个数是( C )。A.100 B.10 C.40 D.4二、填空题 1、同余方程ax+b0(modm)有解的充分必要条件是(a,m)b。2、高斯称反转定律是数论的酵母

28、，反转定律是指设p与q是不相同的两个奇质数， 3、20212021被3除所得的余数为_1_。4、设n是大于2的整数，那么(-1)(n)=_1_。5、单位圆上的有理点的坐标是，其中a与b是不全为零的整数。6、假设3258×a恰好是一个正整数的平方，那么a的最小值为362。7、2021是一素数，那么=_-1_。三、计算题 1、求32021×72021×132021的个位数字。 解：32021×72021×#215;-32021×32021 -32021+2021+2021 -36027 -3×323013

29、 3(mod 10)。2、求满足j(mn)=j(m)+j(n)的互质的正整数m和n的值。 解：由m，n=1知，j(mn)=j(m)j(n)。于是有：j(m)+j(n)= j(m)j(n) 设j(m)=a， j(n)=b，即有：a+b=ab。 显然ab，且ba，因此a=b。 于是由2a=a2 得a=2，即j(m)= j(n)=2。 故 m=3,n=4或m=4,n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100斤，问各买几斤? 解：设买甲物x斤，乙物y斤，丙物z斤，那么5x + 3y +z = 100，x + y + z = 100。消去z，得到 7x +

30、4y = 100。 (1)显然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是 ， 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、2021是质数，那么有2021|。 证明：=102021-10 (mod 2021)。2、设p是4n+1型的质数，证明假设a是p的平方剩余，那么p-a也是p的平方剩余。 证明：因为质数p=4n+1，a是p的平方剩余，所以 =1 即：p-a也是p的

31、平方剩余。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 (mod q)。故：apqa (mod pq)。4、证明：假设m,n都是正整数，那么j(mn)=m,nj(m,n)。 证明：易知mn与m,n有完全相同的质因数，设它们为pi (1ik)，那么 又mn=m,nm,n故。 类似的题：设m=m1m2，m1与m由

32、相同的质因数，证明：j(m)=m2j(m1)。初等数论练习题六一、填空题 1、为了验明2021是质数，只需逐个验算质数2，3，5，p都不能整除2021，此时，质数p至少是_43_。2、最大公因数(4n+3,5n+2)的可能值是_1,7_。3、设340!,而3+140!，即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,z>0的整数解是且仅是x = 2ab，y = a2 - b2，z = a2 + b2，其中a > b > 0，(a

33、, b) = 1，a与b有不同的奇偶性。6、21x9 (mod 43)的解是x25 (mod 43)。7、 = -1。二、计算题1、将写成三个既约分数之和，它们的分母分别是3，5和7。解：设，即35x + 21y + 15z = 17，因(35, 21) = 7，(7, 15) = 1，1½17，故有解。分别解 5x + 3y = t 7t + 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

34、 = -4 - 7v， u，vÎZ。令u =0，v =-1得到：x =4，y =-8，z=3。即：2、假设3是质数p的平方剩余，问p是什么形式的质数？解： 由二次互反律，注意到p>3，p只能为p1(mod 3)且 只能以下情况 或。3、判断不定方程x2+23y=17是否有解？解：只要判断x217(mod 23) 是否有解即可。 171(mod 4) x217(mod 23)无解，即原方程无解。三、论证题1、试证对任何实数x,恒有x+x+=2x证明：设x=x+,0<1当0< 时, x +=x, 2x=2x 等式成立当< 1时, x +=x+1, 2x=2x+1

35、等式成立故对任何实数x,恒有x+x+=2x。2、证明：1当n为奇数时，32n+1； 2当n为偶数时，32n+1。 证明：由2n+1-1n+1mod 3立得结论。3、证明：1当3nn为正整数时，72n-1； 2无论n为任何正整数，72n+1。 证明：1设n=3m，那么2n-1=8m -10mod 7，即：72n-1； 2由于23m 1mod 7得 23m +12mod 7，23m+1 +13mod 7，23m+2 +15mod 7。 故无论n为任何正整数，72n+1。4、设m0，n0，且m为奇数，证明：2m-1，2n+1=1。 证明一：由m为奇数可知：2n+12mn+1，又有2m-12mn-1，

36、于是存在整数x,y使得：2n+1x=2mn+1, (2m-1)y=2mn-1。从而2n+1x-(2m-1)y=2。这说明：2m-1，2n+12由于2n+1，2m-1均为奇数可知：2m-1，2n+1=1。证明二：设2m-1，2n+1=d，那么存在s,tZ,使得2m=sd+1, 2n =td-1。由此得到： 2mn=(sd+1) n, 2mn =(td-1) m 于是 2mn =pd + 1=qd 1,p,qZ。所以：q -pd =2。 从而 d2，就有d =1或2。由因为m为奇数，所以d =1。即2m-1，2n+1=1。 注：我们已证过：记Mn = 2n - 1，对于正整数a，b，有(Ma, M

37、b) = M(a, b) 。显然当ab，a,b为质数时，(Ma, Mb) =1。初等数论练习题七一、单项选择题 1、设a和b是正整数，那么=AA1 Ba CbD(a,b)2、176至545的正整数中，13的倍数的个数是BA27 B28 C29D303、200!中末尾相继的0的个数是AA49 B50 C51D524、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是 BA2的倍数 B3的倍数 C4的倍数D5的倍数5、设n是正整数，以下选项为既约分数的是AA B CD二、填空题 1、314162被163除的余数是_1_。欧拉定理2、同余方程3x5(mod13)的解是x5(mod13)。3、

38、=1。4、-4。5、为使n-1与3n的最大公因数到达最大的可能值，那么整数n应满足条件n=3k+1,kZ。6、如果一个正整数具有21个正因数，问这个正整数最小是26×32=576。7、同余方程x3+x2-x-10(mod 3)的解是x1,2(mod 3)。三、计算题1、求不定方程x + 2y + 3z = 41的所有正整数解。解：分别解x + 2y = tt + 3z = 41得 x = t - 2uy = u uÎZ，t = 41 - 3vz = v vÎZ，消去t得 x = 41 - 3v - 2uy = uz = v u，vÎZ。由此得原方程的全部

39、正整数解为(x, y, z) = (41 - 3v - 2u, u, v)，u > 0，v > 0，41 - 3v - 2u > 0。2、有一队士兵，假设三人一组，那么余1人；假设五人一组，那么缺2人；假设十一人一组，那么余3人。这队士兵不超过170人，问这队士兵有几人？ 解：设士兵有x人，由题意得x º 1 (mod 3)，x º -2 (mod 5)，x º 3 (mod 11)。在孙子定理中，取 m1 = 3， m2 = 5， m3 = 11，m = 3×5×11 = 165，M1 = 55，M2 = 33，M3 = 1

40、5，M1¢ = 1，M2¢ = 2，M3¢ = 3，那么 x º 1×55×1 + -2×33×2 + 3×15×3 º 58 (mod 165)，因此所求的整数x = 52 + 165t，tÎZ。由于这队士兵不超过170人，所以这队士兵有58人。3、判断同余方程是否有解?解：286=2×143，433是质数，(143，443)=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号 原方程有解。四、证明题 1、设(a, m) = 1，d0是使a d º

41、; 1 (mod m)成立的最小正整数，那么() d0½j(m)；()对于任意的i，j，0 £ i, j £ d0 - 1，i ¹ j，有a ia j (mod m)。 1证明：() 由Euler定理，d0 £ j(m)，因此，由带余数除法，有j(m) = qd0 + r，qÎZ，q > 0，0 £ r < d0。因此，由上式及d0的定义，利用欧拉定理得到1 º(mod m)，即整数r满足 a r º 1 (mod m)，0 £ r < d0 。由d0的定义可知必是r = 0，

42、即d0½j(m)。() 假设式(1)不成立，那么存在i，j，0 £ i, j £ d0 - 1，i ¹ j，使a i º a j (mod m)。不妨设i > j。因为(a, m) = 1，所以 ai - j º 0 (mod m)，0 < i - j < d0。这与d0的定义矛盾，所以式(1)必成立。2、证明：设a，b，c，m是正整数，m > 1，(b, m) = 1，并且b a º 1 (mod m)，b c º 1 (mod m) 1记d = (a, c)，那么bd º 1

43、(mod m)。 证明：由裴蜀恒等式知，存在整数x，y，使得ax + cy = d，显然xy < 0。假设x > 0，y < 0，由式(1)知：1 º b ax = b db -cy = b d(b c) -y º b d (mod m)。假设x < 0，y > 0，由式(1)知：1 º b cy = b db -ax = b d(ba) -x º b d (mod m)。3、设p是素数，p½bn - 1，nÎN，那么下面的两个结论中至少有一个成立：() p½bd - 1对于n的某个因数d &l

44、t; n成立；() p º 1 ( mod n )。假设2n，p > 2，那么()中的mod n可以改为mod 2n。证明：记d = (n, p - 1)，由b n º 1，b p - 1 º 1 (mod p)，及第2题有b d º 1 (mod p)。假设d < n，那么结论()得证。假设d = n，那么n½p - 1，即p º 1 (mod n)，这就是结论()。假设2n，p > 2，那么p º1 (mod 2)。由此及结论()，并利用同余的根本性质，得到p º 1 (mod 2n)。初等数

45、论练习题八一、单项选择题 1、设n > 1，那么n为素数是(n - 1)! º -1 (mod n)的 C 。 A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件2、小于545的正整数中，15的倍数的个数是 C A.34 B.35 C.36 D.373、500!的标准分解式中7的幂指数是 D A.79 B.80 C.81 D.824、以下各组数中，成为模10的简化剩余系的是 D A.1,9,3,1 B.1,1,7,9 C.5,7,11,13 D.1,1,3,35、设n是正整数，以下选项为既约分数的是 A A. B. C. D. 二、填空题1、12

46、0=360。2、7355的个位数字是3。3、同余方程3x5(mod14)的解是x11(mod14)。4、=1。5、-2。6、如果一个正整数具有6个正因数，问这个正整数最小是12。7、同余方程x3+x2-x-10(mod 5)的解是x±1(mod5)。三、计算题 1、563是素数，判定方程x2 º 429 (mod 563)是否有解。解：把看成Jacobi符号,我们有-，故方程x2 º 429 (mod 563)有解。2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余为xº1,2,3,4,6,8,9,12,13,16,18 (mod

47、23)；模23的所有的二次非剩余为xº5,7,10,11,14,15,17,19,20,21,22 (mod 23)。3、试求出所有正整数n ，使得1n2n3n4n 能被5整除。 解：假设n为奇数，那么1n2n3n4nº1n2n-2n-1n º 0 (mod 5)； 假设n=2m，mZ，那么1n2n3n4nº12m22m-22m-12m º2+2×22m =2+2×4m =2+2×(-1)m(mod 5)； 当m为奇数时，1n2n3n4nº0(mod 5)； 当m为偶数时，1n2n3n4nº4(

48、mod 5)。 故当4n时，51n2n3n4n 。四、证明题 1、证明：假设质数p>2，那么2P-1的质因数一定是2pk+1形。证明：设q是2-1的质因数，由于2-1为奇数， q2，2，q=1。由条件q|2p-1,即21mod q。设h是使得21mod q成立最小正整数，假设1<h<p，那么有h|p。这与p为质数矛盾。从而 h=p, 于是 p|q-1。又 q-1为偶数，2|q-1， 2p|q-1，q-1=2pk, 即q=2pk+1 kZ。2、设m,n=1,证明：mj(n)+n j(m) 1 (mod mn)。 证明：因为m,n=1，所以由欧拉定理知： n j(m) 1 (mo

49、d m)，mj(n) 1 (mod n) 于是 mj(n)+n j(m) 1 (mod m)， mj(n)+n j(m) 1 (mod n)。 又因为m,n=1，所以 mj(n)+n j(m) 1 (mod mn)。 注：此题也可这样表述：假设两个正整数a,b互质，那么存在正整数m,n，使得am+bn1(mod ab)。3、设a,b=1,a+b0,p为一个奇质数，证明：。 说明：事实上，设，只需证明：d | p 即可。证明：由a+b0(mod a+b)，即a-b (mod a+b)，知ak(-b)k (mod a+b)。其中0kp-1。又。令，那么d | pbp-1 。 又a,b=1，d |a

50、+b知d,b=1。否那么设d,b=d1，立即得到da和db，这与a,b=1矛盾。于是d ，bp-1=1。故d | p，即 d =1或p。初等数论练习题九一、单项选择题1、以下Legendre符号等于-1的30被-1是( D )A. B. C. D. 2、100至500的正整数中，能被17整除的个数是( B )A. 23B. 24C. 25D. 263、设 |500!，但500！，那么=( C )A. 245B.246C.247D. 2484、以下数组中，成为模7的完全剩余系的是( C )A. 14，4，0，5，15，18，19B. 7，10，14，19，25，32，40C. 4，2，8，13，

51、32，35，135D. 3，3，4，4，5，5，05、设n是正整数，那么以下各式中一定成立的是( B )A. (n+1，3n1)=1B.2n1，2n1=1C.2n，n1=1D.2n1，n1=1二、填空题 1、25736被50除的余数是1。2、同余方程3x5(mod16) 的解是x7(mod16)。3、不定方程9x12y=15的通解是x = -1 + 4t，y = -2 +3t，tÎZ。4、 =1。5、实数的小数局部记为x ，那么 0.75。6、为使3n与4n1 的最大公因数到达最大可能值，整数n应满足条件n=3k+2，kZ。7、如果一个正整数具有35个正因数，问这个正整数最小是26&

52、#215;34=5184。三、计算题 1、解不定方程9x24y5z=1000。 解：解 因9，24=3，3，-5=1知原方程有解。原方程化为9x + 24y = 3t， 即 3x + 8y = t， (1)3t -5z = 1000 3t -5z = 1000， (2)解(2)得 ， uÎZ，再解3x + 8y =5u得到 ， u，vÎZ。故 ， u, vÎZ。 2、设A = x1, x2, L, xm是模m的一个完全系，以x表示x的小数局部，假设(a, m) = 1，求。解：当x通过模m的完全剩余系时，ax + b也通过模m的完全剩余系，因此对于任意的i1 &#

53、163; i £ m，axi + b一定与且只与某个整数j1 £ j £ m同余，即存在整数k，使得axi + b = km + j，0 £ j £ m-1。从而：3、设整数n ³ 2，求：。即在数列1, 2, L, n中，与n互素的整数之和。解：设在1, 2, L, n中与n互素的j(n)个数是a1, a2, L, aj(n)，(ai, n) = 1，1 £ ai £ n - 1，1 £ i £ j(n)，那么 (n - ai, n) = 1，1 £ n - ai £ n - 1，1 £ i £ j(n)，因此，集合a1, a2, L, aj(n)与集合n - a1, n - a2, L, n - aj(n)是相同的，于是a1 + a2 + L + aj(n) =