02013初等数论练习题及答案.doc

初等数论练****题一一、填空题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+12≡0(mod37)的解是x≡11(mod37)。5、不定方程18x-23y=100的通解是x=900+23t,y=700+18t tZ。.6、分母是正整数m的既约真分数的个数为_(m)_。7、18100被172除的余数是_256。8、= -1。9、若p是素数,则同余方程xp11(modp)的解数为p-1 。二、计算题1、解同余方程:3x211x200(mod105)。解:因105=357,同余方程3x211x200(mod3)的解为x1(mod3),同余方程3x211x380(mod5)的解为x0,3(mod5),同余方程3x211x200(mod7)的解为x2,6(mod7),故原同余方程有4解。作同余方程组:xb1(mod3),xb2(mod5),xb3(mod7),其中b1=1,b2=0,3,b3=2,6,由孙子定理得原同余方程的解为x13,55,58,100(mod105)。2、判断同余方程x2≡42(mod107)是否有解?故同余方程x2≡42(mod107)有解。3、求(127156+34)28除以111的最小非负余数。解:易知1271≡50(mod111)。由502≡58(mod111),503≡58×50≡14(mod111),509≡143≡80(mod111)知5028≡(509)3×50≡803×50≡803×50≡68×50≡70(mod111)从而5056≡16(mod111)。故(127156+34)28≡(16+34)28≡5028≡70(mod111)三、证明题1、已知p是质数,(a,p)=1,证明:(1)当a为奇数时,ap-1+(p-1)a≡0(modp);(2)当a为偶数时,ap-1-(p-1)a≡0(modp)。证明:由欧拉定理知ap-1≡1(modp)及(p-1)a≡-1(modp)立得(1)和(2)成立。2、设a为正奇数,n为正整数,试证≡1(mod2n+2)。……………(1)证明 设a=2m1,当n=1时,有a2=(2m1)2=4m(m1)11(mod23),即原式成立。设原式对于n=k成立,则有 1(mod2k+2)=1q2k+2,其中qZ,所以 =(1q2k+2)2=1q2k+31(mod2k+3),其中q是某个整数。这说明式(1)当n=k1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数,且1≤k≤p-1。证明:(-1)k(modp)。证明:设A=得:k!·A=(p-1)(p-2)…(p-k)≡(-1)(-2)…(-k)(modp)又(k!,p)=1,故A=(-1)k(modp)4、设p是不等于3和7的奇质数,证明:p6≡1(mod84)。说明:因为84=4×3×7,所以,只需证明:p6≡1(mod4)   p6≡1(mod3)    p6≡1(mod7) 同时成立即可。证明:因为84=4×3×7及p是不等于3和7的奇质数,所以(p,4)=1,(p,3)=1,(p,7)=1。由欧拉定理知:p(4)≡p2≡1(mod4),从而p6≡1(mod4)。同理可证:p6≡1(mod3)  p6≡1(mod7)。 故有p6≡1(mod84)。注:设p是不等于3和7的奇质数,证明:p6≡1(mod168)。(见赵继源p86)初等数论练****题二一、填空题1、(1000)=_16_;(除数函数:因数的个数)σ(1000)=_2340_.(和函数:所有因数的和)2、2010!的标准分解式中,、费尔马(Fermat)数是指Fn=+1,这种数中最小的合数Fn中的n=5。4、同余方程13x≡5(mod31)的解是x≡29(mod31)___5、分母不大于m的既约真分数的个数为(2)+(3)+…+(m)。6、设7∣(80n-1),则最小的正整数n=、使41x+15y=C无非负整数解的最大正整数C=、=、若p是质数,np1,则同余方程xn1(modp)、计算题1、试求被19除所得的余数。解:由2002≡7(mod19) 20022≡11(mod19) 20023≡1(mod19)又由20032004≡22004≡(22)1002≡1(mod3)可得:≡20023n+1≡(20023)n×2002≡7(mod19)2、解同余方程3x144x106x180(mod5)。解:由Fermat定理,x5x(mod5),因此,原同余方程等价于2x2x30(mod5)将x0,1,2(mo