02013初等数论练习题及答案

初等数论练习题一

一、填空题

1、τ； ϕ2、设a ，n 是大于1的整数，若a n -1是质数，则

3、模9的绝对最小完全剩余系是4、同余方程9x+12≡0(mod 37)的解是。

5、不定方程18x-23y=100的通解是.

6、分母是正整数m 的既约真分数的个数为__。

7

8、 ⎛65⎫⎪ 。 ⎝103⎭

9、若p 是素数，则同余方程x p - 1 ≡1(mod p

) 二、计算题

1、解同余方程：3x 2+11x -20 ≡ 0 (mod 105)。

解：因105 = 3⋅5⋅7，

同余方程3x 2+11x -20 ≡ 0 (mod 3)的解为x ≡ 1 (mod 3)，

同余方程3x 2+11x -38 ≡ 0 (mod 5)的解为x ≡ 0，3 (mod 5)，

同余方程3x 2+11x -20 ≡ 0 (mod 7)的解为x ≡ 2，6 (mod 7)，

故原同余方程有4解。

作同余方程组：x ≡ b 1 (mod 3)，x ≡ b 2 (mod 5)，x ≡ b 3 (mod 7)，

其中b 1 = 1，b 2 = 0，3，b 3 = 2，6，

由孙子定理得原同余方程的解为x ≡ 13，55，58，100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解？

237）（）[**************]

3-1107-17-1107-1 ∙∙[1**********]22 （）=-1，（）=（-1）=-（）=1，（）=（-122）=-（）=-[1**********]777

42∴（）=11072⨯3⨯7(42) ≡（）=（

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

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

解：易知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 为奇数时，a p-1+(p-1)≡0 (mod p)；

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

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

2、设a 为正奇数，n 为正整数，试证a 2n a a a

≡1(mod 2n+2) 。 …………… （1）

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

a 2 = (2m + 1)2 = 4m (m + 1) + 1 ≡ 1 (mod 23) ，即原式成立。

设原式对于n = k 成立，则有

其中q ∈Z ，所以 a 2k +1a 2k ≡ 1 (mod 2k + 2) ⇒a 2= 1 + q 2k + 2， k = (1 + q 2k + 2) 2 = 1 + q '2k + 3 ≡ 1 (mod 2k + 3) ，

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

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

k 3、设p 是一个素数，且1≢k ≢p-1。证明：C k

p -1 ≡ （-1 ）(mod p ) 。

（p -1）(p -2) (p -k ) 证明：设A=C k

p -1= 得： k !

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

k 又（k! ，p ）=1，故A = C k ≡ （-1 ）(mod p ) p -1

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

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

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

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

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

由欧拉定理知：p ϕ(4)≡p 2≡1(mod 4)，从而 p 6≡1(mod 4)。

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

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

初等数论练习题二

一、填空题

1、τ；（除数函数：因数的个数）σ（和函数：所有因数的和） 2、2010! 的标准分解式中，质数11的次数是3、费尔马(Fermat)数是指Fn=22+1，这种数中最小的合数Fn 中的。

4、同余方程13x ≡5(mod 31)的解是5、分母不大于m 的既约真分数的个数为6、设7∣(80n -1) ，则最小的正整数7、使41x+15y=C无非负整数解的最大正整数8、⎛ 46⎫⎪⎝101⎭n

9、若p 是质数，n ∣p - 1，则同余方程x n ≡ 1 (mod p ) 的解数为二、计算题

20031、试求20022004被19除所得的余数。

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

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

[1**********]4≡20023n+1≡(20023) n ×2002≡7(mod 19)

2、解同余方程3x 14 + 4x 10 + 6x - 18 ≡ 0 (mod 5)。

解：由Fermat 定理，x 5 ≡ x (mod 5)，因此，原同余方程等价于2x 2 + 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 应为其中使 5 x ≡ 1 (mod 12)成立的最小数，经计算知：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 = n 1n 2，1

0 ≡ -1 (mod n 1) ，矛盾。故n 是素数。

3、证明：设p s 表示全部由1组成的s 位十进制数，若p s 是素数，则s 也是一个素数。 证明：假设s 是合数，即s=ab，1

10s -1(10a ) b -110a -1 p s =11 1===⋅M ，其中M ＞1是正整数。 999s

由p a ＞1也是正整数知p s 是合数，这与题设矛盾。故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的质数，证明：p 4≡1(mod 240)。（提示：可由欧拉定理证明）

证明：因为240=23×3×5，所以只需证：p 4≡1(mod 8)，p 4≡1(mod 3)，p 4≡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 使为既约分数的一组数是（ 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 b a

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)

(3)a的十进位表示的各位数字之和可被9整除

(4)划去a 的十进位表示中所有的数字9，所得的新数被9整除

以上各条件中，成为9|a的充要条件的共有（ C ）。

A.1个 B.2个 C.3个 D.4个

二、填空题

1、σ；ϕ

202、数C 100的标准分解式中，质因数7的指数是。

3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是。

4、同余方程24x ≡6(mod34)的解是≡13(mod34) x ≡30(mod34)_。

5、整数n>1，且(n-1)!+1≡0(mod n)，则n

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

7、 ⎛60⎫⎪。 ⎝97⎭

三、计算题

1、判定 (ⅰ) 2x 3 - x 2 + 3x - 1 ≡ 0 (mod 5)是否有三个解；

(ⅱ) x 6 + 2x 5 - 4x 2 + 3 ≡ 0 (mod 5)是否有六个解？

解：(ⅰ) 2x 3 - x 2 + 3x - 1 ≡ 0 (mod 5)等价于x 3 - 3x 2 + 4x - 3 ≡ 0 (mod 5)，又x 5 - x = (x 3 - 3x 2 + 4x - 3)(x 2 + 3x + 5) + (6x 2 - 12x + 15)，其中r (x ) = 6x 2 - 12x + 15的系数不都是5的倍数，故原方程没有三个解。

(ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。

32n -12、设n 是正整数，求C 1 的最大公约数。 2n , C 2n , , C 2n

132n -1132n -12n -1 解：设(C2n , C 2n , , C 2n ) =d ，由C 2n +C 2n + +C 2n =2知d ∣22n -1，

|n ，即2k +1||n ， 设2k |n 且2k+1/

则由2k +1||C 2n 及2

11k +1|C i 2n =2n i -1C 2n -1，i = 3， 5， ， 2n - 1 得d = 2k + i 。

3、已知a=18，m=77，求使a x ≡ 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。

于是x 应为其中使18x ≡ 1 (mod 77)成立的最小数，经计算知：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的质数，证明：p 2≡q 2(mod 24)。

证明：因为24=3×8，（3，8）=1，所以只需证明：

p 2≡q 2(mod 3) p 2≡q 2(mod 8)同时成立。

事实上， 由于（p ，3）=1，（q ，3）=1，所以p 2≡1(mod 3) ， q 2≡1(mod 3)， 于是p 2≡q 2(mod 3)，由于p ，q 都是奇数，所以p 2≡1(mod 8) ， q 2≡1(mod 8)，

于是p 2≡q 2(mod 8)。故p 2≡q 2(mod 24)。

3、若x ，y ∈R ，

（1）证明：[xy]≣[x][y]；

（2）试讨论{xy}与{x}{y}的大小关系。

注：我们知道，[x + y ] ≣[x ]+ [y ]，{x+y}≢{x }+{y }。此题把加法换成乘法又如何呢？ 证明：（1）设x=[x]+α，0≢α

xy=[x][y]+β[x]+α[y]+αβ

所以[xy]= [x][y]+ [β[x]+α[y]+αβ] ≣[x][y]。

（2）{xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。

当x=y=+ 11时，{xy}={x}{y}=； 24

3131 当x=， y=时，{xy}=，{x}{y}=，此时{xy}＞{x}{y}； 2244

1111 当x=-，y=-时，{xy}=，{x}{y}=，此时{xy}＜{x}{y}。 2363

c c 4、证明：存在一个有理数，其中d

对于k=1，2，…. ，99均成立。

证明：由（73，100）=1以及裴蜀恒等式可知：存在整数c ，d ，使得

73d-100c=1 从而73kc k (73d -100c ) k k -==，由k

0＜

设[k 73kc 1k -＜ 100d d d c d ]=n，则kc ＜n+1=n +1d ，于是 d

73kc +1n +1k ＜d =n+1， ≢100d d

73故 [k ]= n =[k 100c d ]。

初等数论练习题四

一、单项选择题

1、若F n =22+1是合数，则最小的n 是( D ) 。

A. 2 B. 3 C. 4 D. 5

2、记号b a ‖a 表示b a ｜a ，但b a+1/|a. 以下各式中错误的一个是( B ) 。

A. 218‖20! B. 105‖50! C. 119‖100! D. 1316‖200!

3、对于任意整数n ，最大公因数(2n+1，6n-1) 的所有可能值是( A ) 。

A. 1 B. 4 C. 1或2 D. 1，2或4

4、设a 是整数，下面同余式有可能成立的是( C ) 。

A. a2≡2 (mod 4) B. a2≡5 (mod 7) C. a2≡5 (mod 11) D. a2≡6 (mod 13)

5、如果a ≡b(mod m)，c 是任意整数，则下列错误的是（ A ）

A ．ac ≡bc(mod mc)

二、填空题

1、，φ。

2、对于任意一个自然数n ，为使自N 起的n 个相继自然数都是合数，可取N=3、为使3n-1与5n+7的最大公因数达到最大可能值，整数n 应满足条件

4、在5的倍数中，选择尽可能小的正整数来构成模12的一个简化系，则这组数是5、同余方程26x+1≡33 (mod 74)的解是≡24(mod74) x ≡61(mod74)_。

n B ．m|a-b C ．(a，m)=(b，m) D ．a=b+mt，t ∈Z

6、不定方程5x+9y=86的正整数解是7、 ⎛54⎫⎪。 ⎝89⎭

三、计算题

1、设n 的十进制表示是13xy 45z ，若792∣n ，求x ，y ，z 。

解：因为792 = 8⋅9⋅11，故792∣n ⇔ 8∣n ，9∣n 及11∣n 。

我们有8∣n ⇔ 8∣45z ⇒ 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。

⎧x +y +1=a 这样得到四个方程组：⎨ 3-y +x =b ⎩

其中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，

∴ 340≡1(mod 100) ∴ 3406=(340) 10·36≡(32) 2·32≡-19×9≡-171≡29(mod 100) ∴ 末二位数为29。

3、求(214928+40)35被73除所得余数。

解：(214928+40)35≡(3228+40)35≡[(32×32) 14+40]35 ≡(102414+40)35 ≡(214+40)35 ≡(210

×24+40)35 ≡(25+40)35 ≡7235 ≡-1≡72(mod 73)

四、证明题

1、设a 1， a 2， ， a m 是模m 的完全剩余系，证明：

（1）当m 为奇数时，a 1+ a2+ + a m ≡0（mod m）；

（2）当m 为偶数时，a 1+ a2+ + a m ≡m （mod m）。 2

证明：因为{1， 2， ， m }与{a 1， a 2， ， a m }都是模m 的完全剩余系，所以

∑a i ≡∑i =

i =1i =1m m m (m +1) (mod m ) 。 2

m m +1m (m +1) m (m +1) ∈Z 即得：m （1）当m 为奇数时，由，故∑a i =≡0(mod m ) 。 222i =1

m

（2）当m 为偶数时，由（m ，m+1）=1即得：∑a i =

i =1m (m +1) m ≡(mod m ) 。 22

ϕ（m ）

2、证明：若m ＞2，a 1， a 2， ， a ϕ(m)是模m 的任一简化剩余系，则 ∑a

i =1i ≡0(modm ).

证明：若a 1， a 2， ， a ϕ(m)是模m 的一个简化剩余系，则m-a 1， m-a 2， ， m-a ϕ(m)

ϕ（m ）

也是模m 的一个简化剩余系，于是：

ϕ（m ）

i =1∑a ≡∑(m -a ) (modm ). i i i =1i =1ϕ(m ) 从而：2∑a i ≡m ϕ(m )(modm ). 又由于m ＞2，ϕ(m ) 是偶数。故：ϕ（m ）i =1∑a i ≡m ϕ（m ）2≡0(modm ).

3、设m > 0是偶数，{a 1， a 2， ， a m }与{b 1， b 2， ， b m }都是模m 的完全剩余系，证明：{a 1 + b 1， a 2 + b 2， ， a m + b m }不是模m 的完全剩余系。

证明：因为{1， 2， ， m }与{a 1， a 2， ， a m }都是模m 的完全剩余系，所以

∑a i ≡∑i =

i =1i =1m m m (m +1) m ≡(mod m ) 。 (1) 22

同理 ∑b i ≡

i =1m m (mod m ) 。 (2) 2

如果{a 1 + b 1， a 2 + b 2， ， a m + b m }是模m 的完全剩余系，那么也有

m ∑(a i +b i ) ≡2(mod m ) 。 m

i =1

联合上式与式(1)和式(2)，得到 0≡m m m +≡(mod m ) ， 222

这是不可能的，所以{a 1 + b 1， a 2 + b 2， ， a m + b m }不能是模m 的完全剩余系。

4、证明：（1）2730∣x 13-x ； （2）24∣x(x+2)(25x-1) ；

（3）504∣x 9-x 3； （4）设质数p ＞3，证明：6p ∣x p -x 。

证明：（1）因为2730=2×3×5×7×13，2，3，5，7，13两两互质，所以：

由x 13-x=x (x12-1) ≡0 (mod 2)知：2∣x 13-x ；13∣x 13-x ；

2

由x 13-x=x (x12-1)=x(x2-1) (x2+1)(x8+x4+1)≡0 (mod 3)知：3∣x 13-x ；

由x 13-x=x (x12-1)=x(x4-1) (x8+x4+1)≡0 (mod 5)知：5∣x 13-x ；

由x 13-x=x (x12-1)=x(x6-1) (x6+1)≡0 (mod 7)知：7∣x 13-x 。

故有2730∣x 13-x 。

同理可证（2）、（3）、（4）。

初等数论练习题五

一、单项选择题

1、设x 、y 分别通过模m 、n 的完全剩余系，若（ C ）通过模mn 的完全剩余系。

A. m 、n 都是质数，则my + nx B. m ≠n ，则my + nx

C. （m ，n ）=1，则my + nx D. （m ，n ）=1，则mx + ny

2、1×3×5×…×2003×2005×2007×2009×2011标准分解式中11的幂指数是( A ) 。

A.100 B.101 C.99 D.102

3、n 为正整数，若2n -1为质数，则n 是( A ) 。

A. 质数 B. 合数 C.3 D.2k (k为正整数)

4、从100到500的自然数中，能被11整除的数的个数是( B ) 。

A.33 B.34 C.35 D.36

5、模100的最小非负简化剩余系中元素的个数是( C ) 。

A.100 B.10 C.40 D.4

二、填空题

1、同余方程ax +b≡0(modm ) 有解的充分必要条件是

q 2() =(-1) p p -1q -1⋅22(p ) q

3、20122012被3除所得的余数为_1__。

4、设n 是大于2的整数，则(-1)ϕ(n)。

5、单位圆上的有理点的坐标是(±零的整数。

6、若3258×a 恰好是一个正整数的平方，则a 的最小值为 2ab a +b 22, ±a 2-b 2a +b 22) 或(±a 2-b 2a +b 22, ±2ab a +b 22) ，其中a 与b 是不全为

⎛72⎫7、已知2011是一素数，则 ⎪。 2011⎝⎭

三、计算题

1、求32008×72009×132010的个位数字。

解：32008×72009×132010≡32008×（-3）2009×32010 ≡-32008+2009+2010

≡-36027 ≡-3×（32）3013 ≡3(mod 10)。

2、求满足ϕ(mn)=ϕ(m )+ϕ(n ) 的互质的正整数m 和n 的值。

解：由（m ，n ）=1知，ϕ(mn)=ϕ(m ) ϕ(n ) 。于是有：ϕ(m )+ϕ(n )= ϕ(m ) ϕ(n )

设ϕ(m )=a， ϕ(n )=b，即有：a+b=ab。 显然a ∣b ，且b ∣a ，因此a=b。 于是由2a=a2 得a=2，即ϕ(m )= ϕ(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)的一般解是 13

⎧x =4t ， t ∈Z ⎨y =25-7t ⎩

因为x ＞0，y ＞0，所以 0＜t ≤ 3。

即t 可以取值t 1 = 1，t 2 = 2，t 3 = 3。相应的x ，y ，z 的值是

(x ， y ， z ) = (4， 18， 78) ，(8， 11， 81) ，(12， 4， 84) 。

四、证明题

1、已知2011是质数，则有2011|99⋅⋅ ⋅9。

2010个

证明：99⋅⋅ ⋅9=102011-1≡0 (mod 2011)。

2010个

2、设p 是4n+1型的质数，证明若a 是p 的平方剩余，则p-a 也是p 的平方剩余。 证明：因为质数p=4n+1，a 是p 的平方剩余，所以

⎛p -a ⎫⎛-a ⎫⎛-1⎫ p ⎪⎪= p ⎪⎪ p ⎪⎪= ⎝⎭⎝⎭⎝⎭

p -1⎛a ⎫⎛a ⎫2= ⎪ (-1) p ⎪ p ⎪⎪=1 ⎝⎭⎝⎭

即：p-a 也是p 的平方剩余。

3、已知p ，q 是两个不同的质数，且a p-1≡1 (mod q)， a q-1≡1 (mod p)，

证明：a pq ≡a (mod pq)。

证明：由p ，q 是两个不同的质数知（p ，q ）=1。于是由Fermat 定理 a p ≡a (mod p)，

又由题设a q-1≡1 (mod p)得到：a pq ≡(aq ) p ≡a p (aq-1) p ≡a p ≡a (mod p)。

同理可证：a pq ≡a (mod q)。故：a pq ≡a (mod pq)。

4、证明：若m ，n 都是正整数，则ϕ(mn)=（m ，n ）ϕ([m ，n ])。

证明：易知mn 与[m ，n ]有完全相同的质因数，设它们为p i (1≢i ≢k ) ，则

=mn (1- ϕ（mn ）111)(1-) (1-) p 1p 2p k

111)(1-) (1-) p 1p 2p k ϕ（[m , n ]）=[m , n ](1-

又mn=（m ，n ）[m ，n ] =（m , n )[m , n ](1-故ϕ（mn ）111)(1-) (1-) =(m , n ) ϕ([m , n ])。 p 1p 2p k

类似的题：设m=m1m 2，m 1与m 由相同的质因数，证明：ϕ(m)=m2ϕ(m 1) 。

初等数论练习题六

一、填空题

1、为了验明2011是质数，只需逐个验算质数2，3，5，…p 都不能整除2011，此时，质数p 至少是_43___。

2、最大公因数(4n+3，5n+2)的可能值是。

|40! ，即3α‖40! ，则α=_18_。 3、设3α∣40! ，而3α+1/

4、形如3n+1的自然数中，构成模8的一个完全系的最小那些数是。

5、不定方程x 2+y2=z2，2|x， (x，y)=1， x ，y ，z>0的整数解是且仅是x = 2ab ，y = a 22，z = a 2 2，其中a > b > 0，(a ， b ) = 1，a 与b 有不同的奇偶性。

6、21x ≡9 (mod 43)的解是。

7、 ⎛73⎫⎪ ⎝199⎭

二、计算题

1、将17写成三个既约分数之和，它们的分母分别是3，5和7。 105

17x y z =++，即35x + 21y + 15z = 17，因(35， 21) = 7，(7， 15) = 1，1∣17，解：设105357

故有解。

分别解 5x + 3y = t 7t + 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。即：174-83=++ 105357

2、若3是质数p 的平方剩余，问p 是什么形式的质数？

3⎫解：∵ 由二次互反律⎛ p ⎪⎪=(-1) ⎝⎭p -12⎛p ⎫⋅ ⎪，

⎝3⎭

p ≡1(mod4) ⎛p ⎫⎧1≡ ⎪±⎨ 注意到p >3，p 只能为p ≡1(mod 3)且 ⎝3⎭⎩-1p ≡-1(mod4)

∴ ⎧p ≡1(mod3) ⎛3⎫ p ⎪⎪=1只能下列情况⎨p ≡1(mod4) ⎩⎝⎭d ) ⎧p ≡-1(m o 3 ⎨ p ≡-1(m o 4d ) ⎩

∴ p ≡1(mod12) 或p ≡-1(mod12) 。

3、判断不定方程x 2+23y =17是否有解？

解：只要判断x 2≡17(mod 23) 是否有解即可。

∵ 17≡1(mod 4) ∴ ⎛17⎫⎛23⎫⎛6⎫⎛2⎫⎛3⎫⎛3⎫⎛17⎫⎛2⎫⎪= ⎪= ⎪= ⎪ ⎪= ⎪= ⎪= ⎪=-1 23⎝⎭⎝17⎭⎝17⎭⎝17⎭⎝17⎭⎝17⎭⎝3⎭⎝3⎭

∴ x 2≡17(mod 23)无解，即原方程无解。

三、论证题

1、试证对任何实数x ，恒有〔x 〕+〔x+〕=〔2x 〕

证明：设x=[x]+α，0≢α

①当0≢α

②当≢α

故对任何实数x ，恒有[x]+[x+]=[2x]。

2、证明：（1）当n 为奇数时，3∣（2+1）； n 121212

|（2+1）（2）当n 为偶数时，3/。

证明：由2+1≡（-1）+1（mod 3）立得结论。

3、证明：（1）当3∣n （n 为正整数）时，7∣（2-1）； n n n n

|（2+1） （2）无论n 为任何正整数，7/。

证明：（1）设n=3m，则2-1=8-1≡0（mod 7），即：7∣（2-1）；

（2）由于2≡1（mod 7）得

2+1≡2（mod 7），23m 3m+1 3m n m n n +1≡3（mod 7），2

n 3m+2 +1≡5（mod 7）。 |（2+1） 故无论n 为任何正整数，7/。

4、设m ＞0，n ＞0，且m 为奇数，证明：（2-1，2+1）=1。

证明一：由m 为奇数可知：2n +1︱2+1，又有2m -1︱2-1，

于是存在整数x ，y 使得：（2n +1）x=2+1， (2m -1)y=2-1。

从而（2n +1）x-(2m -1)y=2。这表明：

（2m -1，2n +1）︱2

由于2n +1，2m -1均为奇数可知：（2m -1，2n +1）=1。

证明二：设（2-1，2+1）=d，则存在s ，t ∈Z ，使得2=sd+1， 2=td-1。由此得到： 2=(sd+1)， 2=(td-1)mn nmn m m n m n m n mn mn mn mn

于是 2mn =pd + 1=qd – 1，p ，q ∈Z 。所以：（q -p ）d =2。

从而 d ∣2，就有d =1或2。由因为m 为奇数，所以d =1。

即（2-1，2+1）=1。

注：我们已证过：记M n = 2n - 1，对于正整数a ，b ，有(M a ， M b ) = M(a ， b ) 。

显然当a ≠b ，a ，b 为质数时，(M a ， M b ) =1。

m n

初等数论练习题七

一、单项选择题

1、设a 和b 是正整数，则(

A ．1 [a , b ][a , b ], ) =（ A ） a b B ．a C ．b D ．(a，b)

2、176至545的正整数中，13的倍数的个数是（ B ）

A ．27 B ．28 C ．29 D ．30

3、200! 中末尾相继的0的个数是（ A ）

A ．49 B ．50 C ．51 D ．52

4、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（ B ）

A ．2的倍数 B ．3的倍数 C ．4的倍数 D ．5的倍数

5、设n 是正整数，下列选项为既约分数的是（ A ）

A ．21n +4n +12n -1n +1 B ． C ． D ． 14n +32n -15n +23n +1

二、填空题

1、314162被163除的余数是

。（欧拉定理）

2、同余方程3x ≡5(mod13)的解是

3、(

365) 1847

4、［-π

5、为使n-1与3n 的最大公因数达到最大的可能值，则整数n 应满足条件

6、如果一个正整数具有21个正因数，问这个正整数最小是7、同余方程x

3+x2-x-1≡0(mod 3)的解是三、计算题

1、求不定方程x + 2y + 3z = 41的所有正整数解。

解：分别解x + 2y = t

t + 3z = 41

得 x = t - 2u

y = u u ∈Z ，

t = 41 - 3v

z = v v ∈Z ，

消去t 得 x = 41 - 3v - 2u

y = u

z = v u ，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)。

在孙子定理中，取 m 1 = 3， m 2 = 5， m 3 = 11，m = 3⋅5⋅11 = 165，

M 1 = 55，M 2 = 33，M 3 = 15，

M 1' = 1，M 2' = 2，M 3' = 3，

则 x ≡ 1⋅55⋅1 + （-2）⋅33⋅2 + 3⋅15⋅3 ≡ 58 (mod 165)，

因此所求的整数x = 52 + 165t ，t ∈Z 。

由于这队士兵不超过170人，所以这队士兵有58人。

23、判断同余方程x ≡286(mod443) 是否有解?

解：286=2×143，433是质数，(143，443)=1

奇数143不是质数，但可用判定雅可比符号计算的勒让德符号

⎛286⎫⎛2⎫⎛143⎫ ⎪= ⎪ ⎪=(-1) ⎝443⎭⎝243⎭⎝443⎭4432-12⋅(-1) 143-1443-1⋅22⎛443⎫⎛14⎫⎛2⎫⎛7⎫ ⎪= ⎪= ⎪ ⎪ ⎝143⎭⎝143⎭⎝143⎭⎝143⎭

=(-1) 143-1

8⋅(-1) 7-1143-1⋅223⎫⎛1⎫⎛143⎫=-⎛ ⎪= ⎪=1 ∴原方程有解。 ⎪ ⎝7⎭⎝3⎭⎝7⎭

四、证明题

1、设(a ， m ) = 1，d 0是使a d ≡ 1 (mod m ) 成立的最小正整数，则

(ⅰ) d 0∣ϕ(m ) ；

j (ⅱ) 对于任意的i ，j ，0 ≤ i ， j ≤ d 0 - 1，i ≠ j ，有a i ≡/a (mod m ) 。 （1）

证明：(ⅰ) 由Euler 定理，d 0 ≤ ϕ(m ) ，因此，由带余数除法，有

ϕ(m ) = qd 0 + r ，q ∈Z ，q > 0，0 ≤ r

因此，由上式及d 0的定义，利用欧拉定理得到

qd +r 1 ≡a ϕ(m ) =a 0≡a r (mod m ) ，

即整数r 满足 a r ≡ 1 (mod m ) ，0 ≤ r

由d 0的定义可知必是r = 0，即d 0∣ϕ(m ) 。

(ⅱ) 若式(1)不成立，则存在i ，j ，0 ≤ i ， j ≤ d 0 - 1，i ≠ j ，使a i ≡ a j (mod m ) 。 不妨设i > j 。因为(a ， m ) = 1，所以 a i - j ≡ 0 (mod m ) ，0

这与d 0的定义矛盾，所以式(1)必成立。

2、证明：设a ，b ，c ，m 是正整数，m > 1，(b ， m ) = 1，并且

b a ≡ 1 (mod m ) ，b c ≡ 1 (mod m ) （1）

记d = (a ， c ) ，则b d ≡ 1 (mod m ) 。

证明：由裴蜀恒等式知，存在整数x ，y ，使得ax + cy = d ，显然xy

若x > 0，y

若x 0，由式(1)知：1 ≡ b cy = b d b -ax = b d (b a ) -x ≡ b d (mod m ) 。

3、设p 是素数，p ∣b n - 1，n ∈N ，则下面的两个结论中至少有一个成立：

(ⅰ) p ∣b d - 1对于n 的某个因数d

(ⅱ) p ≡ 1 ( mod n )。

若2/|n ，p > 2，则(ⅱ) 中的mod n 可以改为mod 2n 。

证明：记d = (n ， p - 1)，由b n ≡ 1，b p - 1 ≡ 1 (mod p ) ，及第2题有

b d ≡ 1 (mod p ) 。

若d

若d = n ，则n ∣p - 1，即p ≡ 1 (mod n ) ，这就是结论(ⅱ) 。

|n ，p > 2，则p ≡1 (mod 2)。由此及结论(ⅱ) ，并利用同余的基本性质， 若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.37

3、500! 的标准分解式中7的幂指数是（ D ）

A.79 B.80 C.81 D.82

4、以下各组数中，成为模10的简化剩余系的是（ D ）

A.1，9，－3，－1 B.1，－1，7，9 C.5，7，11，13 D. －1，1，－3，3

5、设n 是正整数，下列选项为既约分数的是（ A ） A. 3n +1

5n +2 B. n +1

2n -1 C. 2n -1

5n +2 D. n +1

3n +1

二、填空题

1、σ（120）

2、7355的个位数字是

3、同余方程3x ≡5(mod14)的解是

4、（17

23）

5、

［-26、如果一个正整数具有6个正因数，问这个正整数最小是

7、同余方程x 3+x2-x-1≡0(mod 5)的解是三、计算题

1、已知563是素数，判定方程x 2 ≡ 429 (mod 563)是否有解。 解：把⎛ 429⎫

⎝563⎪⎭看成Jacobi 符号，我们有

⎛429-14292-1 429⎫⎪=(-12. 563-1

2⎛ 563⎫8⎛

⎝563⎭) ⎝429⎪⎭=⎛ 563⎫

⎝429⎪⎭=⎛ 134⎫

⎝429⎪⎭=⎛ 2⎫

⎝429⎪⎛

⎭ 67⎫

⎝429⎪⎭=(-1) 67⎫

⎝429⎪⎭

67-1429-127-167-1

=-⎛ 67⎫⎪=-(-1) 22⎛ 429⎫2. 2⎛

⎝429⎭⎝67⎪⎭=-⎛ 429⎫

⎝67⎪⎭=-⎛ 27⎫

⎝⎪=-(-1) 67⎫

67⎭⎝27⎪⎭=⎛ 67⎫

⎝27⎪⎭

⎛27-113-1

= 13⎫2. 2⎛

⎝27⎪⎭=(-1) 27⎫⎛1⎫

⎝13⎪⎭= ⎝13⎪⎭=1，

故方程x 2 ≡ 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 ，使得1n ＋2n ＋3n ＋4n 能被5整除。

解：若n 为奇数，则1n ＋2n ＋3n ＋4n ≡1n ＋2n ＋（-2）n ＋（-1）n ≡ 0 (mod 5)； 若n=2m，m ∈Z ，则1n ＋2n ＋3n ＋4n ≡12m ＋22m ＋（-2）2m ＋（-1）2m

≡2+2×22m =2+2×4m =2+2×(-1)m (mod 5)；

当m 为奇数时，1n ＋2n ＋3n ＋4n ≡0(mod 5)；

当m 为偶数时，1n ＋2n ＋3n ＋4n ≡4(mod 5)。

故当4/|n 时，5∣1＋2＋3＋4。 n n n n

四、证明题

1、证明：若质数p>2，则2P -1的质因数一定是2pk+1形。

证明：设q 是2p -1的质因数，由于2p -1为奇数，∴ q ≠2，（2，q ）=1。

由条件q|2p -1，即2p ≡1（mod q ）。

设h 是使得2x ≡1（mod q ）成立最小正整数，若1

∴ 2p |q -1，q -1=2pk ， 即q =2pk +1 k ∈Z 。

2、设（m ，n ）=1，证明：m ϕ(n)+n ϕ(m) ≡1 (mod mn)。

ϕ(m) 证明：因为（m ，n ）=1，所以由欧拉定理知： n

于是 m ϕ(n) ≡1 (mod m)，m ϕ(n) ≡1 (mod n) +n ϕ(m) ≡1 (mod m)， m

ϕ(n)ϕ(n)+n ϕ(m) ≡1 (mod n)。 又因为（m ，n ）=1，所以 m +n ϕ(m) ≡1 (mod mn)。

注：此题也可这样表述：若两个正整数a ，b 互质，则存在正整数m ，n ，使得

a m +bn ≡1(mod ab)。

a p +b p

3、设（a ，b ）=1，a+b≠0，p 为一个奇质数，证明：(a +b , ) =1或p 。 a +b

a p +b p 说明：事实上，设(a +b , ) =d ，只需证明：d | p 即可。 a +b

证明：由a+b≡0(mod a+b)，即a ≡-b (mod a+b)，知a ≡(-b) (mod a+b)。

p p a +b 其中0≢k ≢p -1。又=a p -1-a p -2b + -ab p -2+b p -1≡b p -1+b p -1+ +b p -1=pb p -1m (o d a +b k k a +b ) 。

p-1 a p +b p 令(a +b , 。 又（a ，b ）=1，d |（a+b）知（d ，b ）=1。 ) =d ，则d | pb a +b

（否则设（d ，b ）=d′＞1，立即得到d ′︱a 和d ′︱b ，这与（a ，b ）=1矛盾。） 于是（d ，b p-1）=1。故d | p ，即 d =1或p 。

初等数论练习题九

一、单项选择题

1、以下Legendre 符号等于-1的30被-1是( D ) 3⎫A. ⎛ ⎪ ⎝11⎭4⎫B. ⎛ ⎪ C. ⎝11⎭⎛5⎫ D. ⎪⎝11⎭⎛6⎫ ⎪⎝11⎭

2、100至500的正整数中，能被17整除的个数是( B )

A. 23 B. 24 C. 25 D. 26

3、设 3α|500!，但3α+1/，则α=( C ) |500！

A. 245 B.246 C.247 D. 248

4、以下数组中，成为模7的完全剩余系的是( C )

A. －14，－4，0，5，15，18，19

C. －4，－2，8，13，32，35，135 B. 7，10，14，19，25，32，40 D. －3，3，－4，4，－5，5，0

5、设n 是正整数，则以下各式中一定成立的是( B )

A. (n +1，3n ＋1)=1

C. （2n ，n ＋1）=1

二、填空题

1、25736被50

2、同余方程3x ≡

5(mod16) 的解是3、不定方程9x －12y =15的通解是

4、 ⎛323⎫⎪

= 41⎝⎭B. （2n －1，2n ＋1）=1 D. （2n ＋1，n －1）=1

5、实数的小数部分记为{x

} ，则 {－}6、为使3n 与4n ＋1

的最大公因数达到最大可能值，整数n 应满足条件

7、如果一个正整数具有35个正因数，问这个正整数最小是三、计算题

54

1、解不定方程9x ＋24y －5z =1000。

解：解 因（9，24）=3，（3，-5）=1知原方程有解。原方程化为

9x + 24y = 3t ， 即

3x + 8y = t ， (1)

3t -5z = 1000 3t -5z = 1000， (2)

⎧t =5u 解(2)得 ⎨， u ∈Z ， z =-200+3u ⎩

⎧x =-u +8v 再解3x + 8y =5u得到 ⎨， u ，v ∈Z 。 y =u -3v ⎩

⎧x =-u +8v ⎪故 ⎨y =u -3v ， u ， v ∈Z 。

⎪z =-200+3u ⎩

2、设A = {x 1， x 2， ， x m }是模m 的一个完全系，以{x }表示x 的小数部分，若(a ， m )

ax +b = 1，求∑i 。 m i =1m

解：当x 通过模m 的完全剩余系时，ax + b 也通过模m 的完全剩余系，因此对于任意的

i （1 ≤ i ≤ m ），ax i + b 一定与且只与某个整数j （1 ≤ j ≤ m ）同余，即存在整数k ，使得ax i + b = km + j ，（0 ≤ j ≤ m-1）。从而：

m -1m -1m -1ax i +b j j j 1m (m -1) m -1 ={k +={==⋅=。∑∑∑∑m m m m m 22i =1j =0j =1j =1m

3、设整数n ≥ 2，求：

1≤i ≤n (i , n ) =1∑i 。即在数列1， 2， ， n 中，与n 互素的整数之和。

解：设在1， 2， ， n 中与n 互素的ϕ(n ) 个数是

a 1， a 2， ， a ϕ(n ) ，(a i ， n ) = 1，1 ≤ a i ≤ n - 1，1 ≤ i ≤ ϕ(n ) ，

则 (n - a i ， n ) = 1，1 ≤ n - a i ≤ n - 1，1 ≤ i ≤ ϕ(n ) ，

因此，集合{a 1， a 2， ， a ϕ(n ) }与集合{n - a 1， n - a 2， ， n - a ϕ(n ) }是相同的，

于是

a 1 + a 2 + + a ϕ(n ) = (n - a 1) + (n - a 2) + + (n - a ϕ(n ) ) ，

2(a 1 + a 2 + + a ϕ(n ) ) = n ϕ(n ) ， 因此：a 1 + a 2 + + a ϕ(n ) =n ϕ(n ) 。

4、设m > 1，(a ， m ) = 1，x 1， x 2， ⋯， x ϕ(m ) 是模m 的简化剩余系，求：∑ax i 。

i =112ϕ(m ) m

其中{x }表示x 的小数部分。

解：设ax i = mq i + r i ，0 ≤ r i

余系，从而r i 通过模m 的最小非负简化剩余系，于是：

ϕ(m ) ϕ(m ) ϕ(m ) ax i r i r i 1ϕ(m ) =∑{q i +=∑=∑r i =1m ϕ(m ) =1ϕ(m ) 。 ∑m m m i =12m 2i =1i =1i =1m

四、证明题

1、证明：设a 是有理数，b 是使ba 为整数的最小正整数，若c 和ca 都是整数，则 b ∣c 。(提示：利用带余数除法解决。)

证明：设c=bq+r，0≢r ＜b ，q ∈Z ，则ca=(ba)q+ra。

因为ca ，b a ∈Z ，所以ra ∈Z ，于是ra=0，由a ≠0得r=0。故b ∣c 。

2、设p 是素数，证明：

(ⅰ) 对于一切整数x ，x p - 1 - 1 ≡ (x - 1) (x - 2) (x - p + 1) (mod p ) ；

(ⅱ) (p - 1)! ≡ - 1 (mod p ) 。

证明：(ⅰ) x p - 1 - 1 ≡ 0 (mod p ) 有解x ≡ 1，2， ，p - 1 (mod p ) ，

故对于一切整数x ，x p - 1 - 1 ≡ (x - 1) (x - 2) (x - p + 1) (mod p ) ；。

(ⅱ) 在(ⅰ) 中令x = p 。

⎛a ⎫n |n ，p 是奇质数，p ∣a -1，则 3、证明：若2/ p ⎪⎪=1。

⎝⎭

证明：由p ∣a -1知：a ≡ 1(mod p ) 。又（p ，a ）=1得到a

|n ，所以(a 因为2/n +1

22n n n+1 ≡ a(mod p ) 。 ⎛a ⎫2) ≡a (modp ) ，即x ≡ a(mod p ) 有解。故 p ⎪⎪=1。

⎝⎭

m 4、证明：若p=4m+1是一质数，则（）=1。 p

m 4m -1 证明：）=（=() =(-1) p p p p -12=(-1) 2m =1。

p -12) ! ) ≡ -1 (mod p ) 25、设p 是奇质数，p ≡ 1 (mod 4)，则：(±(

解 由Wilson 定理有：

-1≡(p -1)! =(-1) p -1

2(p -1)! =(-1) p -1

21⋅2 p -1p +1p -12 (p -1) ≡(±() ! ) (modp ) 。222

注：（1）设p 为质数且p ＝4m +1，则同余方程x 2≡-1(modp ) 的解是x ≡±1⋅2 (2m )(modp ) 。

（2）设p 为质数且p ＝4m +1，若且唯若存在一个正整数a ，使得 a 2≡-1 (mod p ) 。

初等数论练习题十

一、单项选择题

1、设p 是大于1的整数，如果所有不大于p 的质数都不能整除p ，则p 一定是（ A ）。

A. 素数 B. 合数 C. 奇数 D. 偶数

2、两个质数p ，q ，满足p+q=99，则

A.9413 B. 9413 194p q +的值是（ B ） q p C. 94139413 D. 99111

3、2010！的标准分解式中，7的最高幂指数为（ C ）

A ．331 B ．332 C ．333 D ．334

4、n 为正整数，若2n +1为质数，则n 是（ D ）

A ．质数 B ．合数 C ．1 D ．2k (k为非负整数)

5、当n ＞2时，欧拉函数ϕ(n ) 一定是（ B ）。

A ．奇数 B ．偶数 C ．1 D ．2

二、填空题

1、如果p 是质数，a

2、设p 是奇质数，(a，p)=1，则a 是模p

3、从1000开始到2010结束的所有整数中13的倍数有

4、2756839-1的末位数是

5、不定方程ax+by=c

6、写出模12的一个最小非负简化系，要求每项都是

7

7、已知563是质数，则

三、计算题

1、若3是质数p 的平方剩余，问p 是什么形式的质数？

3⎫解：∵ 由二次互反律⎛ ⎪=(-1) p ⎪⎝⎭p -12⎛2⎫⎪= ⎝563⎭⎛p ⎫⋅ ⎪，

⎝3⎭

⎝3⎭⎩-1p ⎫⎧1p ≡1(mod3) 注意到p >3，p 只能为p ≡±1(mod 4)且⎛ ⎪≡⎨ p ≡-1(mod3)

∴ ⎛3⎫⎧p ≡1(mod3) p ⎪⎪=1，只能是下列情况⎨⎝⎭⎩p ≡1(mod4) p ≡-1(m o 3d ) ⎧ ⎨d ) ⎩p ≡-1(m o 4

∴ p ≡1(mod12) 或p ≡-1(mod12) 。

2、求使12347! 被35k 整除的最大的k 值。

解：k=2054.

四、证明题

1、证明：设p ≥7是一个质数，则存在唯一的一个正整数x ，使得：

x ∈{1,2, , p -1}且120(p-6)! +x ≡0(mod p )

证明：存在性：因为p ≥7是一个素数，由Wilson 定理我们有：(p -1)! +1≡0(mod p )，

然而(p -1)! =(p -1)(p -2)(p -3)(p -4)(p -5)(p -6)! ≡-120(p -6)! (mod p )，所以120(p -6)! +(p -1)=0(mod p )，

故存在x =p -1，使得120(p-6)! +x ≡0(mod p )。

唯一性：若还存在y ∈{1,2, , p -1}且120(p-6)! +y ≡0(mod p )，

, p -1}，所以x =y 是唯一的。 则x ≡y (mod p )，注意到x , y ∈{1,2,

2、已知9901是素数，试证：9901(174950+1) 。

证明：由9901是素数，计算Legendre 符号得：

17-19901-17-117-13-17-1⎛17⎫⎛9901⎫⎛7⎫⎛17⎫⎛3⎫⎛7⎫⎛1⎫222222=-1==-1==-1=-()()() ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪=-1⎝9901⎭⎝17⎭⎝17⎭⎝7⎭⎝7⎭⎝3⎭⎝3⎭

所以17是模9901的平方非剩余，因此由Euler 判别条件可知：

179901-1

2≡-1(mod9901) 即 9901(174950+1) 。

3、证明：若p=10n -1是个质数，则p 55n -1-1。（提示：利用勒让德符号解决。） 说明：要证p 55n -1-1，只需证明55n -1≡1(modp ) ，即证：

55n -1≡510n -1-1

2≡5p -1

2≡1(modp ) 这样就转化为证明：(5) =1。 p

证明：因为(5) =(p ) =(10n -1) =(-1) ≡1(modp ) 。

p 555

所以55n -1≡510n -1-1

2≡5p -1

2≡1(modp ) 。 故：p 55n -1-1。

4、设p=4n+3是质数，证明当q=2p+1也是质数时，梅森数M p =2p -1不是质数。 由此证明：23|（2-1），47|（2-1），503|（21123251-1）。

q 证明：由条件：q =2p+1=8n+7≡-1(mod 8) ，从而：(p ) =1，

即1≡2q -1

2p ≡24n+3≡2p （mod q ) ，于是q |（2p -1）。故：梅森数M p =2-1不是质数。

1123251当n=2，n= 5，n=62时立得：23|（2-1），47|（2-1），503|（2-1）。

注：此题还可以进一步表述为：设p=4n+3是质数，证明：2p+1是质数的充要条件是

2p ≡1(mod 2p+1)。必要性已证。下证充分性：若2p ≡1(mod 2p+1)，则

p ∣ϕ(2p+1) ，因此必有ϕ(2p+1)= p 或2p 。由于ϕ(2p+1) 为偶数，故ϕ(2p+1)=2p 。

5、证明：设p 是大于5的质数，则(p -1)! +p +1∈Z 。 p (p +1)

说明：只需证明：p(p+1) | (p-1)!+p+1。又因为(p，p+1)=1，所以需证：

p | (p-1)!+p+1 与(p+1) | (p-1)!+p+1同时成立即可。

证明：由Wilson 定理：(p -1)! +1≡0(mod p )知：p | (p-1)!+p+1；

又p 是大于5的质数，可设p+1=2n，其中2＜n ＜p-1，于是 (p+1) | (p-1)!+p+1。

故：p(p+1) | (p-1)!+p+1。即(p -1)! +p +1∈Z 。 p (p +1)