初等数论练习题答案

初等数论练习题一

一、填空题

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、??65?? =-1。 ?103?

9、若p是素数，则同余方程x p ? 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)是否有解？

237）（）（）1071071071071073?1107?17?1107?1 ??2310727107222?（）??1，（）?（?1）（）??（）?1，（）?（?1）22（）??（）??1107107331077742?（）?11072?3?7解：(42)?（）?（ 故同余方程x2≡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为奇数时，ap-1+(p-1)≡0 (mod p)； （2）当a为偶数时，ap-1-(p-1)≡0 (mod p)。

证明：由欧拉定理知ap-1≡1 (mod p)及(p-1)≡-1 (mod p)立得（1）和（2）成立。 2、设a为正奇数，n为正整数，试证a2na

aa

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

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

a2 = (2m ? 1)2 = 4m(m ? 1) ? 1 ? 1 (mod 23)，即原式成立。 设原式对于n = k成立，则有 其中q?Z，所以 a2k?1a2k? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，

k= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，

其中q ?是某个整数。这说明式(1)当n = k ? 1也成立。 由归纳法知原式对所有正整数n成立。

k3、设p是一个素数，且1?k?p-1。证明：Ckp?1 ? （-1 ）(mod p)。

（p?1）(p?2)?(p?k) 证明：设A=Ckp?1? 得：

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

k

又（k!，p）=1，故A = Ck ? （-1 ）(mod p) p?14、设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的奇质数，所以

2

（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=22+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、??46??=_1__. ?101?n9、若p是质数，n?p ? 1，则同余方程x n ? 1 (mod p) 的解数为n . 二、计算题

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

解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19) 又由20032004≡22004≡（22）1002≡1 (mod 3)可得：

200320022004≡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应为其中使 5 x ? 1 (mod 12)成立的最小数，经计算知：x=6。

3

三、证明题

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

10s?1(10a)b?110a?1 ps?11?1????M，其中M＞1是正整数。 ???999s由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使为既约分数的一组数是（ 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

ba4、不是同余方程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)

4

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、σ(2010)=_4896____；?(2010)=528。

202、数C100的标准分解式中，质因数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、??60??=_-1_。 ?97?三、计算题

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的同余方程，故原方程不可能有六个解。

32n?12、设n是正整数，求C1 的最大公约数。 2n,C2n,?,C2n132n?1132n?12n?1 解：设(C2n,C2n,?,C2n)?d，由C2n?C2n???C2n?2知d?22n?1，

|n，即2k +1||n ， 设2k|n且2k+1?则由2k +1||C2n及21k?1|Ci2n?2ni?1C2n?1，i = 3, 5, ?, 2n ? 1 得d = 2k + 1。 i3、已知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。

于是x应为其中使18x ? 1 (mod 77)成立的最小数，经计算知：x=30。

5

四、证明题

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(mod 24)。 证明：因为24=3×8，（3,8）=1，所以只需证明：

p2≡q2(mod 3) p2≡q2(mod 8)同时成立。

事实上， 由于（p，3）=1，（q，3）=1，所以p2≡1(mod 3) ， q2≡1(mod 3)，

于是p2≡q2(mod 3)，由于p，q都是奇数，所以p2≡1(mod 8) ， q2≡1(mod 8)，

于是p2≡q2(mod 8)。故p2≡q2(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?α<1，y=[y]+β,0?β<1。于是

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

所以[xy]= [x][y]+ [β[x]+α[y]+αβ] ?[x][y]。 （2）{xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。

11时，{xy}={x}{y}=； 243131 当x=， y=时，{xy}=，{x}{y}=，此时{xy}＞{x}{y}；

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

2363cc4、证明：存在一个有理数，其中d < 100,能使 [k]=[k73]

dd100+

当x=y=

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

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

从而

73kkck(73d?100c)k-==，由k< 100可知： 100100dd100d6

0＜

设[k73kc1k-＜ 100dddcd]=n，则kc＜n+1=n?1d,于是

d73kc?1n?1k＜d=n+1， ?100dd73故 [k]= n =[k100cd]。

初等数论练习题四

一、单项选择题

1、若Fn=22?1是合数，则最小的n是( D )。 A. 2 B. 3 C. 4 D. 5

|a. 以下各式中错误的一个是( B )。 2、记号ba‖a表示ba｜a,但ba+1?nA. 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、d(10010)=_32__，φ(10010)=_2880__。

2、对于任意一个自然数n，为使自N起的n个相继自然数都是合数，可取N=（n+1）！ 3、为使3n-1与5n+7的最大公因数达到最大可能值，整数n应满足条件n=26k+9，k∈Z。 4、在5的倍数中，选择尽可能小的正整数来构成模12的一个简化系，则这组数是{5,25,35,55} 5、同余方程26x+1≡33 (mod 74)的解是x1≡24(mod74) x2≡61(mod74)_。 6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10,y=4。 7、?

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

?54??=_-1_。 ?89?7

三、计算题

1、设n的十进制表示是13xy45z，若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、设a1, a2, ?, am是模m的完全剩余系，证明： （1）当m为奇数时，a1+ a2+ ?+ am ≡0（mod m）； （2）当m为偶数时，a1+ a2+ ?+ am ≡

m（mod m）。 2 证明：因为{1, 2, ?, m}与{a1, a2, ?, am}都是模m的完全剩余系，所以

?ai??i?i?1i?1mmm(m?1)(mod m)。 2 8

mm?1m(m?1)m(m?1)?Z即得：m（1）当m为奇数时，由，故?ai??0(mod m)。 222i?1m（2）当m为偶数时，由（m,m+1）=1即得：?ai?i?1m(m?1)m?(mod m)。 22?（m）2、证明：若m＞2，a1, a2, ?, a?(m)是模m的任一简化剩余系，则

?ai?1i?0(modm).

证明：若a1, a2, ?, a?(m)是模m的一个简化剩余系，则m-a1, m-a2, ?, m-a?(m) 也是模m

?（m）的一个简化剩余系，于是：

?a??(m?a)(modm). 从而：2?aiii?1i?1i?1?(m)?（m）i?m?(m)(modm).

又由于m＞2，?(m)是偶数。故：

?（m）i?1?ai?m?（m）2?0(modm).

3、设m > 0是偶数，{a1, a2, ?, am}与{b1, b2, ?, bm}都是模m的完全剩余系，证明：{a1 ? b1, a2 ? b2, ?, am ? bm}不是模m的完全剩余系。

证明：因为{1, 2, ?, m}与{a1, a2, ?, am}都是模m的完全剩余系，所以

?ai??i?i?1i?1mmm(m?1)m?(mod m)。 (1) 22同理 ?bi?i?1mm(mod m)。 (2) 2如果{a1 ? b1, a2 ? b2, ?, am ? bm}是模m的完全剩余系，那么也有

?(ai?bi)?i?1mm(mod m)。 2联合上式与式(1)和式(2)，得到 0?mmm??(mod m)， 222这是不可能的，所以{a1 ? b1, a2 ? b2, ?, am ? bm}不能是模m的完全剩余系。 4、证明：（1）2730∣x13-x； （2）24∣x(x+2)(25x-1)；

（3）504∣x9-x3； （4）设质数p＞3，证明：6p∣xp-x。 证明：（1）因为2730=2×3×5×7×13，2,3,5，7,13两两互质，所以： 由x13-x=x (x12-1)≡0 (mod 2)知：2∣x13-x；13∣x13-x；

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

9

2

由x13-x=x (x12-1)=x(x6-1)(x6+1)≡0 (mod 7)知：7∣x13-x。 故有2730∣x13-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)有解的充分必要条件是(a,m)∣b。

q2、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数， ()?(?1)pp?1q?1?22(p)

q3、20122012被3除所得的余数为_1__。 4、设n是大于2的整数，则(-1)?(n)=__1__。 5、单位圆上的有理点的坐标是(?零的整数。

6、若3258×a恰好是一个正整数的平方，则a的最小值为362。

?72?7、已知2011是一素数，则??=_-1_。

2011??2aba2?b2,?a2?b2a2?ba?b)或(?,?222a?b222aba2?b2)，其中a与b是不全为

三、计算题

10

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可以取值t1 = 1，t2 = 2，t3 = 3。相应的x，y，z的值是

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

四、证明题

1、已知2011是质数，则有2011|99????9。 ??2010个2011

证明：99=10-1≡0 (mod 2011)。 ???9???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是两个不同的质数，且ap-1≡1 (mod q), aq-1≡1 (mod p), 证明：apq≡a (mod pq)。

11

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

又由题设aq-1≡1 (mod p)得到：apq≡(aq)p≡ap (aq-1)p≡ap≡a (mod p)。 同理可证：apq≡a (mod q)。故：apq≡a (mod pq)。

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

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

?mn(1? ?（mn）111)(1?)?(1?) p1p2pk111)(1?)?(1?) p1p2pk?（[m,n]）?[m,n](1?又mn=（m,n）[m,n]

?（m,n)[m,n](1?故?（mn）111)(1?)?(1?)?(m,n)?([m,n])。 p1p2pk 类似的题：设m=m1m2，m1与m由相同的质因数，证明：?(m)=m2?(m1)。

初等数论练习题六

一、填空题

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

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

|40!，即3α‖40!，则α=_18_。 3、设3α∣40!,而3α+1?4、形如3n+1的自然数中，构成模8的一个完全系的最小那些数是{1,4,7,10,13,16,19，22}。

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

6、21x≡9 (mod 43)的解是x≡25 (mod 43)。 7、??73?? = -1。 ?199?二、计算题 1、将

17写成三个既约分数之和，它们的分母分别是3，5和7。 10517xyz???，即35x ? 21y ? 15z = 17，因(35, 21) = 7，(7, 15) = 1，1?17，故解：设

105357有解。

12

分别解 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??? 1053572、若3是质数p的平方剩余，问p是什么形式的质数？

p?1?3?2解：∵ 由二次互反律??p???(?1)???p????， ?3??p?注意到p>3，p只能为p??1(mod 3)且????3?p?1(mod4)?1? ?1p??1(mod4)?∴

?p?1(mod3)?3?只能下列情况 ???1??p?p?1(mod4)???d)?p??1(mo3 ?

d)?p??1(mo4∴ p?1(mod12)或p??1(mod12)。 3、判断不定方程x2+23y=17是否有解？

解：只要判断x2≡17(mod 23) 是否有解即可。 ∵ 17≡1(mod 4) ∴ ??17??23??6??2??3??3??17??2????????????????????????1 23???17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解，即原方程无解。 三、论证题

1、试证对任何实数x,恒有〔x〕+〔x+〕=〔2x〕 证明：设x=[x]+α,0?α<1

①当0?α<

1211时, [x +]=[x], [2x]=2[x] ∴等式成立 221212②当?α< 1时, [x +]=[x]+1, [2x]=2[x]+1 ∴等式成立 故对任何实数x,恒有[x]+[x+]=[2x]。

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

n

12 13

|（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），2

3m

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

n

mn

m

m

n

m

n

m

n

mnmn

mnmn

于是 2

mn

=pd + 1=qd – 1,p,q∈Z。所以：（q -p）d =2。

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

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

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

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

m

n

初等数论练习题七

一、单项选择题

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

[a,b][a,b],)=（ A ） ab14

A．1 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除的余数是_1__。（欧拉定理） 2、同余方程3x≡5(mod13)的解是x≡5(mod13)。 3、(365)=1。 18474、［-π］＝-4。

5、为使n-1与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+1,k∈Z。 6、如果一个正整数具有21个正因数，问这个正整数最小是26×32=576。 7、同余方程x3+x2-x-1≡0(mod 3)的解是x≡1,2(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。

15

2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？

解：设士兵有x人，由题意得x ? 1 (mod 3)，x ? ?2 (mod 5)，x ? 3 (mod 11)。

在孙子定理中，取 m1 = 3， m2 = 5， m3 = 11，m = 3?5?11 = 165，

M1 = 55，M2 = 33，M3 = 15， M1? = 1，M2? = 2，M3? = 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??????????? 143143143143?????????(?1)143?18?(?1)7?1143?1?223??1??143??????????1 ∴原方程有解。 ??

?7??3??7?四、证明题

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

(ⅰ) d0??(m)；

j

(ⅱ)对于任意的i，j，0 ? i, j ? d0 ? 1，i ? j，有a i??a (mod m)。 （1）

证明：(ⅰ) 由Euler定理，d0 ? ?(m)，因此，由带余数除法，有

?(m) = qd0 ? r，q?Z，q > 0，0 ? r < d0。 因此，由上式及d0的定义，利用欧拉定理得到

qd?r1 ?a?(m)?a0?ar(mod m)，

即整数r满足 a r ? 1 (mod m)，0 ? r < d0 。 由d0的定义可知必是r = 0，即d0??(m)。

(ⅱ) 若式(1)不成立，则存在i，j，0 ? i, j ? d0 ? 1，i ? j，使a i ? a j (mod m)。 不妨设i > j。因为(a, m) = 1，所以 ai ? j ? 0 (mod m)，0 < i ? j < d0。

16

这与d0的定义矛盾，所以式(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)，则bd ? 1 (mod m)。

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

若x > 0，y < 0，由式(1)知：1 ? b ax = b db ?cy = b d(b c) ?y ? b d (mod m)。 若x < 0，y > 0，由式(1)知：1 ? b cy = b db ?ax = b d(ba) ?x ? b d (mod m)。

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

(ⅰ) p?bd ? 1对于n的某个因数d < n成立； (ⅱ) p ? 1 ( mod n )。

|n，p > 2，则(ⅱ)中的mod n可以改为mod 2n。 若2?证明：记d = (n, p ? 1)，由b n ? 1，b p ? 1 ? 1 (mod p)，及第2题有

b d ? 1 (mod p)。

若d < n，则结论(ⅰ)得证。

若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 ）

17

A.

3n?15n?2 B.n?12n?1 C.2n?1n?15n?2 D.3n?1 二、填空题

1、σ（120）=360。 2、7355的个位数字是3。

3、同余方程3x≡5(mod14)的解是x≡11(mod14)。 4、（

1723）=1。 5、［-2］＝-2。

6、如果一个正整数具有6个正因数，问这个正整数最小是12。 7、同余方程x3+x2-x-1≡0(mod 5)的解是x≡±1(mod5)。 三、计算题

1、已知563是素数，判定方程x2 ? 429 (mod 563)是否有解。

解：把??429??563??看成Jacobi符号,我们有

?429?1563?14292?1?429?2.2??563??563??1348??563???(?1)?429?????429??????429?????2??67??429????429???(?1)?67??429??67?1429?27?1????67????(?1)2.12??429?????2.67?12??429??67??429??67??????27??67????(?1)?67??27?????67??27??

27?1???13???(?2.13?12??27??27?1)?13?????1??13???1， 故方程x2 ? 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)；

18

-）

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

|n时，5∣1＋2＋3＋4。 故当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

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，使得

am+bn≡1(mod ab)。

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

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

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

ppa?b其中0?k?p-1。又?ap?1?ap?2b???abp?2?bp?1?bp?1?bp?1???bp?1?pbp?1m(oda?bkk

a?b)。

p-1 ap?bp令(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。

19

初等数论练习题九

一、单项选择题

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除的余数是1。

2、同余方程3x≡5(mod16) 的解是x≡7(mod16)。 3、不定方程9x－12y=15的通解是x = -1 + 4t，y = -2 +3t，t?Z。 4、??323?? =1。 41??B.（2n－1，2n＋1）=1 D.（2n＋1，n－1）=1

5、实数的小数部分记为{x} ，则 {－}＝0.75。

6、为使3n与4n＋1 的最大公因数达到最大可能值，整数n应满足条件n=3k+2，k∈Z。 7、如果一个正整数具有35个正因数，问这个正整数最小是26×34=5184。 三、计算题

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)

20

54

?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 = {x1, x2, ?, xm}是模m的一个完全系，以{x}表示x的小数部分，若(a, m) = 1，

ax?b求?{i}。

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

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

m?1m?1m?1axi?bjjj1m(m?1)m?1 {}?{k?}?{}????。????mmm22i?1j?0j?1mj?1mm3、设整数n ? 2，求：

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

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

a1, a2, ?, a?(n)，(ai, n) = 1，1 ? ai ? n ? 1，1 ? i ? ?(n)， 则 (n ? ai, n) = 1，1 ? n ? ai ? n ? 1，1 ? i ? ?(n)，

因此，集合{a1, a2, ?, a?(n)}与集合{n ? a1, n ? a2, ?, n ? a?(n)}是相同的，于是

a1 ? a2 ? ? ? a?(n) = (n ? a1) ? (n ? a2) ? ? ? (n ? a?(n))，

2(a1 ? a2 ? ? ? a?(n)) = n?(n)， 因此：a1 ? a2 ? ? ? a?(n) =n?(n)。 4、设m > 1，(a, m) = 1，x1, x2, ?, x?(m)是模m的简化剩余系，求：?{axi}。

i?112?(m)m 21

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

解：设axi = mqi ? ri，0 ? ri < m，由xi通过模m的简化剩余系知：axi也通过模m的简化剩

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

?(m)?(m)?(m)axiriri1?(m)11{}?{q?}??r?m?(m)??(m)。 ????iimmmm2m2i?1i?1i?1i?1四、证明题

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

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

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

2、设p是素数，证明：

(ⅰ) 对于一切整数x，xp ? 1 ? 1 ? (x ? 1) (x ? 2)?(x ? p ? 1) (mod p)； (ⅱ) (p ? 1)! ? ? 1 (mod p)。

证明：(ⅰ) xp ? 1 ? 1 ? 0 (mod p)有解x ? 1，2，?，p ? 1 (mod p)，

故对于一切整数x，xp ? 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?122nnn+1

? a(mod p)。

?a?2

)?a(modp)，即x ? a(mod p)有解。故 ??p???1。

??m（）?1。 4、证明：若p=4m+1是一质数，则pm4m?1 证明：（）?（）?()?(?1)pppp?12?(?1)2m?1。

p?12)!)? ?1 (mod p) 25、设p是奇质数，p ? 1 (mod 4)，则：(?(解 由Wilson定理有：

22

?1?(p?1)!?(?1)p?12(p?1)!?(?1)p?121?2?p?1p?1p?12 ?(p?1)?(?()!)(modp)。222注：（1）设p为质数且p＝4m+1，则同余方程x2??1(modp)的解是x??1?2?(2m)(modp)。 （2）设p为质数且p＝4m+1，若且唯若存在一个正整数a，使得 a2≡?1 (mod p)。

初等数论练习题十

一、单项选择题

1、设p是大于1的整数，如果所有不大于p的质数都不能整除p，则p一定是（ A ）。 A.素数 B.合数 C.奇数 D. 偶数 2、两个质数p，q，满足p+q=99，则A.9413 B.

9413 194pq?的值是（ B ） qpC.

94139413 D. 991113、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是整数，则有（a，p）=1或者p∣a。 2、设p是奇质数,(a,p)=1,则a是模p的平方非剩余的充要条件是a3、从1000开始到2010结束的所有整数中13的倍数有78个。 4、2756839-1的末位数是7。

5、不定方程ax+by=c有解的充要条件是(a, b)?c。

p?12??1(modp)

6、写出模12的一个最小非负简化系，要求每项都是7的倍数，此简化系为{7,35,49,77}。 7、已知563是质数，则?三、计算题

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

23

?2??=-1。 ?563?3?解：∵ 由二次互反律????(?1)?p???p?12?p????， ?3??3???1p??1p?1(mod3)注意到p>3，p只能为p??1(mod 4)且? ????

p??1(mod3)∴

?3??p?1(mod3) ，只能是下列情况???1?p?????p?1(mod4)p??1(mo3d) ? ?d)?p??1(mo4∴ 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?modp?

证明：存在性：因为p?7是一个素数，由Wilson定理我们有：?p?1?!?1?0?modp?，

然而?p?1?!??p?1??p?2??p?3??p?4??p?5??p?6?!??120?p?6?!?modp?，所以120?p?6?!??p?1??0?modp?，

故存在x?p?1，使得120?p-6?!?x?0?modp?。

唯一性：若还存在y??1,2,?,p?1?且120?p-6?!?y?0?modp?， 则x?y?modp?，注意到x,y??1,2,?,p?1?，所以x?y是唯一的。

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?12??1?mod9901? 即 9901(174950?1)。

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

24

55n?1?510n?1?12?5p?12?1(modp) 这样就转化为证明：(5)?1。

p 证明：因为(5)?(p)?(10n?1)?(?1)?1(modp)。

p555 所以55n?1?510n?1?12?5p?12?1(modp)。 故：p55n?1?1。

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

11

23

251

-1）。

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

即1?2q?12p

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

11

23

251

当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?modp?知：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) 25

本文来源：https://www.bwwdw.com/article/1pur.html