初等数论练习题答案.docx

初等数论练习题一 一、填空题 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+12≡0(mod37)的解是x≡11(mod37)。 5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t t Z。. 6、分母是正整数m的既约真分数的个数为_(m)_。 7、18100被172除的余数是_256。 8、65 =-1。 103 、若 是素数，则同余方程 x p11(modp)的解数为p-1 。 9p 二、计算题 1、解同余方程：3x2 11x200(mod105)。 解：因105=3 57， 同余方程3x2 11x 20 0(mod3) 的解为x 1(mod3) ， 同余方程3x2 11x 38 0(mod5) 的解为x 0，3(mod5) ， 同余方程3x2 11x 20 0(mod7) 的解为x 2，6(mod7) ， 故原同余方程有  4解。 作同余方程组：x 其中  b1(mod3)，x b1=1，b2=0  b2(mod5)，x ，3，b3=2，6，  b3(mod7)  ， 由孙子定理得原同余方程的解为  x  13，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，明： a （1）当a奇数，ap-1+(p-1)≡0(modp)； 明：由欧拉定理知 p-1 a≡-1(modp)立得（1）和（2）建立。 a≡1(modp)及(p-1) 2、a正奇数，n正整数，a2n ≡1(mod2n+2)。?????（1） 明 a=2m1，当n=1，有 a2=(2m1)2=4m(m 1) 11(mod23)，即原式建立。 原式于n=k建立，有 a2k 1(mod2k+2) a2k =1q2k+2， 其中qZ，所以 a2k1 =(1 q2k+2)2=1 q2k+3 1(mod2k+3)， 其中q是某个整数。明式(1)当n=k 1也建立。 由法知原式所有正整数n建立。 、 是一个素数，且 ≤ ≤ p-1 。明： k （-1 ）k(modp)。 3p 1 k Cp1 明：A=Ckp1 （p 1）(p 2)(p k) 得： k! k! ·A=（p-1）(p-2) ?（p-k）≡（-1）(-2) ?（-k）(modp) 又（k!，p）=1，故A= k （ -1 k p ) Cp1 ） (mod 6 4、p是不等于3和7的奇数，明：p≡1(mod84)。 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、d(1000)=_16_；σ(1000)=_2340_. 2、2010!的准分解式中，数11的次数是199__. n 3、(Fermat)数是指Fn=22+1,种数中最小的合数Fn中的n=5。 4、同余方程13x≡5(mod31)的解是x≡29(mod31)___ 5、分母不大于m的既真分数的个数(2)+(3)+?+(m)。 6、7∣(80n-1),最小的正整数n=_6__. 7、使41x+15y=C无非整数解的最大正整数 C=__559__. 8、46=_1__. 101 9、若p是数，np 1，同余方程xn 1(modp)的解数n. 二、算 1、求200220032004 被19除所得的余数。 解：由2002≡7(mod19) 2002 2≡11(mod19) 20023≡1(mod19) 又22004≡（22）1002≡1(mod3)可得： 200220032004 ≡20023n+1≡(20023