初等数论练习题答案.doc

上传人:good****022 文档编号:116524395 上传时间:2022-07-05 格式:DOC 页数:26 大小:621.06KB
返回 下载 相关 举报
初等数论练习题答案.doc_第1页
第1页 / 共26页
初等数论练习题答案.doc_第2页
第2页 / 共26页
初等数论练习题答案.doc_第3页
第3页 / 共26页
点击查看更多>>
资源描述
初等数论练习题一一、填空题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
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 机械制造 > 机械理论


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!