当前位置:首页 >> 政史地 >> 初等数论练习题答案

初等数论练习题答案


初等数论练习题答案

信阳职业技术学院
2010 年 12 月

初等数论练习题一
一、填空题 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 6、分母是正整数 m 的既约真分数的个数为_?(m)_。 7、18100 被 172 除的余数是_256。 8、 ?
? 65 ? ? =-1。 ? 103 ?

t?Z。.

9、若 p 是素数,则同余方程 x p ? 1 ?1(mod p)的解数为 p-1 二、计算题 1、解同余方程:3x2?11x?20 ? 0 (mod 105)。 解:因 105 = 3?5?7,



同余方程 3x ?11x?20 ? 0 (mod 3)的解为 x ? 1 (mod 3),
2

同余方程 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)是否有解?
2 3 7 )( )( ) 107 107 107 107 107 3?1 107?1 7 ?1 107?1 ? ? 2 3 107 2 7 107 2 2 2 ? ( ) ? ?1,( ) ? (?1 ) ( ) ?? ( ) ? 1,( ) ? (?1 )2 2 ( ) ?? ( ) ? ?1 107 107 3 3 107 7 7 42 ? ( ) ?1 107 2 ? 3? 7 解: ( 42 ) ? ( ) ? (

故同余方程 x2≡42(mod 107)有解。 3、求(127156+34)28 除以 111 的最小非负余数。
2

解:易知 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 为正整数,试证 a 证明 设 a = 2m ? 1,当 n = 1 时,有 a2 = (2m ? 1)2 = 4m(m ? 1) ? 1 ? 1 (mod 23),即原式成立。 设原式对于 n = k 成立,则有 其中 q?Z,所以
2n
a a a

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

a2

k

? 1 (mod 2k + 2) ? a 2 = 1 ? q2k + 2,
k

a2

k ?1

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

其中 q ?是某个整数。这说明式(1)当 n = k ? 1 也成立。 由归纳法知原式对所有正整数 n 成立。 3、设 p 是一个素数,且 1?k?p-1。证明: C kp ?1 ? (-1 )k(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!,p)=1,故 A = C kp ?1 ? (-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

(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= 2 2 +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?
n

9、若 p 是质数,n?p ? 1,则同余方程 x n ? 1 (mod p) 的解数为 n . 二、计算题 1、试求 2002 2003
2004

被 19 除所得的余数。 20022≡11(mod 19) 20023≡1 (mod 19)

解:由 2002≡7 (mod 19)

又由 20032004≡22004≡(22)1002≡1 (mod 3)可得:
2002 2003
2004

≡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。

4

三、证明题 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<a,b<s。则
10 s ? 1 (10 a )b ? 1 10 a ? 1 ps ? 11 ? 1? ? ? ? M ,其中 M>1 是正整数。 ? ? ? 9 9 9 s

由 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 为质数的( A.必要但非充分条件 C )条件。 C.充要条件 D.既非充分又非必要条件 D ) 。

B.充分但非必要条件
b a

2、设 n 是正整数,以下各组 a,b 使 为既约分数的一组数是( A.a=n+1,b=2n-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 A

D.a=3n+1,b=5n+2 ) 。

3、使方程 6x+5y=C 无非负整数解的最大整数 C 是( A.19 B.24 C.25 D.30 D ) 。

4、不是同余方程 28x≡21(mod 35)的解为( A.x≡2(mod 35) B. x≡7(mod 35)

C. x≡17(mod 35) D. x≡29(mod 35)
5

5、设 a 是整数,(1)a≡0(mod9)

(2)a≡2010(mod9)

(3)a 的十进位表示的各位数字之和可被 9 整除 (4)划去 a 的十进位表示中所有的数字 9,所得的新数被 9 整除 以上各条件中,成为 9|a 的充要条件的共有( A.1 个 二、填空题 1、σ (2010)=_4896____; ? (2010)=528。
20 2、数 C100 的标准分解式中,质因数 7 的指数是_3。

C ) 。

B.2 个

C.3 个

D.4 个

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 的同余方程,故原方程不可能有六个解。
3 2 n ?1 2、设 n 是正整数,求 C1 的最大公约数。 2n , C 2n , ? , C 2n

1 3 2 n ?1 1 3 2 n ?1 2 n ?1 解:设 (C2n , C2n ,?, C2n ) ? d,由C2n ? C2n ? ? ? C2n ? 2 知 d?22n?1,

设 2k|n 且 2k+1 ? | n,即 2k +1||n , 则由 2k +1|| C2n 及2
1 k ?1

| Ci 2n ?

2n i ?1 C2n ?1 ,i = 3, 5, ?, 2n ? 1 i

得 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。 于是 x 应为其中使 18x ? 1 (mod 77)成立的最小数,经计算知:x=30。
6

四、证明题 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}之间等于、大于、小于三种关系都有可能出现。
1 1 时,{xy}={x}{y}= ; 2 4 3 1 3 1 当 x= , y= 时,{xy}= ,{x}{y}= ,此时{xy}>{x}{y}; 2 2 4 4 1 1 1 1 当 x=- ,y=- 时,{xy}= ,{x}{y}= ,此时{xy}<{x}{y}。 2 3 6 3 c c 4、证明:存在一个有理数 ,其中 d < 100,能使 [k ] =[k 73 ] d d 100
+

当 x=y=

对于 k=1,2,….,99 均成立。 证明:由(73,100)=1 以及裴蜀恒等式可知:存在整数 c,d,使得 73d-100c=1 从而
73 k c k (73d ? 100 c) k = ,由 k< 100 可知: k- = 100 100 d 100 d d
7

0< 设 [k

73 kc 1 k- < 100 d d

c ] =n,则 k c <n+1= n ? 1 d ,于是 d d d
73 kc?1 n ?1 ? k< d =n+1, 100 d d



[k

73 ] = n = [k 100

c ]。 d

初等数论练习题四
一、单项选择题 1、若 Fn= 2 2 ? 1 是合数,则最小的 n 是( D A. 2 B. 3 C. 4
n

)。 D. 5 )。

2、记号 ba‖a 表示 ba|a,但 ba+1 ? | a. 以下各式中错误的一个是( B A. 218‖20! B. 105‖50! C. 119‖100!

D. 1316‖200! A )。

3、对于任意整数 n,最大公因数(2n+1,6n-1)的所有可能值是( 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) A ) D.a=b+mt,t∈Z

5、如果 a≡b(mod m),c 是任意整数,则下列错误的是( A.ac≡bc(mod mc) 二、填空题 1、d(10010)=_32__,φ(10010)=_2880__。 B.m|a-b C.(a,m)=(b,m)

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、 ?
? 54 ? ? =_-1_。 ? 89 ?
8

三、计算题 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, 由于 0 ? x, y ? 9,所以由式(1)与式(2)分别得出 x ? y ? 1 = 9 或 18, 3 ? y ? x = 0 或 11。 (1)

11?n ? 11?z ? 5 ? 4 ? y ? x ? 3 ? 1 = 3 ? y ? x ? 11?3 ? y ? x。 (2)

?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 ?1 i ?1

m

m

m(m ? 1) (mod m)。 2

9

(1)当 m 为奇数时,由

m m(m ? 1) m ?1 m(m ? 1) ,故 ? ai ? ? 0 (mod m)。 ? Z 即得: m 2 2 2 i ?1 m

(2)当 m 为偶数时,由(m,m+1)=1 即得: ? ai ?
i ?1

m(m ? 1) m ? (mod m)。 2 2
?(m)

2、证明:若 m>2,a1, a2, ?, a?(m)是模 m 的任一简化剩余系,则

?a
i ?1

i

?0(mod m).

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

的一个简化剩余系,于是:

? ai ? ? (m ? ai )(mod m). 从而: 2 ? ai ?m? (m)(mod m).
i ?1 i ?1 i ?1

? (m)

?(m)

又由于 m>2,?(m)是偶数。故:

?(m)
i ?1

?a

i

?m

?(m)
2

? 0(mod m).

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 ?1 i ?1

m

m

m(m ? 1) m ? (mod m)。 2 2

(1) (2)

同理

? bi
i ?1

m

?

m (mod m)。 2

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

联合上式与式(1)和式(2),得到

0?

m m m ? ? (mod m), 2 2 2

这是不可能的,所以{a1 ? b1, a2 ? b2, ?, am ? bm}不能是模 m 的完全剩余系。 4、证明: (1)2730∣x13-x; (3)504∣x9-x3; (2)24∣x(x+2)(25x -1); (4)设质数 p>3,证明:6p∣xp-x。
2

证明: (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;
10

由 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 C. (m,n)=1,则 my ? nx B. m≠n,则 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 )。 D.2k(k 为正整数) )。

3、n 为正整数,若 2n-1 为质数,则 n 是( A A.质数 B.合数 C.3

4、从 100 到 500 的自然数中,能被 11 整除的数的个数是( B A.33 B.34 C.35 D.36

5、模 100 的最小非负简化剩余系中元素的个数是( C )。 A.100 二、填空题 1、同余方程 ax+b≡0(modm)有解的充分必要条件是(a,m)∣b。
2、高斯称反转定律是数论的酵母,反转定律是指设 p 与 q 是不相同的两个奇质数,

B.10

C.40

D.4

( q ) ? (?1) 2 2 ( p )
p q

p ?1 q ?1 ?

3、20122012 被 3 除所得的余数为_1__。 4、设 n 是大于 2 的整数,则(-1) ? (n)=__1__。 5、单位圆上的有理点的坐标是 (? 零的整数。 6、若 3258×a 恰好是一个正整数的平方,则 a 的最小值为 362。
? 72 ? 7、已知 2011 是一素数,则 ? ? =_-1_。 ? 2011 ?
2ab a ?b
2 2

,?

a2 ? b2 a ?b
2 2

) 或 (? a 2 ? b 2 , ?
a ?b

2

2

2ab a2 ? b2

) ,其中 a 与 b 是不全为

三、计算题
11

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)
1 3

显然 x = 0,y = 25 是方程(1)的解,因此,方程(1)的一般解是
? 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个

证明: 99 ? ?? ? 9 =10 ? ?
2010个

2011

-1≡0 (mod 2011)。

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

? p ? a ? ? ? a ? ? ?1? ? ? ? p ? ?=? ? ? ? ? ?=? ? ? ? p ? ? p ?

p ?1 ?a? 2 ? ? p? ? = (?1) ? ?

?a? ? ? p? ? =1 ? ?

即:p-a 也是 p 的平方剩余。 3、已知 p,q 是两个不同的质数,且 ap-1≡1 (mod q), aq-1≡1 (mod p), 证明:apq≡a (mod pq)。
12

证明:由 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) ? mn(1 ?

1 1 1 )(1 ? )?(1 ? ) p1 p2 pk 1 1 1 )(1 ? )?(1 ? ) p1 p2 pk

?([m, n]) ? [m, n](1 ?
又 mn=(m,n)[m,n]

? (m, n)[ m, n](1 ? 故 ?(mn)

1 1 1 )(1 ? )?(1 ? ) ? (m, n)? ([ m, n]) 。 p1 p2 pk

类似的题:设 m=m1m2,m1 与 m 由相同的质因数,证明:?(m)=m2?(m1)。

初等数论练习题六
一、填空题 1、为了验明 2011 是质数,只需逐个验算质数 2,3,5,…p 都不能整除 2011,此时,质 数 p 至少是_43___。 2、最大公因数(4n+3,5n+2)的可能值是_1,7__。 3、设 3α∣40!,而 3α+1 ? | 40!,即 3α‖40!,则α =_18_。 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。 105

解:设 有解。

17 x y z ? ? ? ,即 35x ? 21y ? 15z = 17,因(35, 21) = 7,(7, 15) = 1,1?17,故 105 3 5 7

13

分别解 5x ? 3y = t 得

7t ? 15z = 17

x = ?t ? 3u,y = 2t ? 5u,u?Z, t = 11 ? 15v,z = ?4 ? 7v,v?Z, x = ?11 ? 15v ? 3u, y = 22 ? 30v ? 5u, z = ?4 ? 7v, u,v?Z。
17 4 ? 8 3 ? ? ? 105 3 5 7

消去 t 得

令 u =0,v =-1 得到:x =4,y =-8,z=3。即:

2、若 3 是质数 p 的平方剩余,问 p 是什么形式的质数?
p ?1 ?3? ? p? 2 解:∵ 由二次互反律 ? ? ? ( ? 1 ) ?? ?, ? ?

? p?

?3?

注意到 p>3,p 只能为 p ? ? 1(mod 3)且 ?
? p ? 1(mod 3) ?3? ? ?p? ? ? 1 只能下列情况 ? p ? 1(mod 4) ? ? ?

? p ? ?1 ??? ? 3 ? ?? 1

p ? 1(mod 4) p ? ?1(mod 4)



d) ? p ? ?1( m o 3 ? d) ? p ? ?1( m o 4

∴ 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?α <
1 2 1 1 时, [x + ]=[x], 2 2 1 2 1 2

[2x]=2[x]

∴等式成立 ∴等式成立

②当 ?α < 1 时, [x + ]=[x]+1, [2x]=2[x]+1 故对任何实数 x,恒有[x]+[x+ ]=[2x]。 2、证明: (1)当 n 为奇数时,3∣(2 +1) ;
n

1 2

| (2 +1) (2)当 n 为偶数时,3 ? 。
14

n

证明:由 2 +1≡(-1) +1(mod 3)立得结论。 3、证明: (1)当 3∣n(n 为正整数)时,7∣(2 -1) ;
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) ,
mn mn n m n m n m n

mn

mn

mn

mn

2 =(td-1)

mn

m

于是 2 =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.1 B.a
[a, b] [a, b] , ) =( a b

A ) D.(a,b)
15

C.b

2、176 至 545 的正整数中,13 的倍数的个数是( A.27 B.28 C.29

B ) D.30

3、200!中末尾相继的 0 的个数是( A ) A.49 B.50 C.51 D.52 )

4、从以下满足规定要求的整数中,能选取出模 20 的简化剩余系的是( B A.2 的倍数
21n ? 4 14 n ? 3

B.3 的倍数
n ?1 2n ? 1

C.4 的倍数
2n ? 1 5n ? 2

D.5 的倍数 A )
n ?1 3n ? 1

5、设 n 是正整数,下列选项为既约分数的是( A. B. C. D.

二、填空题 1、314162 被 163 除的余数是_1__。 (欧拉定理) 2、同余方程 3x≡5(mod13)的解是 x≡5(mod13)。 3、 ( 365 ) =1。
1847

4、 [-π ]=-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 t = 41 ? 3v z=v 消去 t 得 x = 41 ? 3v ? 2u y=u z=v u,v?Z。 v?Z, u?Z,

由此得原方程的全部正整数解为 (x, y, z) = (41 ? 3v ? 2u, u, v),u > 0,v > 0,41 ? 3v ? 2u > 0。 2、有一队士兵,若三人一组,则余 1 人;若五人一组,则缺 2 人;若十一人一组,则余 3
16

人。已知这队士兵不超过 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 人。
2 3、判断同余方程 x ? 286(mod 443) 是否有解?

解:286=2×143,433 是质数,(143,443)=1 奇数 143 不是质数,但可用判定雅可比符号计算的勒让德符号

? 286 ? ? 2 ?? 143 ? ? ??? ?? ? ? (?1) ? 443 ? ? 243 ?? 443 ?

4432 ?1 2

? (?1)

143?1 443?1 ? 2 2

? 443 ? ? 14 ? ? 2 ?? 7 ? ? ??? ??? ?? ? ? 143 ? ? 143 ? ? 143 ?? 143 ?
∴原方程有解。

? (?1)

143?1 8

? (?1)

7 ?1 143?1 ? 2 2

3? ?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 ? r 1 ? a ? ( m) ? a 0 ? a r (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。

这与 d0 的定义矛盾,所以式(1)必成立。
17

2、证明:设 a,b,c,m 是正整数,m > 1,(b, m) = 1,并且 b a ? 1 (mod m),b c ? 1 (mod m) 记 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 )。 若 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 < n,则结论(ⅰ)得证。 若 d = n,则 n?p ? 1,即 p ? 1 (mod n),这就是结论(ⅱ)。 若 2? | n,p > 2,则 p ?1 (mod 2)。由此及结论(ⅱ),并利用同余的基本性质,
得到 p ? 1 (mod 2n)。

(1)

初等数论练习题八
一、单项选择题 1、设 n > 1,则 n 为素数是(n ? 1)! ? ?1 (mod n)的( C ) 。 A.必要但非充分条件 C.充要条件 B.充分但非必要条件 D.既非充分又非必要条件 ) D.37

2、小于 545 的正整数中,15 的倍数的个数是( C A.34 B.35 D C.36 ) C.81

3、500!的标准分解式中 7 的幂指数是( A.79 B.80

D.82 D ) D.-1,1,-3,3

4、以下各组数中,成为模 10 的简化剩余系的是( A.1,9,-3,-1 B.1,-1,7,9

C.5,7,11,13 A )

5、设 n 是正整数,下列选项为既约分数的是(

18

A.

3n ? 1 5n ? 2

B.

n ?1 2n ? 1

C.

2n ? 1 5n ? 2

D.

n ?1 3n ? 1

二、填空题 1、σ (120)=360。 2、7355 的个位数字是 3。 3、同余方程 3x≡5(mod14)的解是 x≡11(mod14)。 4、 (
17 )=1。 23

5、 [- 2 ]=-2。 6、如果一个正整数具有 6 个正因数,问这个正整数最小是 12。 7、同余方程 x3+x2-x-1≡0(mod 5)的解是 x≡±1(mod5)。 三、计算题 1、已知 563 是素数,判定方程 x2 ? 429 (mod 563)是否有解。
? 429 ? 解:把 ? ? 看成 Jacobi 符号,我们有 ? 563 ?
? 429 ? ? ? ? (?1) ? 563 ?
429?1 563?1 . 2 2

? 563 ? ? 563 ? ? 134 ? ? 2 ?? 67 ? ? ??? ??? ??? ?? ? ? (?1) ? 429 ? ? 429 ? ? 429 ? ? 429 ?? 429 ?

4292 ?1 8

? 67 ? ? ? ? 429 ?

-



? 67 ? ? ?? ? ? ?(?1) ? 429 ?

67?1 429?1 . 2 2

? 429 ? ? 429 ? ? 27 ? ? ? ? ?? ? ? ?? ? ? ?(?1) ? 67 ? ? 67 ? ? 67 ?

27?1 67?1 . 2 2

? 67 ? ? 67 ? ? ??? ? ? 27 ? ? 27 ?

? 13 ? ? ? ? ? (?1) ? 27 ?

27?1 13?1 . 2 2

? 27 ? ? 1 ? ? ? ? ? ? ? 1, ? 13 ? ? 13 ?

故方程 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);
19

当 m 为奇数时,1n+2n+3n+4n?0(mod 5); 当 m 为偶数时,1n+2n+3n+4n?4(mod 5)。 故当 4 ? | n 时,5∣1n+2n+3n+4n 。 四、证明题 1、证明:若质数 p>2,则 2P-1 的质因数一定是 2pk+1 形。 证明:设 q 是 2 p -1 的质因数,由于 2 p -1 为奇数,∴ q≠2, (2,q)=1。 由条件 q|2p-1,即 2 p ≡1(mod q) 。 设 h 是使得 2 x ≡1(mod q)成立最小正整数,若 1<h<p,则有 h|p。这与 p 为质 数矛盾。从而 h=p, ∴ 2p|q-1,q-1=2pk, 2、设(m,n)=1,证明:m
?(n)

于是

p|q-1。又∵ q-1 为偶数,2|q-1,

即 q=2pk+1 k∈Z。
?(m)

+n

≡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)。 3、设(a,b)=1,a+b≠0,p 为一个奇质数,证明: (a ? b,
ap ?bp ) ? 1或p 。 a?b

p p 说明:事实上,设 (a ? b, 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 其中 0?k?p-1。 又 a ? b ? 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

k

k

a?b

a ? b) 。

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

a?b

(否则设(d,b)=d′>1,立即得到 d′︱a 和 d′︱b,这与(a,b)=1 矛盾。 )
于是(d ,b
p-1

)=1。故 d | p,即

d =1 或 p。

20

初等数论练习题九
一、单项选择题 1、以下 Legendre 符号等于-1 的 30 被-1 是(
3? A. ? ? ? ? 11 ? 4? B. ? ? ? ? 11 ? 5? C. ? ? ? ? 11 ?

D

)
6? D. ? ? ? ? 11 ?

2、100 至 500 的正整数中,能被 17 整除的个数是( B A. 23 B. 24 C. 25 C )

) D. 26

3、设 3? |500!,但 3??1 ? ,则α =( | 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)。

B.(2n-1,2n+1)=1 D.(2n+1,n-1)=1

3、不定方程 9x-12y=15 的通解是 x = -1 + 4t,y = -2 +3t,t?Z。 4、 ?
? 323 ? ? =1。 ? 41 ?

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 知原方程有解。原方程化为 即 3x ? 8y = t, 3t -5z = 1000,
21

5 4

9x ? 24y = 3t, 3t -5z = 1000

(1) (2)

解(2)得

?t ? 5u , u?Z, ? ? z ? ?200 ? 3u

再解 3x ? 8y =5u 得到

? x ? ?u ? 8v , u,v?Z。 ? ? y ? u ? 3v
? x ? ?u ? 8v ? , u, v?Z。 ? y ? u ? 3v ? z ? ?200 ? 3u ?



2、设 A = {x1, x2, ?, xm}是模 m 的一个完全系,以{x}表示 x 的小数部分,若(a, m) = 1, 求 ?{
i ?1 m

axi ? b }。 m

解:当 x 通过模 m 的完全剩余系时,ax ? b 也通过模 m 的完全剩余系,因此对于任意的 i(1 ? i ? m) ,axi ? b 一定与且只与某个整数 j(1 ? j ? m)同余,即存在整数 k,使 得 axi ? b = km ? j, (0 ? j ? m-1) 。从而:
ax ? b j j j 1 m(m ? 1) m ? 1 ?{ m } ? ?{k ? m} ??{ m} ? ? m ? m ? 2 ? 2 。
m m ?1 j ?0 m ?1 j ?1 m ?1 j ?1 i i ?1

3、设整数 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 ?1

1 2

? (m)

m

22

其中{x}表示 x 的小数部分。 解:设 axi = mqi ? ri,0 ? ri < m,由 xi 通过模 m 的简化剩余系知:axi 也通过模 m 的简化剩 余系,从而 ri 通过模 m 的最小非负简化剩余系,于是:
? ( m)
i ?1

ax ?{ m } ? ?{q
i i ?1

? ( m)

i

?

? ( m) ? ( m) ri } ? ? ri ? 1 ? ri ? 1 m? (m) ? 1 ? (m) 。 m m i ?1 2m 2 i ?1 m

四、证明题 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 3、证明:若 2 ? | n,p 是奇质数,p∣a -1,则 ? ? p? ? ? 1。 ? ?

证明:由 p∣a -1 知:a ? 1(mod p)。又(p,a)=1 得到 a 因为 2 ? | n,所以 (a
n ?1 2 2

n

n

n+1

? a(mod p)。

?a? 2 ) ? a(mod p) ,即 x ? a(mod p)有解。故 ? ? p? ? ? 1。 ? ?

m 4、证明:若 p=4m+1 是一质数,则 ( ) ? 1。 p
m 4m ?1 证明: ( ) ? ( ) ? ( ) ? (?1) p p p
p ?1 2

? (?1) 2 m ? 1 。
p ?1 2 )!) ? ?1 (mod p) 2

5、设 p 是奇质数,p ? 1 (mod 4),则: (?( 解 由 Wilson 定理有:

23

? 1 ? ( p ? 1)!? (?1)

p ?1 2

( p ? 1)!? (?1)

p ?1 2

1 ? 2?

p ?1 p ?1 p ?1 2 ?( p ? 1) ? (?( )!) (mod p) 。 2 2 2

注: (1) 设 p 为质数且 p=4m+1, 则同余方程 x 2 ? ?1(mod p) 的解是 x ? ?1 ? 2?(2m)(mod p) 。 (2)设 p 为质数且 p=4m+1,若且唯若存在一个正整数 a,使得 a2≡?1 (mod p)。

初等数论练习题十
一、单项选择题 1、设 p 是大于 1 的整数,如果所有不大于 p 的质数都不能整除 p,则 p 一定是( A.素数 B.合数 C.奇数
p q ? 的值是( q p

A ) 。

D. 偶数 B ) D. C ) D.334
9413 111

2、两个质数 p,q,满足 p+q=99,则 A.9413 B.
9413 194

C.

9413 99

3、2010!的标准分解式中,7 的最高幂指数为( A.331 B.332 C.333

4、n 为正整数,若 2n+1 为质数,则 n 是( A.质数 B.合数 C.1 B

D ) D.2k(k 为非负整数)

5、当 n>2 时,欧拉函数?(n)一定是( A.奇数 二、填空题 B.偶数

) 。 D.2

C.1

1、如果 p 是质数,a 是整数,则有(a,p)=1 或者 p∣a。 2、设 p 是奇质数,(a,p)=1,则 a 是模 p 的平方非剩余的充要条件是 a 3、从 1000 开始到 2010 结束的所有整数中 13 的倍数有 78 个。 4、2756839-1 的末位数是 7。 5、不定方程 ax+by=c 有解的充要条件是(a, b)?c。 6、写出模 12 的一个最小非负简化系,要求每项都是 7 的倍数,此简化系为{7,35,49,77}。 7、已知 563 是质数,则 ? 三、计算题 1、若 3 是质数 p 的平方剩余,问 p 是什么形式的质数?
24
p ?1 2

? ?1(mod p)

? 2 ? ? =-1。 ? 563 ?

3? 解:∵ 由二次互反律 ? ? ? p? ? ? (?1) ? ?

p ?1 2

? p? ?? ?, ?3?
p ? 1(mod 3) p ? ?1(mod 3)
?? 1

p ? ?1 注意到 p>3,p 只能为 p ? ? 1(mod 4)且 ? ? ??? ?3?



?3? ? p ? 1(mod 3) ? ?p? ? ? 1 ,只能是下列情况 ? ? ? ? p ? 1(mod 4)

d) ? p ? ?1( m o 3 ? 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 ? , 则 x ? y ? mod p ? ,注意到 x, y ? ?1, 2,? , p ? 1? ,所以 x ? y 是唯一的。 2、已知 9901 是素数,试证: 9901 (17
4950

? 1) 。

证明:由 9901 是素数,计算 Legendre 符号得:
17 ?19901?1 7 ?117 ?1 3?17 ?1 ? 17 ? ? 9901 ? ? 7 ? ? 17 ? ? 3 ? ?7? ?1? ? ? ? ? ?1? 2 2 ? ? ? ? ? ? ? ?1? 2 2 ? ? ? ? ? ? ? ?1? 2 2 ? ? ? ? ? ? ? ?1 ? 9901 ? ? 17 ? ? 17 ? ? 7 ? ?7? ? 3? ? 3?

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

17

9901?1 2

? ?1? mod 9901?



9901 (17 4950 ? 1) 。

3、证明:若 p=10n-1 是个质数,则 p 5 5 n ?1 ? 1 。 (提示:利用勒让德符号解决。 ) 说明:要证 p 5 5 n ?1 ? 1 ,只需证明 55 n ?1 ? 1(mod p) ,即证:

25

55n?1 ? 5
证明:因为 5

10n ?1?1 2

?5

p ?1 2

? 1(mod p)

这样就转化为证明: ( 5 ) ? 1。
p

p 10n ?1 ?1 ( )?( )?( ) ? ( ) ?1(mod p) 。 p 5 5 5
5 n ?1

所以 5

?5

10n ?1?1 2

?5

p ?1 2

? 1(mod p) 。 故: p 5 5 n ?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? 2
q ?1 2

p ?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 ? 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)

26


更多相关文档:

初等数论练习题答案

初等数论练习题答案_教育学_高等教育_教育专区。初等数论练习题答案 原点教育培训学校 初等数论练习题一一、填空题 1、d(2420)=12; ? (2420)=_880_ 2、设 a...

初等数论课后习题答案

初等数论课后习题答案_理学_高等教育_教育专区。初等数论课后习题答案初等数论(闵嗣鹤)》习题解答 2010 修改版 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

初等数论练习题答案

初等数论练习题答案_政史地_高中教育_教育专区。初等数论练习题答案 信阳职业技术学院 2010 年 12 月 初等数论练习题一一、填空题 1、d(2420)=12; ? (2420)...

《初等数论》第三版习题解答

3 ? 5 ? 7 有唯一解 33 / 77 《初等数论习题解答(第三版) 35M 1? ...参考答案:一.单项选择:ABCDD;DACCB;DCAAD;BCBAB。 二. 填空题: 21. 21;...

02013初等数论练习题及答案

02013初等数论练习题答案_理学_高等教育_教育专区。本人认真做过的初等数论习题,其中有相应的答案,为广大考生尽一点绵薄之力。初等数论练习题一一、填空题 1、 ...

初等数论练习题答案

初等数论练习题答案_高一数学_数学_高中教育_教育专区。n 初等数论练习题一一、填空题 1、d(2420)=12; ? (2420)=_880_ 2、设 a,n 是大于 1 的整数,若...

王进明__初等数论_习题解答

王进明__初等数论_习题解答_理学_高等教育_教育专区。王进明为 454.求被除数. ...即为答案. 此题也可先考虑 10 个灯泡。用归纳得出“只有完全平方数”的结论...

初等数论练习题一(含答案)

初等数论练习题一(含答案)_理学_高等教育_教育专区。《初等数论》期末练习二一、单项选择题 1、 (0, b) ? (). A b B ?b C b D 0 ). 2、如果 (...

自考初等数论试题及答案

暂无评价|0人阅读|0次下载|举报文档 自考初等数论试题及答案_财会/金融考试_资格考试/认证_教育专区。初等数论考试试卷 1 一、单项选择题(每题 3 分,共 18 分...

初等数论练习题二(含答案)

初等数论练习题二(含答案)_理学_高等教育_教育专区。《初等数论》期末练习一一、单项选择题 1、如果 b a , a b ,则( ). A a?b B a ? ?b C a?b...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com