初等数论练习题答案

初等数论练习题一

一、填空题

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(mod 37)的解是x≡11(mod 37)。

5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t tZ。.

6、分母是正整数m的既约真分数的个数为_(m)_。

7、18100被172除的余数是_256。

8、10365 =-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、判断同余方程x2≡42(mod 107)是否有解？

11074217271071107713231071107311072107710731072107732107422110721721107213)(••）（）（）（）（），（）（）（）（），（）（））（）（（）（解：

故同余方程x2≡42(mod 107)有解。

3、求（127156+34）28除以111的最小非负余数。 . .

2 / 25 解：易知1271≡50（mod 111）。

由502 ≡58（mod 111）, 503 ≡58×50≡14（mod 111），509≡143≡80（mod 111）知5028 ≡（509）3×50≡803×50≡803×50≡68×50≡70（mod 111）

从而5056 ≡16（mod 111）。

故（127156+34）28≡（16+34）28 ≡5028≡70（mod 111）

三、证明题

1、已知p是质数，（a,p）=1，证明：

（1）当a为奇数时，ap-1+(p-1)a≡0 (mod p)；

（2）当a为偶数时，ap-1-(p-1)a≡0 (mod p)。

证明：由欧拉定理知ap-1≡1 (mod p)与(p-1)a≡-1 (mod p)立得（1）和（2）成立。

2、设a为正奇数，n为正整数，试证n2a≡1(mod 2n+2)。 …………… （1）

证明 设a = 2m1，当n = 1时，有

a2 = (2m1)2 = 4m(m1)11 (mod 23)，即原式成立。

设原式对于n = k成立，则有 ka21 (mod 2k+2) ka2= 1q2k+2，

其中qZ，所以 12ka= (1q2k+2)2 = 1q2k+31 (mod 2k+3)，

其中q是某个整数。这说明式(1)当n = k1也成立。

由归纳法知原式对所有正整数n成立。

3、设p是一个素数，且1≤k≤p-1。证明：kp1C （-1 ）k(mod p)。

证明：设A=!)()2(1C1kkpppkp）（ 得：

k!·A =（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(mod p)

又（k!，p）=1，故A = kp1C （-1 ）k(mod p)

4、设p是不等于3和7的奇质数，证明：p6≡1(mod 84)。

说明：因为84=4×3×7，所以，只需证明：

p6≡1(mod 4) p6≡1(mod3) p6≡1(mod 7) 同时成立即可。

证明：因为84=4×3×7与p是不等于3和7的奇质数，所以 . .

3 / 25 （p，4）=1，（p，3）=1，（p，7）=1。

由欧拉定理知：p(4)≡p2≡1(mod 4)，从而 p6≡1(mod 4)。

同理可证：p6≡1(mod3) p6≡1(mod 7)。 故有p6≡1(mod 84)。

注：设p是不等于3和7的奇质数，证明：p6≡1(mod 168)。（见继源p86）

初等数论练习题二

一、填空题

1、d(1000)=_16_；σ(1000)=_2340_.

2、2010!的标准分解式中，质数11的次数是199__.

3、费尔马(Fermat)数是指Fn=n22+1,这种数中最小的合数Fn中的n=5。

4、同余方程13x≡5(mod 31)的解是x≡29(mod 31)___

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 (mod p) 的解数为n .

二、计算题

1、试求200420032002被19除所得的余数。

解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19)

又由20032004≡22004≡（22）1002≡1 (mod 3)可得：

200420032002≡20023n+1≡(20023)n×2002≡7(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，所以有欧拉定理知5(21)≡1(mod 21)。

又由于(21)=12，所以x|12，而12的所有正因数为1,2,3,4,6,12。

于是x应为其中使 5x 1 (mod 12)成立的最小数，经计算知：x=6。

三、证明题 . .

4 / 25 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

Mpabasss911091)10(9110111，其中M＞1是正整数。

由pa＞1也是正整数知ps是合数，这与题设矛盾。故s也是一个素数。

4、证明：若2p 1是奇素数，则 (p!)2 (1)p 0(mod 2p 1)。

证明：由威尔逊定理知 1  (2p)! = p!(p 1)(2p)  (1)p(p!)2(mod 2p 1)，

由此得(p!)2 (1)p 0(mod 2p 1)。

5、设p是大于5的质数，证明：p4≡1(mod 240)。（提示：可由欧拉定理证明）

证明：因为240=23×3×5，所以只需证：p4≡1(mod 8)，p4≡1(mod 3)，p4≡1(mod 5)即可。事实上，由(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-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 D.a=3n+1,b=5n+2

3、使方程6x+5y=C无非负整数解的最大整数C是（ A ）。

A.19 B.24 C.25 D.30

4、不是同余方程28x≡21(mod 35)的解为（ D ）。

A.x≡2(mod 35) B. x≡7(mod 35) C. x≡17(mod 35) D. x≡29(mod 35)

5、设a是整数，(1)a≡0(mod9) (2)a≡2010(mod9) . .

5 / 25 (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、整数n>1，且(n-1)!+1≡0(mod n),则n为素数。

6、3103被11除所得余数是_5_。

7、9760=_-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是正整数，求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 (mod m)成立的最小自然数x。

解：因为（18,77）=1，所以有欧拉定理知18(77)≡1(mod 77)。

又由于(77)=60，所以x|60，而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30,

60。