初等数论练习题答案.doc

初等数论练习题一一、填空题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 tZ。.6、分母是正整数m的既约真分数的个数为_j(m)_。7、18100被172除的余数是_256。8、 =-1。9、若p是素数，则同余方程x p - 1 1(mod p)的解数为 p-1 。二、计算题1、解同余方程：3x2+11x-20 0 (mod 105)。解：因105 = 357，同余方程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 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+34）28除以111的最小非负余数。 解：易知127150（mod 111）。由502 58（mod 111）, 503 585014（mod 111），50914380（mod 111）知5028 （509）3508035080350685070（mod 111）从而5056 16（mod 111）。故（127156+34）28（16+34）28 502870（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为正整数，试证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 2k + 2) = 1 + q2k + 2，其中qZ，所以 = (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(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的奇质数，证明：p61(mod 168)。（见赵继源p86）初等数论练习题二一、填空题1、d(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 - 1，则同余方程x n 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定理，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,求使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 （-1）2m+（-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、=_-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的倍数，故原方程没有三个解。 () 因为这是对模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 77)。 又由于j(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、若质数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 + y x+ y，x+yx+y。此题把加法换成乘法又如何呢？ 证明：（1）设x=x+,01，y=y+,01。于是xy=xy+x+y+所以xy= xy+ x+y+ xy。（2）xy与xy之间等于、大于、小于三种关系都有可能出现。当x=y=时，xy=xy=； 当x=， y=时，xy=，xy=，此时xyxy； 当x=-，y=-时，xy=，xy=，此时xyxy。4、证明：存在一个有理数，其中d 100,能使 = 对于k=1，2，.，99均成立。证明：由（73，100）=1以及裴蜀恒等式可知：存在整数c，d，使得 73d-100c=1从而-=，由k 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, am + bm是模m的完全剩余系，那么也有(mod m)。联合上式与式(1)和式(2)，得到 0(mod m)，这是不可能的，所以a1 + b1, a2 + b2, L, am + bm不能是模m的完全剩余系。4、证明：（1）2730 x13-x； （2）24x(x+2)(25x2-1)；（3）504x9-x3； （4）设质数p3，证明：6pxp-x。证明：（1）因为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分别通过模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、13520032005200720092011标准分解式中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、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数， 3、20122012被3除所得的余数为_1_。4、设n是大于2的整数，则(-1)(n)=_1_。5、单位圆上的有理点的坐标是，其中a与b是不全为零的整数。6、若3258a恰好是一个正整数的平方，则a的最小值为362。7、已知2011是一素数，则=_-1_。三、计算题 1、求3200872009132010的个位数字。 解：320087200913201032008（-3）200932010 -32008+2009+2010 -36027 -3（32）3013 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 + 4y = 100。 (1)显然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是 ， tZ因为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|。 证明：=102011-10 (mod 2011)。2、设p是4n+1型的质数，证明若a是p的平方剩余，则p-a也是p的平方剩余。 证明：因为质数p=4n+1，a是p的平方剩余，所以 =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 (mod q)。故：apqa (mod pq)。4、证明：若m,n都是正整数，则j(mn)=（m,n）j(m,n)。 证明：易知mn与m,n有完全相同的质因数，设它们为pi (1ik)，则 又mn=（m,n）m,n故。 类似的题：设m=m1m2，m1与m由相同的质因数，证明：j(m)=m2j(m1)。初等数论练习题六一、填空题 1、为了验明2011是质数，只需逐个验算质数2，3，5，p都不能整除2011，此时，质数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,z0的整数解是且仅是x = 2ab，y = a2 - b2，z = a2 + b2，其中a b 0，(a, 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，117，故有解。分别解 5x + 3y = t 7t + 15z = 17得 x = -t + 3u，y = 2t - 5u，uZ，t = 11 + 15v，z = -4 - 7v，vZ， 消去t得 x = -11 - 15v + 3u，y = 22 + 30v - 5u，z = -4 - 7v， u，vZ。令u =0，v =-1得到：x =4，y =-8，z=3。即：2、若3是质数p的平方剩余，问p是什么形式的质数？解： 由二次互反律，注意到p3，p只能为p1(mod 3)且 只能下列情况 或。3、判断不定方程x2+23y=17是否有解？解：只要判断x217(mod 23) 是否有解即可。 171(mod 4) x217(mod 23)无解，即原方程无解。三、论证题1、试证对任何实数x,恒有x+x+=2x证明：设x=x+,01当0 时, x +=x, 2x=2x 等式成立当 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 = 3511 = 165，M1 = 55，M2 = 33，M3 = 15，M1 = 1，M2 = 2，M3 = 3，则 x 1551 + （-2）332 + 3153 58 (mod 165)，因此所求的整数x = 52 + 165t，tZ。由于这队士兵不超过170人，所以这队士兵有58人。3、判断同余方程是否有解?解：286=2143，433是质数，(143，443)=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号 原方程有解。四、证明题 1、设(a, m) = 1，d0是使a d 1 (mod m)成立的最小正整数，则() d0j(m)；()对于任意的i，j，0 i, j d0 - 1，i j，有a ia j (mod m)。 （1）证明：() 由Euler定理，d0 j(m)，因此，由带余数除法，有j(m) = qd0 + r，qZ，q 0，0 r d0。因此，由上式及d0的定义，利用欧拉定理得到1 (mod m)，即整数r满足 a r 1 (mod m)，0 r j。因为(a, m) = 1，所以 ai - j 0 (mod m)，0 i - j 1，(b, m) = 1，并且b a 1 (mod m)，b c 1 (mod m) （1）记d = (a, c)，则bd 1 (mod m)。 证明：由裴蜀恒等式知，存在整数x，y，使得ax + cy = d，显然xy 0，y 0，由式(1)知：1 b ax = b db -cy = b d(b c) -y b d (mod m)。若x 0，由式(1)知：1 b cy = b db -ax = b d(ba) -x b d (mod m)。3、设p是素数，pbn - 1，nN，则下面的两个结论中至少有一个成立：() pbd - 1对于n的某个因数d 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 2，则p 1 (mod 2)。由此及结论()，并利用同余的基本性质，得到p 1 (mod 2n)。初等数论练习题八一、单项选择题 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、（120）=360。2、7355的个位数字是3。3、同余方程3x5(mod14)的解是x11(mod14)。4、（）=1。5、-2。6、如果一个正整数具有6个正因数，问这个正整数最小是12。7、同余方程x3+x2-x-10(mod 5)的解是x1(mod5)。三、计算题 1、已知563是素数，判定方程x2 429 (mod 563)是否有解。解：把看成Jacobi符号,我们有-），故方程x2 429 (mod 563)有解。2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余为x1,2,3,4,6,8,9,12,13,16,18 (mod 23)；模23的所有的二次非剩余为x5,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，mZ，则1n2n3n4n12m22m（-2）2m（-1）2m 2+222m =2+24m =2+2(-1)m(mod 5)； 当m为奇数时，1n2n3n4n0(mod 5)； 当m为偶数时，1n2n3n4n4(mod 5)。 故当4n时，51n2n3n4n 。四、证明题 1、证明：若质数p2，则2P-1的质因数一定是2pk+1形。证明：设q是2-1的质因数，由于2-1为奇数， q2，（2，q）=1。由条件q|2p-1,即21（mod q）。设h是使得21（mod q）成立最小正整数，若1h 1，(a, m) = 1，x1, x2, , xj(m)是模m的简化剩余系，求：。其中x表示x的小数部分。解：设axi = mqi + ri，0 ri 3，p只能为p1(mod 4)且 ，只能是下列情况 或。2、求使12347!被35k整除的最大的k值。 解：k=2054.四、证明题 1、证明：设是一个质数，则存在唯一的一个正整数x，使得：证明：存在性：因为是一个素数，由Wilson定理我们有：，然而，所以，故存在，使得。唯一性：若还存在，则，注意到，所以是唯一的。2、已知9901是素数，试证：。 证明：由9901是素数，计算Legendre符号得： 所以17是模9901的平方非剩余，因此由Euler判别条件可知： 即 。3、证明：若p=10n-1是个质数，则。（提示：利用勒让德符号解决。） 说明：要证，只需证明，即证： 这样就转化为证明：。 证明：因为。 所以。 故：。4、设p=4n+3是质数，证明当q=2p+1也是质数时，梅森数Mp=2p-1不是质数。由此证明：23|（211-1），47|（223-1），503|（2251-1）。证明：由条件：q=2p+1=8n+7-1(mod 8)，从而：=1，即124n+32p （mod q)，于是q|（2