初等数论练习题及答案

初等数论练习题一一、填空题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 tÎZ。.6、分母是正整数m的既约真分数的个数为_j(m)_。7、18100被172除的余数是_256。8、 =-1。9、若p是素数，则同余方程xp- 1º1(mod p)的解数为p-1。二、计算题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 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）。由50258（mod 111），50358×5014（mod 111），50914380（mod 111）知5028（509）3×50803×50803×5068×5070（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为正整数，试证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，其中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(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、(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是质数，n½p-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)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，求使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+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，1<a，b<s。则，其中M1是正整数。由pa1也是正整数知ps是合数，这与题设矛盾。故s也是一个素数。4、证明：若2p+ 1是奇素数，则(p!)2+ (-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、若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+2C.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(mod9)(2)a2010(mod9)(3)a的十进位表示的各位数字之和可被9整除(4)划去a的十进位表示中所有的数字9，所得的新数被9整除以上各条件中，成为9|a的充要条件的共有（C）。A.1个B.2个C.3个D.4个二、填空题1、(2010)=_4896_；(2010)=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除所得余数是_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是正整数，求的最大公约数。 解：设知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 (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=3×8，（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+yx+y，x+yx+y。此题把加法换成乘法又如何呢？ 证明：（1）设x=x+，0<1，y=y+，0<1。于是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< 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. 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是任意整数，则下列错误的是（A）Aacbc(mod mc)Bm|a-bC(a，m)=(b，m) Da=b+mt，tZ二、填空题 1、d(10010)=_32_，(10010)=_2880_。2、对于任意一个自然数n，为使自N起的n个相继自然数都是合数，可取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½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+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)1（mod 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×32)14+4035(102414+40)35(214+40)35(210×24+40)35(25+40)357235-172(mod73)四、证明题1、设a1， a2，L，am是模m的完全剩余系，证明： （1）当m为奇数时，a1+ a2+L+am0（mod 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(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，am+bm是模m的完全剩余系，那么也有(mod m)。联合上式与式(1)和式(2)，得到0(mod m)，这是不可能的，所以a1+b1，a2+b2，L，am+bm不能是模m的完全剩余系。4、证明：（1）2730x13-x；（2）24x(x+2)(25x2-1)；（3）504x9-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)(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 +nxB.mn，则my +nxC.（m，n）=1，则my +nx D.（m，n）=1，则mx+ny2、1×3×5××2003×2005×2007×2009×2011规范分解式中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、若3258×a恰好是一个正整数的平方，则a的最小值为362。请预览后下载！7、已知2011是一素数，则=_-1_。三、计算题1、求32008×72009×132010的个位数字。解：32008×72009×13201032008×（-3）2009×32010-32008+2009+2010-36027 -3×（32）30133(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)的一般解是 ， 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|。 证明：=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，z>0的整数解是且仅是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，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。即：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等式成立故对任何实数x，恒有x+x+=2x。2、证明：（1）当n为奇数时，3（2n+1）；（2）当n为偶数时，3（2n+1）。 证明：由2n+1（-1）n+1（mod 3）立得结论。3、证明：（1）当3n（n为正整数）时，7（2n-1）； （2）无论n为任何正整数，7（2n+1）。 证明：（1）设n=3m，则2n-1=8m-10（mod 7），即：7（2n-1）； （2）由于23m1（mod 7）得23m+12（mod 7），23m+1 +13（mod 7），23m+2 +15（mod 7）。 故无论n为任何正整数，7（2n+1）。4、设m0，n0，且m为奇数，证明：（2m-1，2n+1）=1。证明一：由m为奇数可知：2n+12mn+1，又有2m-12mn-1，于是存在整数x，y使得：（2n+1）x=2mn+1，(2m-1)y=2mn-1。从而（2n+1）x-(2m-1)y=2。这表明：（2m-1，2n+1）2由于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-p）d =2。 从而 d2，就有d=1或2。由因为m为奇数，所以d=1。即（2m-1，2n+1）=1。 注：我们已证过：记Mn=2n- 1，对于正整数a，b，有(Ma，Mb)= M(a，b)。请预览后下载！显然当ab，a，b为质数时，(Ma，Mb)=1。初等数论练习题七一、单项选择题 1、设a和b是正整数，则=（A）A1BaCbD(a，b)2、176至545的正整数中，13的倍数的个数是（B）A27 B28C29D303、200!中末尾相继的0的个数是（A）A49 B50C51D524、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（ B）A2的倍数B3的倍数C4的倍数D5的倍数5、设n是正整数，下列选项为既约分数的是（A）ABCD二、填空题 1、314162被163除的余数是_1_。（欧拉定理）2、同余方程3x5(mod13)的解是x6(mod13)。3、=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 = uuÎZ，t = 41 - 3v请预览后下载！z = vvÎZ，消去t得x = 41 - 3v- 2uy = uz = vu，vÎZ。由此得原方程的全部正整数解为(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 = 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。由于这队士兵不超过170人，所以这队士兵有58人。3、判断同余方程是否有解?解：286=2×143，433是质数，(143，443)=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号原方程有解。四、证明题 1、设(a，m) = 1，d0是使adº1 (mod m)成立的最小正整数，则() d0½j(m)；()对于任意的i，j，0 £i，j £d0- 1，i¹j，有aiaj (mod m)。 （1）证明：() 由Euler定理，d0£j(m)，因此，由带余数除法，有j(m) = qd0+r，qÎZ，q>0，0 £r < d0。请预览后下载！因此，由上式及d0的定义，利用欧拉定理得到1 º(mod m)，即整数r满足arº 1(mod m)，0 £r < d0 。由d0的定义可知必是r = 0，即d0½j(m)。() 若式(1)不成立，则存在i，j，0 £i，j £d0- 1，i¹j，使aiºaj (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，并且baº 1(mod m)，bcº 1(mod m) （1）记d = (a，c)，则bdº 1 (mod m)。证明：由裴蜀恒等式知，存在整数x，y，使得ax+cy = d，显然xy< 0。若x>0，y<0，由式(1)知：1ºbax = bdb-cy = bd(bc)-yºbd (mod m)。若x<0，y>0，由式(1)知：1ºbcy = bdb-ax = bd(ba)-xºbd (mod m)。3、设p是素数，p½bn-1，nÎN，则下面的两个结论中至少有一个成立：() p½bd-1对于n的某个因数d<n成立；() pº1 ( mod n )。若2n，p>2，则()中的mod n可以改为mod 2n。证明：记d = (n，p- 1)，由bnº 1，bp- 1º 1(mod p)，及第2题有bdº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)。初等数论练习题八一、单项选择题 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，9C.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)的解是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 23)；模23的所有的二次非剩余为xº5，7，10，11，14，15，17，19，20，21，22 (mod 23)。3、试求出所有正整数n ，使得1n2n3n4n 能被5整除。 解：若n为奇数，则1n2n3n4nº1n2n（-2）n（-1）nº0 (mod 5)； 若n=2m，mZ，则1n2n3n4nº12m22m（-2）2m（-1）2mº2+2×22m=2+2×4m=2+2×(-1)m(mod 5)； 当m为奇数时，1n2n3n4nº0(mod 5)； 当m为偶数时，1n2n3n4nº4(mod 5)。 故当4n时，51n2n3n4n。四、证明题 1、证明：若质数p>2，则2P-1的质因数一定是2pk+1形。证明：设q是2-1的质因数，由于2-1为奇数，q2，（2，q）=1。由条件q|2p-1，即21（mod q）。设h是使得21（mod 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+1kZ。2、设（m，n）=1，证明：mj(n)+nj(m)1 (mod mn)。 证明：因为（m，n）=1，所以由欧拉定理知：nj(m)1 (mod m)，mj(n)1 (mod n)于是mj(n)+nj(m)1 (mod m)，mj(n)+nj(m)1 (mod n)。 又因为（m，n）=1，所以mj(n)+nj(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+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，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除的余数是12、同余方程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×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的完全剩余系，因此对于任意的i（1 £i £m），axi+b一定与且只与某个整数j（1 £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) = (n-a1) + (n-a2) +L+ (n-aj(n)，2(a1+a2+L+aj(n) = nj(n)，因此：a1+a2+L+aj(n) =nj(n)。4、设m>1，(a，m) = 1，x1，x2，¼，xj(m)是模m的简化剩余系，求：。其中x表示x的小数部分。解：设axi = mqi+ri，0 £ri < m，由xi通过模m的简化剩余系知：axi也通过模m的简化剩余系，从而ri通过模m的最小非负简化剩余系，于是：。四、证明题1、证明：设a是有理数，b是使ba为整数的最小正整数，若c和ca都是整数，则bc。(提示：利用带余数除法解决。)证明：设c=bq+r，0rb，qZ，则ca=(ba)q+ra。因为ca，baZ，所以raZ，于是ra=0，由a0得r=0。故bc。2、设p是素数，证明：() 对于一切整数x，xp- 1-1 º (x-1) (x-2)L(x-p+ 1) (mod p)；() (p-1)! º-1 (mod p)。 证明：() xp- 1-1 º 0 (mod p)有解xº 1，2，L，p-1 (mod p)，故对于一切整数x，xp- 1-1 º (x-1) (x-2)L(x-p+ 1) (mod p)；。 () 在()中令x = p。3、证明：若2n，p是奇质数，pan-1，则。 证明：由pan-1知：anº1(mod p)。又（p，a）=1得到an+1º a(mod p)。请预览后下载！ 因为2n，所以，即x2ºa(mod p)有解。故 。4、证明：若p=4m+1是一质数，则。证明：。5、设p是奇质数，pº 1 (mod 4)，则：º-1 (mod p)解由Wilson定理有：注：（1）设p为质数且p4m+1，则同余方程的解是。（2）设p为质数且p4m+1，若且唯若存在一个正整数a，使得a2-1 (mod p)。初等数论练习题十一、单项选择题1、设p是大于1的整数，如果所有不大于的质数都不能整除p，则p一定是（ A ）。A.素数B.合数C.奇数D. 偶数2、两个质数p，q，满足p+q=99，则的值是（B）A.9413 B.C.D.3、2010！的规范分解式中，7的最高幂指数为（C）A331B332C333D3344、n为正整数，若2n+1为质数，则n是（D）A质数B合数C1 D2k(k为非负整数)5、当n2时，欧拉函数j(n)一定是（ B ）。A奇数 B偶数C1 D2二、填空题1、如果p是质数，a是整数，则有（a，p）=1或者pa。请预览后下载！2、设p是奇质数，(a，p)=1，则a是模p的平方非剩余的充要条件是3、从1000开始到2010结束的所有整数中13的倍数有78个。4、2756839-1的末位数是7。5、不定方程ax+by=c有解的充要条件是(a，b)½c。6、写出模12的一个最小非负简化系，要求每项都是7的倍数，此简化系为7，35，49，77。7、已知563是质数，则=-1。三、计算题1、若3是质数p的平方剩余，问p是什么形式的质数？解： 由二次互反律，注意到p>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，即1ºº24n+3º2p （mod q)，于是q|（2p-1）。故：梅森数Mp=2p-1不是质数。当n=2，n=5，n=62时立得：23|（211-1），47|（223-1），503|（2251-1）。注：此题还可以进一步表述为：设p=4n+3是质数，证明：2p+1是质数的充要条件是2p1(mod 2p+1)。必要性已证。下证充分性：若2p1(mod 2p+1)，则pj(2p+1)，因此必有j(2p+1)=p 或2p 。由于j(2p+1)为偶数，故j(2p+1)=2p 。5、证明：设p是大于5的质数，则。说明：只需证明：p(p+1)|(p-1)!+p+1。又因为(p，p+1)=1，所以需证：p|(p-1)!+p+1 与(p+1)|(p-1)!+p+1同时成立即可。请预览后下载！证明：由Wilson定理：知：p|(p-1)!+p+1；又p是大于5的质数，可设p+1=2n，其中2np-1，于是 (p+1)|(p-1)!+p+1。故：p(p+1)|(p-1)!+p+1。即。 （注：可编辑下载，若有不当之处，请指正，谢谢!） 请预览后下载！