02013初等数论练习题及答案

初等数论练习题一一、填空题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+18ttZ。.6、分母是正整数m的既约真分数的个数为_(m)_。7、18100被172除的余数是_256。8、10365=-1。9、若p是素数，则同余方程xp11(modp)的解数为p-1。二、计算题1、解同余方程：3x211x200(mod105)。解：因105=357，同余方程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b2(mod5)，xb3(mod7)，其中b1=1，b2=0，3，b3=2，6，由孙子定理得原同余方程的解为x13，55，58，100(mod105)。2、判断同余方程x2≡42(mod107)是否有解？11074217271071107713231071107311072107710731072107732107422110721721107213)(）（）（）（）（），（）（）（）（），（）（））（）（（）（解：故同余方程x2≡42(mod107)有解。3、求（127156+34）28除以111的最小非负余数。2解：易知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为正整数，试证n2a≡1(mod2n+2)。……………（1）证明设a=2m1，当n=1时，有a2=(2m1)2=4m(m1)11(mod23)，即原式成立。设原式对于n=k成立，则有ka21(mod2k+2)ka2=1q2k+2，其中qZ，所以12ka=(1q2k+2)2=1q2k+31(mod2k+3)，其中q是某个整数。这说明式(1)当n=k1也成立。由归纳法知原式对所有正整数n成立。3、设p是一个素数，且1≤k≤p-1。证明：kp1C（-1）k(modp)。证明：设A=!)()2(1C1kkpppkp）（得：k!·A=（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(modp)又（k!，p）=1，故A=kp1C（-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的奇质数，所以3（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!的标准分解式中，质数11的次数是199__.3、费尔马(Fermat)数是指Fn=n22+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、10146=_1__.9、若p是质数，np1，则同余方程xn1(modp)的解数为n.二、计算题1、试求200420032002被19除所得的余数。解：由2002≡7(mod19)20022≡11(mod19)20023≡1(mod19)又由20032004≡22004≡（22）1002≡1(mod3)可得：200420032002≡20023n+1≡(20023)n×2002≡7(mod19)2、解同余方程3x144x106x180(mod5)。解：由Fermat定理，x5x(mod5)，因此，原同余方程等价于2x2x30(mod5)将x0，1，2(mod5)分别代入上式进行验证，可知这个同余方程解是x1(mod5)。3、已知a=5，m=21，求使ax1(modm)成立的最小自然数x。解：因为（5，21）=1，所以有欧拉定理知5(21)≡1(mod21)。又由于(21)=12，所以x|12，而12的所有正因数为1，2，3，4，6，12。于是x应为其中使5x1(mod12)成立的最小数，经计算知：x=6。4三、证明题1、试证13|(54m+46n+2000)。(提示：可取模13进行计算性证明)证明：54m+46n+2000252m+642n+2000（-1）2m+（-1）2n+200020020(mod13)。2、证明Wilson定理的逆定理：若n1，并且(n1)!1(modn)，则n是素数。证明：假设n是合数，即n=n1n2，1n1n，由题设易知(n1)!1(modn1)，得01(modn1)，矛盾。故n是素数。3、证明：设ps表示全部由1组成的s位十进制数，若ps是素数，则s也是一个素数。证明：假设s是合数，即s=ab，1a，bs。则Mpabasss911091)10(9110111，其中M＞1是正整数。由pa＞1也是正整数知ps是合数，这与题设矛盾。故s也是一个素数。4、证明：若2p1是奇素数，则(p!)2(1)p0(mod2p1)。证明：由威尔逊定理知1(2p)!=p!(p1)(2p)(1)p(p!)2(mod2p1)，由此得(p!)2(1)p0(mod2p1)。5、设p是大于5的质数，证明：p4≡1(mod240)。（提示：可由欧拉定理证明）证明：因为240=23×3×5，所以只需证：p4≡1(mod8)，p4≡1(mod3)，p4≡1(mod5)即可。事实上，由(8)=4，(3)=2，(5)=4以及欧拉定理立得结论。初等数论练习题三一、单项选择题1、若n＞1，(n)=n-1是n为质数的（C）条件。A.必要但非充分条件B.充分但非必要条件C.充要条件D.既非充分又非必要条件2、设n是正整数，以下各组a，b使ab为既约分数的一组数是（D）。A.a=n+1，b=2n-1B.a=2n-1，b=5n+2C.a=n+1，b=3n+1D.a=3n+1，b=5n+23、使方程6x+5y=C无非负整数解的最大整数C是（A）。A.19B.24C.25D.304、不是同余方程28x≡21(mod35)的解为（D）。A.x≡2(mod35)B.x≡7(mod35)C.x≡17(mod35)D.x≡29(mod35)55、设a是整数，(1)a≡0(mod9)(2)a≡2010(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、数20100C的标准分解式中，质因数7的指数是_3。3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。4、同余方程24x≡6(mod34)的解是x1≡13(mod34)x2≡30(mod34)_。5、整数n1，且(n-1)!+1≡0(modn)，则n为素数。6、3103被11除所得余数是_5_。7、9760=_-1_。三、计算题1、判定(ⅰ)2x3x23x10(mod5)是否有三个解；(ⅱ)x62x54x230(mod5)是否有六个解？解：(ⅰ)2x3x23x10(mod5)等价于x33x24x30(mod5)，又x5x=(x33x24x3)(x23x5)+(6x212x15)，其中r(x)=6x212x15的系数不都是5的倍数，故原方程没有三个解。(ⅱ)因为这是对模5的同余方程，故原方程不可能有六个解。2、设n是正整数，求1223212C,,C,Cnnnn的最大公约数。解：设12122321212232122CCC)C,,C,(Cnnnnnnnnnd，由知d22n1，设2k|n且2k+1|n，即2k+1||n，则由2k+1||1122112C2C2C|ininknin及，i=3，5，，2n1得d=2k+1。3、已知a=18，m=77，求使ax1(modm)成立的最小自然数x。解：因为（18，77）=1，所以有欧拉定理知18(77)≡1(mod77)。又由于(77)=60，所以x|60，而60的所有正因数为1，2，3，4，5，6，10，12，615，20，30，60。于是x应为其中使18x1(mod77)成立的最小数，经计算知：x=30。四、证明题1、若质数p≥5，且2p+1是质数，证明：4p+1必是合数。证明：因为质数p≥5，所以（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的质数，证明：p2≡q2(mod24)。证明：因为24=3×8，（3，8）=1，所以只需证明：p2≡q2(mod3)p2≡q2(mod8)同时成立。事实上，由于（p，3）=1，（q，3）=1，所以p2≡1(mod3)，q2≡1(mod3)，于是p2≡q2(mod3)，由于p，q都是奇数，所以p2≡1(mod8)，q2≡1(mod8)，于是p2≡q2(mod8)。故p2≡q2(mod24)。3、若x，y∈R+，（1）证明：[xy]≥[x][y]；（2）试讨论{xy}与{x}{y}的大小关系。注：我们知道，[xy]≥[x]+[y]，{x+y}≤{x}+{y}。此题把加法换成乘法又如何呢？证明：（1）设x=[x]+α，0≤α1，y=[y]+β，0≤β1。于是xy=[x][y]+β[x]+α[y]+αβ所以[xy]=[x][y]+[β[x]+α[y]+αβ]≥[x][y]。（2）{xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。当x=y=21时，{xy}={x}{y}=41；当x=23，y=21时，{xy}=43，{x}{y}=41，此时{xy}＞{x}{y}；当x=-21，y=-31时，{xy}=61