tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

《初等数论(闵嗣鹤、严士健)》第三版习题解答


《初等数论》习题解答(第三版)广东石油化工学院

第一章 整数的可除性 § 整除的概念· 1 带余除法 1. 证 明 定 理 3 定理 3

? ? 若 a1,a2, ,an 都 是 m 得 倍 数 , q1,q2, ,qn 是 任 意 n 个 整 数 , 则

q1a1 ? q2 a2 ? ? ? qn an 是 m 得 倍 数 .
证明:? a1 , a2 ? , an 都是 m 的倍数。

? 存在 n 个整数 p1 , p2 ,? pn 使 a1 ? p1m, a2 ? p2 m, ?, an ? pn m
又 q1 , q2 ,? , qn 是任意 n 个整数

? q1a1 ? q2 a2 ? ? ? qn an ? q1 p1m ? q2 p2 m ? ? ? qn pn m ? ( p1q1 ? q2 p2 ? ? ? qn pn )m
即 q1a1 ? q2 a2 ? ? ? qn an 是 m 的整数 2.证明 3 | n(n ? 1)(2n ? 1) 证明 ? n( n? 1 ) ( 2? n

1 ) n n? ? (

1n? ? 2 ? )( n
1)

1)

? n( n ? 1 ) ( ? 2 ) n ? 1 ) n ( n ? ( n ?

又? n(n ? 1)(n ? 2) , (n ? 1)n(n ? 2) 是连续的三个整数 故 3| n(n ? 1)(n ? 2), 3| (n ?1)n(n ? 1)

? 3| n(n ? 1)(n ? 2) ? (n ?1)n(n ? 1)
从而可知

3 | n(n ? 1)(2n ? 1)

3.若 ax0 ? by0 是形如 ax ? by (x,y 是任意整数,a,b 是两不全为零的整数)的数中最小 整数,则 (ax0 ? by0 ) | (ax ? by ) .

1 / 77

《初等数论》习题解答(第三版)广东石油化工学院

证: ? a, b 不全为 0

?在整数集合 S ? ?ax ? by | x, y ? Z ? 中存在正整数,因而有形如 ax ? by 的最小整数
ax0 ? by0
?x, y ? Z ,由带余除法有 ax ? by ? (ax0 ? by0 )q ? r , 0 ? r ? ax0 ? by0
则 r ? ( x ? x0 q)a ? ( y ? y0 q)b ? S ,由 ax0 ? by0 是 S 中的最小整数知 r ? 0

? ax0 ? by0 | ax ? by ? ax0 ? by0 | ax ? by
( x, y 为任意整数) ? ax0 ? by0 | a, ax0 ? by0 | b

? ax0 ? by0 | (a, b). 又有 (a, b) | a , (a, b) | b

? (a, b) | ax0 ? by0 故 ax0 ? by0 ? (a, b)
4.若 a,b 是任意二整数,且 b ? 0 ,证明:存在两个整数 s,t 使得

a ? bs ? t ,

| t |?

|b| 2

成立,并且当 b 是奇数时,s,t 是唯一存在的.当 b 是偶数时结果如何? 证:作序列 ? , ?

3b 2

,? b ,?

b 2

, 0,

b 2

,b,

3b 2

,? 则 a 必在此序列的某两项之间

即存在一个整数 q ,使

q q ?1 b ?a? b 成立 2 2 q q , t ? a ? bs ? a ? b ,则有 2 2

(i ) 当 q 为偶数时,若 b ? 0. 则令 s ?

b q q q 0 ? a ? bs ? t ? a ? b ? a ? b ? b ? t ? 2 2 2 2
若 b ? 0 则令 s ? ? , t ? a ? bs ? a ?

q 2

b q b ,则同样有 t ? 2 2

(ii) 当 q 为奇数时,若 b ? 0 则令 s ?

q ?1 q ?1 , t ? a ? bs ? a ? b ,则有 2 2
2 / 77

《初等数论》习题解答(第三版)广东石油化工学院

?

b 2

? t ? a ? bs ? a ?

b q ?1 q ?1 b?a? b ? 0? t ? 2 2 2

若 b ? 0 ,则令 s ? ?

b q ?1 q ?1 综上所述,存在性 , t ? a ? bs ? a ? b ,则同样有 t ? 2 , 2 2

得证. 下证唯一性 当 b 为奇数时,设 a ? bs ? t ? bs1 ? t1 则 t ? t1 ? b( s1 ? s ) ? b 而t ?

b 2

, t1 ?

b 2

? t ? t1 ? t ? t1 ? b 矛盾 故 s ? s1 , t ? t1
b 为整数 2

当 b 为偶数时, s, t 不唯一,举例如下:此时

3?

b b b b b ? b ?1 ? ? b ? 2 ? (? ), t1 ? , t1 ? 2 2 2 2 2

§ 最大公因数与辗转相除法 2 1.证明推论 4.1 推论 4.1 a,b 的公因数与(a,b)的因数相同. 证:设 d ? 是 a,b 的任一公因数,? d ? |a, d ? |b 由带余除法

a ? bq1 ? r1 , b ? r1q2 ? r2 ,? , rn ?2 ? rn ?1qn ? rn , rn ?1 ? rn qn ?1 , 0 ? rn ?1 ? rn ? rn ?1 ? ? ? r1 ? b

? (a, b) ? rn ? d ? | a ? bq1 ? r1 , d ? | b ? r1q2 ? r2 ,┄, d ? | rn ?2 ? rn ?1qn ? rn ? (a, b) ,
即 d ? 是 (a, b) 的因数。
3 / 77

《初等数论》习题解答(第三版)广东石油化工学院

反过来 (a, b) | a 且 (a, b) | b ,若 d ?? |(a, b), 则 d ?? | a, d ?? | b ,所以 (a, b) 的因数都是 a, b 的公因 数,从而 a, b 的公因数与 (a, b) 的因数相同。 2.证明:见本书 P2,P3 第 3 题证明。 3.应用§ 习题 4 证明任意两整数的最大公因数存在,并说明其求法,试用你的所说的求 1 法及辗转相除法实际算出(76501,9719) . 解:有§ 习题 4 知: 1

?a, b ? Z , b ? 0, ?s, t ? Z , 使 a ? bs ? t ,| t |?

b 。 , 2

??s1 , t1 ,使 b ? s1t ? t1 ,| t1 |?
?sn , tn , tn?2 ? tn ?1sn ? tn ; ?sn ?1 , tn ?1 , tn ?1 ? tn sn ?1 ? tn ?1 ;
且 | tn |?

|t | b ? ,?, 如此类推知: 2 22

| tn?1 | | tn?2 | |t | |b| ? 2 ? ? ? n ? n?1 2 2 2 2

而 b 是一个有限数,??n ? N , 使 tn?1 ? 0

? (a, b) ? (b, t ) ? (t , t1 ) ? (t1 , t2 ) ? ? ? (tn , tn?1 ) ? (tn , 0) ? tn ,存在其求法为: (a, b) ? (b, a ? bs) ? (a ? bs, b ? (a ? bs) s1 ) ? ?

? (76501,9719) ? (9719, 76501 ? 9719 ? 7) ? (8468,9719 ? 8468) ? (1251,8468 ? 1251? 6) ?? ? (3,1) ?1
4.证明本节(1)式中的 n ?

log b log 2
4 / 77

《初等数论》习题解答(第三版)广东石油化工学院

证:由 P3§ 习题 4 知在(1)式中有 1

0 ? rn?1 ? rn ?
?1 ?

rn?1 rn?2 r b ? 2 ? ? ? n1?1 ? n ,而 rn?1 2 2 2 2

b n , ?2 ? , b 2n

?n ? l o gb ? 2

log b log b ,即 n ? log 2 log 2

§ 整除的进一步性质及最小公倍数 3 1.证明两整数 a,b 互质的充分与必要条件是:存在两个整数 s,t 满足条件 ax ? bt ? 1 . 证明 必要性。若 (a, b) ? 1 ,则由推论 1.1 知存在两个整数 s,t 满足: as ? bt ? (a, b) ,

?as ? bt ? 1
充分性。若存在整数 s,t 使 as+bt=1,则 a,b 不全为 0。 又因为 (a, b) | a, (a, b) | b ,所以 (a, b | as ? bt ) 又 (a, b) ? 0 ,? (a, b) ? 1 2.证明定理 3 定理 3 即 (a, b) |1 。

? a1 , a2 ?, an ? ? ?| a1 |,| a2 | ?,| an |?

证:设 [a1 , a2 ,?, an ] ? m1 ,则 ai | m1 (i ? 1, 2,?, n) ∴ | ai || m1 (i ? 1, 2,?, n) 又设 [| a1 |,| a2 |,?,| an |] ? m2 则 m2 | m1 。反之若 | ai || m2 ,则 ai | m2 ,? m1 | m2 从而 m1 ? m2 ,即 [a1 , a2 ,?, an ] = [| a1 |,| a2 |,?,| an |]2 3.设 an x n ? an ?1 x n ?1 ? ? ? a1 x ? a0 (1)

是一个整数系数多项式且 a0 ,an 都不是零,则(1)的根只能是以 a0 的因数作分子以 an 为 分母的既约分数,并由此推出 2 不是有理数. 证:设(1)的任一有理根为

p , ( p, q) ? 1, q ? 1 。则 q
5 / 77

《初等数论》习题解答(第三版)广东石油化工学院

p p p an ( ) n ? an ?1 ( ) n ?1 ? ? ? a1 ? a0 ? 0 q q q
an p n ? an?1 p n ?1q ? ? ? a1 pq n ?1 ? a0 q n ? 0
由 (2) ? an p n ? an ?1 p n ?1q ? ? ? a1 pq n ?1 ? a0 q n , 所以 q 整除上式的右端,所以 q | an p n ,又 ( p, q) ? 1, q ? 1 , 所以 (q, p n ) ? 1,? q | an ; 又由(2)有 an p n ? an ?1 p n ?1q ? ? ? a1 pq n ?1 ? ?a0 q n 因为 p 整除上式的右端,所以 P | a0 q n , ( p, q) ? 1, q ? 1 ,所以 (q n , p) ? 1, 故(1)的有理根为 (2)

∴p | an

p ,且 p | a0 , q | an 。 q

假设 2 为有理数, x ? 2,? x 2 ? 2 ? 0 ,次方程为整系数方程,则由上述结论,可知其 有有理根只能是

?1, ?2 ,这与 2 为其有理根矛盾。故 2 为无理数。
另证,设 2 为有理数 2 =

p , ( p, q) ? 1, q ? 1 ,则 q

p2 2 ? 2 ,? 2q 2 ? p 2 ,? ( p 2 , q 2 ) ? (2q 2 , p 2 ) ? q 2 ? 1 q
但由 ( p, q) ? 1, q ? 1 知 ( p 2 , q 2 ) ? 1,矛盾,故 2 不是有理数。 § 质数· 4 算术基本定理 1.试造不超过 100 的质数表 解:用 Eratosthenes 筛选法 (1)算出 100 ? 10 a (2)10 内的质数为:2,3,5,7
6 / 77

《初等数论》习题解答(第三版)广东石油化工学院

(3)划掉 2,3,5,7 的倍数,剩下的是 100 内的素数 将不超过 100 的正整数排列如下: 1 11 21 31 41 51 61 71 81 91 2 3 12 13 22 23 32 33 42 43 52 53 62 63 72 73 82 83 92 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6 16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 10 19 20 29 30 39 40 49 50 59 60 69 70 79 80 89 90 99 100

2.求 82798848 及 81057226635000 的标准式. 解:因为 8|848,所以 8 | A, A ? 82798848 ? 8 ?10349856 ? 23 ? B , 又 8|856,所以 8|B, B ? 8 ?1293732 ? 23 ? C , 又 4|32,所以 4|C, C ? 4 ? 323433 ? 22 ? D 又 9|(3+2+3+4+3+3) ,所以 9|D, D ? 9 ? 35937 ? 32 ? E , 又 9|(3+5+9+3+7) ,所以 9|E, E ? 9 ? 3993 又 3993 ? 3 ?1331 ? 3 ?113 所以 A ? 2835113 ; 同理有 81057226635000 ? 23 ? 33 ? 54 ? 73 ?112 ?17 ? 23 ? 37 。 3.证明推论 3.3 并推广到 n 个正整数的情形. 推论 3.3 设 a,b 是任意两个正整数,且
? ? ? a ? p1 1 ? p2 2 ?? ? pn n , ? i ? 0 , i ? 1, 2,?, k ,

? ? b ? p1?1 ? p2 2 ?? ? pn n , ?i ? 0 , i ? 1, 2,?, k ,
? ? ? ? ? ? 则 (a, b) ? p1 1 ? p2 2 ?? ? pk k , [a, b] ? p1 1 ? p2 2 ?? ? pk k ,

7 / 77

《初等数论》习题解答(第三版)广东石油化工学院

其中 ? i ? min(? i , ?i ) , ? i ? min(? i , ?i ) , i ? 1, 2,?, k 证:? ? i ? min(? i , ?i ) ,? 0 ? ? i ? ? i , 0 ? ? i ? ?i ∴ ∴

pi ? i | pi?i , pi? i | pi?i (i ? 1, 2 ? k )
? ? pi i
i ?1 k

? ? ? pi i , ? pi i
i ?1 i ?1

k

k

?p
i ?1

k

?i

i

.

∴ ∴ 推广

? ? ? ? ? ? p1 1 p2 2 ? pk k | (a, b) ,又显然 (a, b) | p1 1 p2 2 ? pk k
? ? ? ? ? ? p1 1 p2 2 ? pk k ? (a, b) ,同理可得 p1 1 p2 2 ? pk k ? [a, b] , ? i ? max{?i , ?i }

? ? ? ? ? ? 设 a1 ? p1?11 p2 12 ? pk 1k , a2 ? p1?21 p2 22 ? pk 2 k , ? , an ? p1?n1 p2 n 2 ? pk nk

(其中 p j 为质数 j ? 1, 2,?, k , ai 为任意 n 个正整数 i ? 1, 2,?, n, ?ij ? 0 ),
? ? p1? i1 p2 i 2 ? pk ik ? (a1 , a2 ,? , an ), ? ij ? min{?ij },
1?i ? n



j ? 1, 2,? , k

? ? ? p1 i1 p2 i 2 ? pk ik ? [a1 , a2 ,? , an ], ? ij ? max{?ij }, j ? 1, 2,? , k
1?i ? n

4.应用推论 3.3 证明§ 的定理 4(ii) 3
? ? ? ? ? 证:设 a ? p1 1 p2 2 ? pk k ,b ? p1?1 p2 1 ? pk k ,

其中 p1, p2, ?, pk 是互不相同的素数,?i,?i(1 ? i ? k)都是非负整数,有
? ? (a, b) ? p1?1 p21 ? pk k , ?i ? min{? i , ? i }, 1 ? i ? k, ? [a, b] ? p1?1 p2 1 ? pk?k , ?i ? max{? i , ? i }, 1 ? i ? k。

由此知(a, b)[a, b] =

? pi?i ??i ? ? pimin{?i ,?i }?max{?i ,?i } ? ? pi?i ??i =ab;从而有 [a, b] ?
i ?1 i ?1 i ?1

k

k

k

ab . ( a, b)

5.若 2n ? 1 是质数(n>1) ,则 n 是 2 的方幂. 证: (反证法)设 n ? 2k l (l 为奇数) ,
n 2 ?l 2 l 2 2 则 2 ? 1 ? 2 ? 1 ? (2 ) ? 1 ? (2 ? 1)[2
k k k k

?( l ?1)

? 22

k

?( l ? 2)

? ? ? 1]

8 / 77

《初等数论》习题解答(第三版)广东石油化工学院



1 ? 2 ? 1 ? (2 ) ? 1 ? 2 ? 1 ,
2k 2k l n

∴ 2n ? 1为合数矛盾,故n一定为2的方幂. § 函数[x],{x}及其在数论中的一个应用 5 1. 求 30! 的 标 准 分 解 式 . 解 : 30 内 的 素 数 为 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

?2 ? ? ? ? ? 2 ? ? ? 3 ? ? ? 4 ? ? ? 5 ? ?? ? 2 ? ?2 ? ?2 ? ?2 ? ?2 ?
? 15 ? 4 ? 3 ?1 ? 0 ? 23

? 30 ? ? 30 ? ? 30 ? ? 30 ? ? 30 ?

?3 ? ?

? 30 ? ? 30 ? ? 30 ? ? 30 ? ? 2 ? 3 ? 4 ? ? ? 10 ? 3 ? 1 ? 0 ? 14 ? 3 ? ?3 ? ?3 ? ?3 ? ? ? ? ? ? ? ?

?5 ? ? ? ? ? 2 ? ? ? 3 ? ? ? ? 6 ? 1 ? 0 ? 7 ? 5 ? ?5 ? ?5 ?
? 7 ? ? ? ? ? 2 ? ? ? ? 4 ? 0 ? 4 , ?11 ? ? ? ? ? 2 ? ? ? ? 2 ? 0 ? 2 ? 7 ? ?7 ? ? 11 ? ?11 ?
? 30 ? ? 30 ? ? 30 ? ? 30 ?

? 30 ? ? 30 ? ? 30 ?

?13 ? ?

? 30 ? ? 30 ? ? 30 ? ? 30 ? ? ? ?132 ? ? ? ? 2 ? 0 ? 2 , ?13 ? ? 13 ? ? ?132 ? ? ? ? 2 ? 0 ? 2 ? 13 ? ? ? ? ? ? ? ? 30 ? ? 30 ?

?17 ? ? ? ? ? 2 ? ? ? ? 1 ? 0 ? 1 , ?19 ? ?19 ? ? 23 ? ? 29 ? 1 ? 17 ? ?17 ?


30! ? 223 ? 314 ? 55 ? 74 ?112 ?132 ?17 ?19 ? 23 ? 29

2.设 n 是任一正整数,?是实数,证明:

(i)

? ? n? ? ? ? ? ? ?? ? ? n ?

(ii)

?? ? ? ?? ? ?
?

1? n ? 1? ? ? ? ??? ? ?? ? n ? ? ? n? ? n? ? ?

证:(i)设 [? ] ? m .则由性质 II 知 m ? ? ? m ? 1 ,

9 / 77

《初等数论》习题解答(第三版)广东石油化工学院

所以

nm ? n? ? nm ? n ,
[n? ] ? m ? 1 ,又在m与m+1之间只有唯一整数m, n

所以 nm ? [n? ] ? nm ? n ,所以 m ?

所以 [

[n? ] ] ? m ? [? ] . n
(ii) [证法一]设

k k ?1 ? {? } ? , k ? 0,1, 2,?, n ? 1 , n n

则 k ? n{?} ? k ? 1,?[n? ] ? n[? ] ? k ①当 i ? k ? n ? 1时, {? } ?

i k ?1? i i ? ? 1,[? ? ] ? [? ] ; n n n i k ?i i ? ? 1,[? ? ] ? [? ] ? 1 ; n n n

②当 i ? k ? n 时, 2 ? {? } ?

1 n ?1 ?[? ] ? [? ? ] ? ? ? [? ? ] n n n ?1 n ?1 1 n ?1? k i i ? ? [? ? ] ? ? [? ? ] ? ? [? ? ] n n i ?n?k n i ?0 i ?0 ? (n ? k )[? ] ? k ([? ] ? 1) ? n[? ] ? k
n ?1 i ? ? [? ? ] ? [n? ] n i ?0

[证法二] 令 f (? ) ?

?[? ? n ] ? [n? ] ,
i ?0

n ?1

i

n ?1 1 i ?1 ? f (? ? ) ? ? [? ? ] ? [n? ? 1] ? f (? ) n n i ?0

n ?1 1 i ?1 ? f (? ? ) ? ? [? ? ] ? [n? ? 1] ? f (? ) n n i ?0

? f (? ) 是以

1 为周期的函数。 n
10 / 77

《初等数论》习题解答(第三版)广东石油化工学院

又当 ? ?[0,1)时, f (? ) ? 0 ? 0 ? 0,?? ? R, f (? ) ? 0 , 即

? [? ? n ] ? [n? ] 。
i ?0

n ?1

1

[评注]:[证一]充分体现了 常规方法的特点,而[证二]则表现了较高的技巧。 3.设 ? , ? 是任意二实数,证明: (i) (ii)

[? ] ? [? ] ? [? ? ? ] 或 [? ? ? ] ? 1

[2? ] ? [2? ] ? [? ] ? [? ? ? ] ? [ ? ]

证明: (i)由高斯函数[x]的定义有

? ? [? ] ? r, ? ? [? ] ? s,0 ? r ? 1;0 ? s ? 1 。则
? ? ? ?[ ?] ? [ ? ] ? ? r ? ?1 r s , s
当 r ? s ? 0时,[? ? ? ] ? [? ] ? [ ? ] 当 r ? s ? 0时,[? ? ? ] ? [? ] ? [ ? ] ? 1 故 [? ? ? ] ? [? ] ? [ ? ]或[? ? ? ] ? 1 ? [? ] ? [ ? ] (ii)设 ? ? [? ] ? x, ? ? [? ] ? y,0 ? x, y ? 1 , 则有 0 ? x ? y ? {?} ? {? } ? 2 下面分两个区间讨论: ①若 0 ? x ? y ? 1 ,则 [ x ? y] ? 0 ,所以 [? ? ? ] ? [? ] ? [? ] ,所以

[2? ] ? [2? ] ? [2[? ] ? 2 x] ? [2[ ? ] ? 2 y] ? 2[? ] ? 2[ ? ] ? 2([ x] ? [ y]) ? 2[? ] ? 2[ ? ] ? [? ] ? [? ] ? [? ] ? [? ] ? [? ] ? [? ? ? ] ? [? ]
②若 1 ? x ? y ? 2 ,则 [ x ? y] ? 1 ,所以 [? ? ? ] ? [? ] ? [? ] ? 1 。 所以

11 / 77

《初等数论》习题解答(第三版)广东石油化工学院

[2? ] ? [2 ? ] ? [2[? ] ? 2 x] ? [2[ ? ] ? 2 y] ? 2[? ] ? 2[ ? ] ? 2([ x] ? [ y ]) ? 2[? ] ? 2[ ? ] ? 2([ x] ? [1 ? x])
?x ?1? y ???? ?

? [? ] ? [ ? ] ? [ ? ] ? [? ] ? 2 ? 2([ x] ? [? x]) ? 2[? ] ? 2[ ? ] ? 1 ? [? ] ? [? ? ? ] ? [ ? ]
(ii) (证法 2)由于 ? , ? 对称,不妨设 {?} ? {? }

[2? ] ? [2? ] ? [2([? ] ? {?})] ? [2([ ? ] ? {? })]

? 2[? ] ? 2[? ] ? [2{?}] ? [2{? }]

? 2[? ] ? 2[ ? ] ? [{?} ? {? }]
? [? ] ? [? ] ? ([? ] ? [? ] ? [{?} ? {? }]) ? [? ] ? [? ] ? [[? ] ? {?} ? [? ] ? {? }]

? [? ] ? [? ? ? ] ? [ ? ]
4. (i) 设函数 在闭区间 Q ? x ? R 上是连续的,并且非负,证明:和式

表示平面区域 Q ? x ? R , 0 ? y ? f ( x) 内的整点(整数坐标的点)的个数. (ii) 设 p,q 是两个互质的单正整数,证明:

(iii) 设

,T 是区域

内的整点数,证明:

(iv) 设

,T 是区域




12 / 77

内的整点数,证明:

《初等数论》习题解答(第三版)广东石油化工学院

证明:(略) 5. 设 任一正整数,且 ,p 是质数, ,证明:在 的

标准分解式中,质因数 p 的指数是

其中

.

证明:在 的标准分解式中,质因数 p 的指数有限,即


所以



第二章 § 2.1

不定方程

习题

1、解下列不定方程

a) 1 5 ? 2 5? x y

1 0 0 b)306 x ? 360 y ? 630
13 / 77

《初等数论》习题解答(第三版)广东石油化工学院

解: a ) 原方程等价于: 3x ? 5 y ? 20 故一般解为

显然它有一个整数解 x0 ? 10, y0 ? ?2 ,

t ? x ? 1 0? 5 (t ? 0 ? 1 , ? , , ? 2 ? ? y ? ?2 ? 3t

)

b) 原方程等价于: 17 x ? 20 y ? 35 显然它有一个整数解 x0 ? ?7 ? 35, y0 ? ?6 ? 35
故一般解为

? t ? x ? ?7 ? 3 5 2 0 (t ? 0 ? 1 , ? , , ? 2 ? ? ? y ? ?6 ? 3 5 1t 7

)

2、把 100 分成两份,使一份可被 7 整除,一份可被 11 整除。 解:依题意 即求 7 x ? 11y ? 100 的正整数解,解得 x0 ? 8, y0 ? 4 一般解是: ?

? x ? 8 ? 11t (t ? 0, ?1,?) ? y ? 4 ? 7t
a x? b y ,N a 0 , ? ? b 0, ( a b ? , ? )

但除 t ? 0 外无其他正整数解,故有且只有 100 ? 56 ? 44 3、证明:二元一次不定方程 的非负整数解为

1

?N? ?N? ? ab ? 或 ? ab ? ? 1 ? ? ? ? ?N?

证明:当 N ? 0 时,原方程没有整数解,而 ? ? ? 1 ? 0 故命题正确 ? ab ? 当 N ? 0 时,原方程有且只有一个非负整数解 因为

? 0, 0 ?

而 ? ??0 ? ab ?

?N?

?N? ? ab ? ? 1 ? 1 ? ?

? a, b ? ? 1

所以

原方程有整数解 其中

? x0 , y0 ? , y0 ? (?1)n?1 ?q1 ,?, qn?1? N , x0 ? (?1)n ?q2 ,?, qn?1? N

a ? ? q1 , q2 , q3 , ?, qn ? ,由于 a ? b ? 0 ,故 x0 , y0 中一正一负,可设 x ? 0, y ? 0 b

原方程的一般解是: ?

? x ? x0 ? bt ? t ? 0, ?1,?? ? y ? y0 ? at
x0 y ?t ?? 0 , b a

要求 x0 ? bt ? 0, y0 ? at ? 0 ? 仅当 ?

y0 ? y ? ? y ? 是整数时,才能取 t ? ? ? 0 ? ,否则 t ? ? ? 0 ? a ? a? ? a?
14 / 77

《初等数论》习题解答(第三版)广东石油化工学院

故这个不等式的整数解个数 T 是 : 当是整数时 T ? ? 0 ? ? ? ? 0 ? ? 1 ? ? 0 ? ? ? 0 ? ? 1 ?b? ? a? ?b? ?a? 因而 ? ? ? ? 0 ? ? ? 0 ? ? T ? ? ? ? 1 ? ab ? ? b ? ? a ? ? ab ? 当

?x ? ? y ?

?x ? ?y ?

?N?

?x ? ?y ?

?N?

y0 ?x ? ? y ? ?x ? ? y ? 不是整数时 T ? ? 0 ? ? ? ? 0 ? ? ? 0 ? ? ? 0 ? ? 1 a ?b? ? a? ?b? ?a?

? ? x0 ? ? y0 ? ? ? ??? ? ?N? ? ?b? ?a ? 因而 ? ? ? ? ? ab ? ? ? x0 ? ? y0 ? ? ?1 ?? b ? ? a ? ?? ? ? ?

所以

? ( m)

证 明 2: 二 元 一 次 不 定 方 程 ax ? by = N 的 一 切 整 数 解 为 ? 是 由 x ? 0,y ? 0 得 ?

? x ? x0 ? bt , t ?Z , 于 ? y ? y0 ? at

y0 x y x N ,故 此 区 间 内 的 ? t ? 0 , 但 区 间 [? 0 , 0 ] 的 长 度 是 a b a b ab N N 整 数 个 数 为 [ ] 或[ ]? 1 。 ab ab
: 4、证明:二元一次不定方程 ax ? by ? N ,(a, b) ? 1, a ? 1, b ? 1 ,当 N ? ab ? a ? b 时有非负整数解, N ? ab ? a ? b 则不然。 证明:先证后一点,当 N ? ab ? a ? b 时,原方程有非负整数解 则 d ? (m1 , m2 ).

? x0 , y0 ?

? b x0 ? 1, a y0 ? 1 ? x0 ? 1 ? bk , y0 ? 1 ? ah, k ? 1, h ? 1

? ab ? k ? h ? ? ab, k ? h ? 2 ,这是不可能的。
次证, N>ab-a-b 时, 当 因(a, b)=1, 故原方程有整数解 0 , 0 )一般解是 (x y , 要求 x 0 -bt ? 0,y 0 ?at ? 0 ? ?

?

x ? x0 ? bt y ? y0 ? at

(t ? 0, ?1,?)

y0 x ? t ? 0 会证明存在满足这个不等式的整数 t ? t0 可取使 a b

x0 ? bt0 ? r (0 ? r ? b) 于是对于这个 t 0 有:
15 / 77

《初等数论》习题解答(第三版)广东石油化工学院

x ? bt0 ? r ? b ? 1 ? t0 ?

x ? b ?1 b



a 1 1 1 y0 ? at0 ? y0 ? ( x0 ? b ? 1) (by0 ? ax0 ? ab ? a) ? ( N ? ab ? a) ? (ab ? a ? b ? ab ? a) ? ?1 b b b b y ? y0 ? at0 ? 0 ? t0 ? ? 0 a
这就证明了当 N ? ab ? a ? b 时,原方程有非负整数解. 1. 证 明 定 理 2 推 论 。 推论 单位圆周上座标都是有理数的点(称为有理点) ,可以写成

2ab a 2 ? b2 a 2 ? b2 (? 2 2 , ? 2 2 ) 或 (? 2 2 , ? 22ab 2 ) a ?b a ?b a ?b a ?b
的形式,其中 a 与 b 是不全为零的整数。

证明:设有理数 x?

l n , y ? ( m ? 0) 满 足 方 程 x2 ? y2 = 1, 即 l2 ? n2 = m2, m m

于 是 得 l = ? 2 a b d, = ? ( a 2 ? b 2 ) d , = ? ( a 2 ? b 2 ) d 或 l = ? ( a 2 ? b 2 ) d , = ? 2a b d , n m m m = ? ( a 2 ? b 2 ) d , 由 此 得 ( x, y ) = ?

(

2 2 2ab a 2 ? b2 ,? 2 )或(? a2 ? b2 , ? 22ab 2 ) 。 反 之 , a 2 ? b2 a ? b2 a ?b a ?b

代 入 方 程 x2 ? y2 = 1 即 知 这 样 的 点 在 单 位 圆 周 上 。

2.求出不定方程 x 2 ? 3 y 2 ? z 2 , ( x, y) ? 1, x ? 0, y ? 0, z ? 0 的一切正整数解的公式。 解:设不定方程 x 2 ? 3 y 2 ? z 2 ,( x, y) ? 1 有解则 (1) 3/z-x 或 3/z+x 因为 3 y 2 ? z 2 ? x 2 ? ( z ? x)( z ? x)

? 3 / ( z ? x)( z ? x) ? 3 / z ? x 或 3/z+x

x

2

? 3y ? z ?
2

2

y

2

?

2 z?x z?x ? ? z ? x ? 或者 y ? ? z ? x ? ? 3 3

得3 / z ? x或3 / z ? x
以下不妨设 3 / z ? x
16 / 77

《初等数论》习题解答(第三版)广东石油化工学院

② ? x, z ? ? 1 , 设
2

( x , z? 则, ) d
2 2

d / x? / zy dz 3 ? ,d ?/ x
2

2

2

,

若,3 / d , ? 9 / x ,9 / z ? 9 / 3 y ? 3 / y ? 3 / ? x, y ? 与 ? x, y ? ? 1 矛盾!
这样 ? 3, d ? ? 1 ? d /

y

2

? d / y ? d / 3 y 而 d / x ? d / ? x, y ? ? d ? 1
2 2

?

?

③ ? z ? x, z ? x ? ? 1或2 , 设t ? ? z ? x, z ? x ? ? t / ( z ? x) ? ( z ? x) ? 2 x ,

t / ( z ? x) ? ( z ? x) ? 2 z ? t / ? 2 x.2 z ? ? 2 即
④若

t ? 1或t ? 2

? z ? x, z ? x ? ? 1, 则? ?
2

z?x ? , z ? x ? ? 1, ? 3 ?

从而3 y ? ? z ? x ?? z ? x ? ?
由引理可设

y

2

?

z?x 2 2 ? a , z ? x ? b , y ? ab 3

z?x ? ? z ? x? 3

从而 ? , 为证得 x, z 为整数,
2

? x, z ? ? 1,
2

必须有 a , b 均为奇数,且 3a ? b ⑤若 ? z ? x, z ? x ? ? 2 ? ?

?z?x z?x? ?z?x z?x? , , ? ?1? ? ? ?1 2 ? 2 ? ? 2 ? 6
2

2 z?x z?x ? y? 从而3 y ? ? z ? x ?? z ? x ? ? ? ? ? ? 6 2 ?2?



z?x 2 z?x 2 y 2 2 2 2 ?a , ? b , ? ab,即x ? 3a ? b , y ? 2ab, z ? 3a ? b , 6 2 2

其中 a, b 为一奇一偶,且有 ? a, b ? ? 1 4 . 解 不 定 方 程 : x 2 ? 3 y 2 = z 2 , x > 0, y > 0 , z > 0 , ( x , y ) = 1 。 解 : 设 ( z ? x , z ? x ) = d , 易 知 d = 1 或 2 。 由 ( z ? x) ( z ? x) = 3 y 2 得 z ? x = 3 d a 2 , z ? x = d b 2 , y = da b 或 z ? x = d b 2 , z ? x = 3 d a 2 , y = d a b, a > 0 , b > 0 , ( a , b ) = 1 。 ( ⅰ) 当 d = 1: x ?

| b 2 ? 3a 2 | b 2 ? 3a 2 , y ? ab, z ? ,a > 0, b > 0,(a, b ) = 2 2
当 d = 2 :x = |b 2 ? 3 a 2 |, y = 2 a b , z = b 2 ? 3 a 2 ,

1 , 3 ? b , a , b 同 为 奇 数 ; ( ⅱ) |

a > 0 , b > 0 , ( a , b ) = 1 , 3 b , a , b 一 奇 一 偶 。 反 之 , 易 验 证 ( ⅰ ) 或 ( ⅱ) 是 原
17 / 77

| ?

《初等数论》习题解答(第三版)广东石油化工学院

不 定 方 程 的 解 , 且 x > 0, y > 0, z > 0, (x, y) = 1。 3.证明不等式方程

x ? y ? z , ? x, y ? ? 1, x ? 0, y ? 0, z / x 的一切正整数解.
2 2 4
2 2 4 4 2

可以写成公式: x ? 4ab(a ? b ), y ? ∣ a ? b ? 6a 其中 a ? 0, b ? 0, ? a, b ? ? 1, a, b一单一双

b

2

∣, z ? a ? b
2

2

证明:由定理 1 知道原方程的解是 x ? 2cd , y ? c ? d , z ? c ? d ,
2 2 2 2

c ? d ? 0, ? c, d ? ? 1 , 且 c, d 为一奇一偶,
其中, c ? 2ab, d ? a ? b , a ? b ? 0, ? a, b ? ? 1 , 且 a, b 为一奇一偶.
2 2

所以 x ? 4ab(a ? b ), y ? ∣ a ? b ? 6a
2 2 4 4 2

2

b

2

∣, z ? a ? b 是原方程的正整数解
2 2

( x ? 0, y ? 0, z ? 0, ? x, y ? ? 1, 2 / x, 且a ? b 是奇数 ,
2

原方程正整数的解有:

? ?0, a , ?a? , ? ?a ,0, ?a ? ? ?4ab(a ? b ), ?(a ? b ? 6a b ), ?(a ? b )? , ? ?(a ? b ? 6a b ), ?4ab(a ? b ), ?(a ? b )? ,
00 ? 0,,? ,
4

2

2

2

2

4

4

2

2

2

2

4

2

2

2

2

2

2

6. 求 方 程 x2 ? y2 = z4 的 满 足 (x, y ) = 1, 2?x 的 正 整 数 解 。 解 : 设 x , y, z 是 x 2 ? y 2 = z 4 的 满 足 ( x , y) = 1 , 2 ? x 的 正 整 数 解 , 则 x = 2 a b, y = a2 ? b2, z2 = a2 ? b2, a > b > 0, (a, b) = 1, a, b 一 奇 一 偶 , 再 由 z2 = a2 ? b 2 得 a = 2 u v, b = u 2 ? v 2 , z = u 2 ? v 2 或 a = u 2 ? v 2 , b = 2 u v , z = u 2 ? v 2 , u > v > 0 , u , v ) = 1 , v 一 奇 一 偶 , 是 得 x = 4 u v( u 2 ? v 2 ) , = |u 4 ? v 4 ? 6 u 2 v 2 |, ( u, 于 y z = u 2 ? v 2 , u > v > 0, ( u , v ) = 1 , u , v 一 奇 一 偶 。 反 之 , 易 验 证 它 是 原 不 定 方 程 的 整 数 解 , 且 x > 0 , y > 0, z > 0 , ( x , y ) = 1 , 2 ? x 。 其中正负号可任意选取. 第三章 同余

? 1 同余的概念及其基本性质

18 / 77

《初等数论》习题解答(第三版)广东石油化工学院

1、 证明(i)若 ??1?? k ? ???1 ?k (modm) x i ? y i (modm)、i=1,2,、,k 、、 则

? ? ?
,?,

? ? ??1?? k x1 1 ? x1 k ?
k

? ?? ?
1,?,? k

1 ,?,? k

? ? y1 1 ? yk k (modm)

特别地,若 ai ? bi (modm) ,i=0,1, ?, n 则

an x n ? an ?1 x n ?1 ? ? a0 ? bn x n ? bn ?1 x n ?1 ? ? ? b0 (modm)
(ii)若 a ? b(modm),k ? 0,? ak ? bk (mod mk ), (iii)若 a ? b(modm),d 是 a,b 及 m 的任一正公因数,则 (iv)若 a ? b(modm), d m , d ? 0. 则 a ? b(modd). 证明 : (i)据性质戊,由 xi ? yi (mod m), i ? 1, 2,?, k. 得 xi?i ? yi?i (mod m), i ? 1, 2,?, k , 进一步,则
? ? ? ? ??1?? k x1 1 ? xk k ? B?? ?? k y1 1 ? yk k (mod m)
1

a b m ? (mod ), b d d

最后据性质丁,可得:

? ? ?
,?,

? ? ??1?? k x1 1 ? x1 k ?
k

? ?? ?
1,?,? k

1 ,?,? k

? ? y1 1 ? yk k (modm)

(ii) 据定理 1,a ? b(modm) ? m a ? b ,

? k ? 0,? mk k (a ? b) ? ka ? kb
又据定理 1,即得 ka ? kb(mod mk ). (iii)据定理 1, a ? b(modm) ? m a ? b , 即 a-b=ms(s ? z)

? d a, b, m , d ? 0,?

a ?b m a b m ? s ,即 ? ? ? s, d d d d d a b m 仍据定理 1,立得 ? (mod ), b d d
(iv) 据定理 1, a ? b(modm) ? a ? a ? ms,( s ? z ),
19 / 77

《初等数论》习题解答(第三版)广东石油化工学院

又? d m ,? m ? dt , t ? z, 故 a ? b ? ms ? d (st ), st ? z,

? a ? b(mod d ).
2、设正整数 a ? an10n ? an ?110n ?1 ? ? a0 , 0 ? ai ? 10 试证 11 整除的充分且必要条件是 11 整除

? (?1) a .
i ?1 i

n

i

证明 :?10 ? ?1(mod11),?由上题(i)的特殊情形立得

a ? an10n ? an ?110n ?1 ? ? a0 ? an (?1) n ? an ?1 (?1) n ?1 ?? a0 (mod11)

a ? ? (?1)i ai (mod11),
i ?0

n

?11 a ? 11

? (?1) a .
i ?0 i

n

i

3.找出整数能被 37,101 整除有判別条件来。 解:?1000 ? 1(mod37) 故正整数 a ? ak 1000k ? ak ?11000k ?1 ? ? a0 , 0 ? ai ? 1000 立得 37 a ? 37

?a .
i ?0 i

k

?100 ? ?1(mod101).
故设正整数 a ? bs 100s ? bs ?1100s ?1 ? ?b0 , 0 ? bi ? 100 ' , 立得 101 a ? 101

? (?1) b .
i i ?0 i

s

4、证明 641 | 232 ? 1
8 证明:∵ 2 ? 256 ? mod 641?

20 / 77

《初等数论》习题解答(第三版)广东石油化工学院
16 2 ∴ 2 ? 256 ? 65536 ? 154 ? mod 641? 32 2 ∴ 2 ? 154 ? 23716 ? ?1? mod 641?

即 641 ∣ 232 ? 1 5、若 a 是任一单数,则 a
2n

? 1? mod 2 n ? 2 ? , ? n ? 1?

证明: (数学归纳法)设 a ? 2m ? 1 (1) n ? 1 时, a 2 ? ? 2m ? 1? ? 4m ? m ? 1? ? 1 ? 1? mod 8 ? ,
2

结论成立。 (2)设 n ? k 时,结论成立,即:

? 2m ? 1?
而 a2
k ?1

2k

?1 ? 0 ? mod 2k ?2 ? ? ? 2m ? 1? ?1 ? 2k ?2 t , ? t ? z ?
2k

?1 ? a2 ?1 a2 ? 1 ? a2 ?1 a2 ?1 ? 2
k k k k

?

??
2

? ?
3

??

?

? ? 2k ? 2 t ? ? 2 ? 2k ? 2 ? t
k ? t 2 ? 2 2 ? 4 t ? 2k ? ?

? t ? 2k ?3 ? t ? 2k ?1 ? 1? ? 0 ? m o dk ? 3 ? 2
故 n ? k ? 1 时,结论也成立;∴ n ? 1时,结论也成立。 证明:若 2 ? a,n 是正整数,则 a 2 ? 1 (mod 2n + 2)。 |
n

(4)

设 a = 2k ? 1,当 n = 1 时,有 a2 = (2k ? 1)2 = 4k(k ? 1) ? 1 ? 1 (mod 23), 即式(4)成立。 设式(4)对于 n = k 成立,则有

a 2 ? 1 (mod 2k + 2) ? a 2 = 1 ? q2k + 2,
其中 q?Z,所以

k

k

a 2 = (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3),
其中 q ?是某个整数。这说明式(4)当 n = k ? 1 也成立。 由归纳法知式(4)对所有正整数 n 成立。

k ?1

21 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? i ?1535625 ;

? ii ?1158066

3 4 解: ? i ?1535625 ? 3 ? 5 ? 7 ?13 ;

? ii ?1158066 ? 2 ? 3272 ?13 ?101
§ 2 剩余类及完全剩余系

1、 证明 x ? u ? p s ?t v , u ? 0,1, 2,?, pt ? 1 , t ? s 是模 p s 的一个完全剩余类。 证明:显然对 u, v 的不同取值, x 共有 p s ?t ? pt ? p s 个值,故只需证这样的 p s 个值,关于模 p s 的两两互不同余。 若 u1 ? p s ?t v1 ? u2 ? p s ?t v2 mod p s

?

?

? u1 ? u2 ? p s ?t ? v1 ? v2 ? ? mod p s ?

? p s ?t ∣ u1 ? u2 ,即 u1 ? u2 ? mod p s ?t ? ? u1 ? u2
? p s ?t v1 ? p s ?t v2 ? mod p s ? ? v1 ? v2 ? mod p t ? ? v1 ? v2
∴ u1 ? u2 或 v1 ? v2 时,

u1 ? ps ? t v ? u? 1 2

? s

p

t

?vm o d ? p .结论成立。
s 2

2、 若 m1 , m2 ,?, mk 是 k 个两两互质的正整数, x1 , x2 ,? , xk 分别通过模 m1 , m2 ,?, mk 的完全剩 余类,则

M1 x 1? M x ? ? ? M k xk 2 2
通过模 m1m2 ? mk ? m 的完全剩余系,其中 m ? mi M i , i ? 1, 2,?, k 证明: (数学归纳法) (1) 根据本节定理 3,知 k ? 2 时,结论成立。

, (2) 设 对 整 数 k ? 1 , 结 论 成 立 , 即 若 m1 , m2?

,m 两 两 互 质 , 令 k? 1

, s ' ? M1 x' ? M x 2 ' ? ? ? M k ? xk ? ',当 x1 ,x2 , ? x 1 2 1 1
余系时, s ' 必过模

k1 ?

分别通过模 m1 , m2 ,? , mk ?1 的完全剩

m' ? m1m2 ...mk ?1 的完全剩余系,其中 mi M i' ? m' (i ? 1, 2...k ? 1) 。
22 / 77

《初等数论》习题解答(第三版)广东石油化工学院

现增加 mk , 使 (mi , mk ) ? 1 (i ? 1,...k ?1) , 令 M i ? M k mk (1,...k ? 1) , m' ? M k ? m1m2 ...mk ?1 , m ? mk M k ? m1m2 ...mk 则易知 (m1 , m2 ,..., mk ) ? (mk , M k ) ? 1, 再令 x ? M k xk ? mk s ' , 当 xk 过 模 mk 的 完 全 剩 余 系 , s ' 过 模 M k 的 完 全 剩 余 系 时 , 据 本 节 定 理 3 , x 必 过 模

m ? mk M k ? m1m2 ... mk 的完全剩余系,即对 k 结论成立。

3n ?1 ? 1 ) 中每一个整数有而且只有一种方法表示成 3、 (i)证明整数 ? H ,... ? 1, ?0,1,..., H ( H ? 3 ?1
3n xn ? 3n ?1 xn ?1 ? ...3x ? x0 ............. ?
的形状,其中 xi ? ?1, 0,1(i ? 0,1,...n) ;反之,?中每一数都 ? ? H 且 ? H , 。 (ii)说明应用 n ? 1个特别的砝码,在天平上可以量出 1 到 H 中的任意一个斤数。 证明: (i)当 xi ? ?1, 0,1(i ? 0,1,...n ) 时,?过模 2H ? 1 ? 3n?1 的绝对最小完全剩余系,也就是 ?表示 ? ? H , H ? 中的 2H ?1 个整数,事实上,当 xi ? ?1, 0,1 时,共有 3n?1 个值,且两两互不相 等,否则

3n xn ' ? 3n ?1 xn ?1' ? ...3x1' ? x0' ? 3n xn ? 3n ?1 xn ?1 ? ...3x1 ? x0
' ? 3n ( xn ' ? xn ) ? 3n ?1 ( xn ?1' ? xn ?1 ) ? ...3( x1' ? x1 ) ? x0 ? x0 ' ' ? 3 | x0 ? x0 ? x0 ? x0 .

此即

3n ?1 ( xn ' ? xn ) ? 3n ? 2 ( xn ?1' ? xn ?1 ) ? ...( x ' ? x) ? 0
' ? 3 | x1' ? x1 ? x1' ? x1 ? ... ? xn ? xn

又?的最大值是 3 ? 3
n

n ?1

3n ?1 ? 1 ? ...3 ? 1 ? ?H 3 ?1

最小值是 ?3n ? 3n?1 ? ... ? 3 ? 1 ? ? H 所以,结论成立。

23 / 77

《初等数论》习题解答(第三版)广东石油化工学院

(ii)特制 n ? 1 个砝码分别重 1, 3, 3 ,..., 3 斤,把要称的物体
2 n

?? ? d ? ? ?? ? d
i ?1 i i ?1

r

r

?a? ? 及取-1 ? i?

的砝码放在天平的右盘, xi 取 1 的砝码放在左盘,则从(i)的结论知,当 xi 取适当的值时, 可使 T ? 3n xn ? 3n ?1 xn ?1 ? ...3x ? x0 . 之值等于你所要称的物体的斤数 ? ? H ? 。 4、若 m1 , m2 ,..., mk 是 K 个两两互质的正整数,x1 , x2 ,...xk 分别过模 m1 , m2 ,..., mk 的完全剩余系, 则

x1 ? m1 x2 ? m1 , m2 x3 ? ... ? m1 , m2 ,..., mk xk ................. ?
通过模 m1 , m2 ,..., mk 的完全剩余系。 证明: (数学归纳法) (1) K ? 2 时, x1 , x2 分别过模 m1 , m2 的完全剩余系时,

x1 ? m1 x2 共有 m1m2 个值,且若 ? ? ? ? x1 ? m1 x2 ? x1 ? m1 x2 (mod m1m2 ) ? m1 ( x2 ? x2 ) ? x1 ? x1 (mod m1m2 )

? ? ? m1 x1 ? x1 ,且 x2 ? x2 ?

? x1 ? x1 (mod m2 ) m1

? ? ? x1 ? x1 , x2 ? x2 ,即 k ? 2 时结论成立;
(2)设当 x2 ,? , xk 分别过模 m2 ,?, mk 的完全剩余系时,

x2 ? m2 x3 ? ? ? m2 m3 ? mk ?1 xk 过模 m2 ? mk 的完全剩余系。
因为 (m1 , m2 ? mk ) ? 1 ,由本节定理 2 得,

m1 ( x2 ? m2 x3 ? ? ? m2 ? mk ?1 xk ) 亦过模 m2 ? mk 的完全剩余系。
当 x1 , x2 ,?, xk ?1 , xk 分别过模 m1 , m2 ,?, mk ?1 , mk 的完全剩余系时, 2 有 m1m2 ? mk 个值,且据归纳假设, 若 x1 ? m1 x2 ? ? ? m1 ? mk ?2 xk ?1 ? m1 ? mk ?1 xk

? ? ? ? ? x1 ? m1 x2 ? ? ? m1 ? mk ?2 xk ?1 ? m1 ? mk ?1 xk (mod m1 ? mk )
24 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? ? x1 ? x1 (mod m1 ) ; x2 ? m2 x3 ? ? ? m2 ? mk ?1 xk ? ? ? ? ? x2 ? m2 x3 ? ? m? km 1(xm o d m ? 2 ? k 2 ? ? ? ? x1 ? x1 (mod m1 ) , x2 ? x2 (mod m2 ) ,…, xk ? xk (mod mk ) ? ? ? ? x1 ? x1 , x2 ? x2 ,…, xk ? xk 。
所以 x1 ? m1 x2 ? ? ? m1m2 ? mk ?1 xk 过模 m1m2 ? mk 的完全剩余系。
k

m )

3.简化剩余系与欧拉函数 1.证明定理 2:若 a1 , a2 ,?, a? ( m) 是 ? (m) 与 m 互质的整数, 并且两 ? 对模 m 不同余,则 a1 , a2 ,? , a? ( m ) 是模 m 的一个简化剩余系。 证明:

? a1 , a2 ,?, a? ( m) 两 ? 对模 m 不同余,所以它们分别取自模 m 的不同剩余类,
又? a1 , a2 ,?, a? ( m) 恰是 ? (m) 个与 m 互质的整数,即它们恰取自与模 m 互质的全部剩余类。 2.若 m 是大于 1 的正整数, a 是整数, (a, m) ? 1 , ? 通过 m 的简化剩余系, 则
? ? ? m ? ? 2 ? (m) ,其中 ? ?

?a ? ? ?

1

表示展布在 ? 所通过的一切值上的和式。

?

证明:由定理 3 知, ? 通过 m 的简化剩余系:

a1 , a2 ,? , a? ( m ) ,其中 0< ai < m 且 (ai , m) ? 1 ,
而?

? ai ? ai 。 ? ? ( i ? 1, 2,?? (m) ) ?m? m

若 m >2,则 ? (m) 必是偶数,又由 (ai , m) ? 1 , 得 (m ? ai , m) ? 1,且易见 m ? ai ? ai , 故?

? ai ? ? m ? ai ? ai ? m ? ai ?1 ??? ?? m ?m? ? m ?

25 / 77

《初等数论》习题解答(第三版)广东石油化工学院

所以

? ? m ? ? ? m ? ? ? m ? ? .? ? ? ? ? ? ? ? ? ?

? a? ?

? a1 ? ? a2 ?

? a? ( m ) ? ? ? m ?

左边每一项 ?

? m ? ai ? ? a j ? ? ai ? ? ? ? ? (i ? j ) , ? 都存在另一项 ? ? m ? ?m? ?m?

使得 ?

1 ? ai ? ? a j ? ? ? ? ? ? 1 ,右边共有 ? (m) 对, 2 ?m? ? m ?

此即

? ? m ? ? 2 ? ( m) 。 ? ? ? ?? m ? ? 2 。 ? ? ?
展布在 a 的一切正整数上的和式。

? a? ?

1

特别地,当 m=2 时, ? (2) ? 1,

? a? ?

1

3. (i)证明 ? (1) ? ? ( p) ? ? ? ? ( p? ) ? p? ,p 质数。 (ii) 证明

?? (d ) ? a ,其中 ?
d a d a

证明: (i)因为 ? ( p k ) ? p k ? p k ?1 , (k ? 1, 2?, ? ) 所以 ? (1) ? ? ( p) ? ? ? ? ( p? ) = 1 ? ( p ? 1) ? ( p 2 ? p) ? ? ? ( p? ? p? ?1 ) = p? (ii)设 a ? p1?1 p2?2 ? pk ?k 是 a 的标准分解式, 则

? d ? (1 ? p ? ? ? p ? )(1 ? p
1

1

1

2

? ? ? p2?2 )?(1 ? pk ? ? ? pk ?k ) ,

d a

? ?? (d ) ? (1 ? ? ( p1 ) ? ? ? ? ( p1?1 ))?(1 ? ? ( pk ) ? ? ? ? ( pk ?k ))
d a

= p1?1 p2? 2 ? pk ? k =a 4.若 m1 , m2 ,?, mk 是 k 个两两互质的正整数,?1 , ? 2 ,? , ? k 分别通过模 m1 , m2 ,?, mk 的简化剩 余系,则

M1? 1? M ? ? ? ? M k?k 2 2
26 / 77

《初等数论》习题解答(第三版)广东石油化工学院

通过模 m1m2 ? mk ? m 的简化剩余系,其中 m ? mi M i , i ? 1, 2,?, k 。 证明: (数学归纳法) (1) 由定理 4 知 k=2 时,结论成立; (2) 设 k-1 时结论成立,即 m? ? m1 ? mk ?1 ? mi M i? (i ? 1,? , k ? 1) , ?1 , ?2 ,?, ? k ?1 分别过 模 m1 ,? , mk ?1 时,

? ? M 1??1 ? M 2?? 2 ? ? ? M k ?1?? k ?1
过 m? 模的简化剩余系。 显见 (m?, mk ) ? 1 ,则又由定理 4 知, mk? ? M k ?k 通过模 m?mk 的简化剩余系,注意到:

mk? ? (mk M 1? )?1 ? (mk M 2? )? 2 ? ? ? (mk M k ?1? )? k ?1

? M1?1 ? M 2?2 ? ? ? M k ?1? k ?1
所以, M1?1 ? M 2?2 ? ? ? M k? k 通过模 m 的简化剩余系。

? 4 .欧拉定理 ? 费马定理及其对循环小数的应用
1、如果今天是星期一,问从今天起再过 1010 天是星期几? 解:若 1010 ? 1 被 7 除的非负最小剩余是 r ,则这一天就是星期 r (当 r ? 0 时是星期日) .
10 10

? ?10? 7 ? ? 1 ,由费马定理得 106 ? 1
又?10 ? ?2

? mod 7 ? ,
10

? mod 7 ? ? 1010 ? ? ?2 ? ?K ?Z ?

? 45 ? 4

? mod 6 ?

?1010 ? 6 K ? 4
10

?1010 ? 1 ? 106 K ? 4 ? 1 ? 104 ? 1 ? 34 ? 1 ? 5
即这一天是星期五.
56 2、求 12371 ? 34

? mod 7 ?

?

?

28

被 111除的余数。

解:?111 ? 37 ? 3. 据欧拉定理,易知

?? ?111? ? ? ? 37 ? ? ? ? 3? ? 36 ? 2 ? 72 ,

? ? mod 37 ? ? 36 ? ? 12371 ? 1 ? mod111? 2?18 36 12371 ? ?12371? ? 1 ? mod 3? ? ? 1237136 ? 1
27 / 77

《初等数论》习题解答(第三版)广东石油化工学院

?1237156 ? 1237120
又?12371 ? 1112 ? 50

? mod111?
? ?12371 ? 50

(1)

? mod111?

故 ?123712 ? 502 ? ?53

? mod111? ??123714 ? 532 ? 34 ? mod111?

? 123718 ? 46


? mod111? ? 1237116 ? 7 ? mod111? ? mod111? .由(1)即得?1237156 ? 16 ? mod111?
28

1237120 ? 34 ? 7 ? 16

?1237156 ? 34 ? 50
由以上计算,知
28

? mod111? ? ?1237156 ? 34 ?
? mod111??

? 50 28

? mod111? .

5020 ? 16

508 ? 46

? mod111? .

? ?1237156 ? 34 ? ? 50 28 ? 16 ? 46 ? 70

? mod111? .

3 、 (i ) 证 明 下 列 事 实 但 不 许 用 定 理 1 推 论 : 若 p 是 质 数 , h1 , h2 ,? ha 是 整 数 , 则
p (h1 ? h 2 ? ? ha )p ? h 1 ? h p? ? ha 2 p

?

m o d ?。 p

(ii) 由 (i ) 证明定理1推论,然后再由定理1推论证明定理1。
证明

(i ) 对 a 应用数学归纳法:

?1? 当 a ? 2 时,按二项式展开即得
(h1 ? h2 ) p ? h1p ? h2p

? mod p ?

? 2 ? 设 a ? k 时,结论成立,即
(h1 ? h2 ? ? hk ) p ? h1p ? h2p ? ? hkp
当 a ? k ? 1 时,

? mod p ?

(h1 ? h2 ? ? hk ? hk ?1 ) p ? (h1 ? h2 ? ? hk ) p ? hkp?1 ? h1p ? h2p ? ? hkp ? hkp?1
结论成立。

? mod p ?

(ii) 在 (i ) 的结论中,令 h1 ? h2 ? ? ? ha ? 1 ,即得:
ap ? a
即定理1推论成立。
28 / 77

? mod p ?

《初等数论》习题解答(第三版)广东石油化工学院
? ? 进一步,设 m ? p1 1 ? ps s ,则

? ? m ? ? ? pi ? 1? pi?
i ?1

s

i ?1

固对任一整数 p ,若 ? a, p ? ? 1 ,则由上述已证性质得:

a p ?1 ? 1

? mod p ? 存在 k ? z ,使 a p ?1 ? 1 ? kp
p p

故 (a p ?1 ) p = ?1 ? kp ? ? 1 ? C1 kp ? ? ? ? kp ? ? 1 ? p 2l ( l ? z ) p

? ? a p ?1 ? ? 1? mod p 2 ?
p

依此类推可得 (a p ?1 ) p? ?1 ? 1 mod p? , 即 a 若

?

?

? p?

? ?

? 1? mod p? ? .
?

? a, m ? ? 1


i



? a, p ? ? 1, ? i ? 1, 2,? s ? .
?i
i

a

? pi?i

? ? ? 1 mod p? ? i

i

?

? a? ? m ? ? 1? mod pi? ? , ? i ? 1, 2,? s ? ? a? ? m ? ? 1? mod m ? ,定理成立。
4、证明:有理数

a , 0 ? a ? b, ? a, b ? ? 1 表成纯循环小数的充分与必要条件是有一正数 t 使得同 b

t 余式 10 ? 1? mod b ? 成立,并且使上式成立的最小正整数 t 就是循环节的长度。

证明: ? i ? 必要性,若结论成立,则由定理 2 知(b,10)=1,
t 令 t= ? ? b ? , 则据欧拉定理得 10 ? 1? mod b ? ;

a 2 充分性,若有正数 t,满足 10t ? 1? mod b ?
令 t 为使上式成立的最小正整数,且 10t = q1b ? 1

? 10t a ? ? aq1 ? b ? a ? qb ? a, ? q ? a1q ?
且 0 ? q ab 10t

a ? 1? ? 10t ?1 ? ? ? 10t ? 1 。 b ? b?

以下参照课本 51 页的证明可得:
. . a a = 0. a1 ? a t . 即 可表成循环小数,但循环节的长度就是 t。 b b

29 / 77

《初等数论》习题解答(第三版)广东石油化工学院

第四章

同余式

? 1 基本概念及一次同余式
例 解同余式 12 x ? 15 ? 0 ? mod 45 ? 解:?(12,45)= 3 15

?同余多项式有 3 个解
而原同余式为 4 x ? 5 ? 0 ? mod15 ?

4 x ? ? 5? m o d ? 5 1
4 ?4 x ? ?20 ? mod15 ?

1 5x ? x ? ? 2 ? m o d 1 5 0 ?
? x0 ? 10(mod15) 与 x0 ? ?5(mod 45) 也一样
所以原同余式的 3 个解是 x ? 10 ? 15t (t=0、1、2) 即 x1 ? 10(mod15) , x2 ? 25(mod15) , x3 ? 40(mod15) 1、 求下列各同余式的解

? i ? 256x ? ?

30 ? 179 ? mod 337 ? 2 ?5 ? ?

? ii ? 1215x ? 560 ? mod 2755?
? iii ? 1296x ? 1125 ? mod1935 ?

? i ? ?337 是素数,
先解同余式 256x ?

? ? 256,337 ? ? 1 ,原同余式有唯一解。

? 30 ? 1 ? mod 337 ? 2 ?5 ? ?

由辗转相除法,得 256 ?104 ? 337 ? ?79 ? ? 1

?上述同余式的解是 x ? 104 ? mod 337 ? ?原同余式的解是 x ? 104 ?179 ? 81? mod 337 ?

? ii ? ?(1215,2755)=5,故先解
30 / 77

《初等数论》习题解答(第三版)广东石油化工学院

243x ?

? 30 ? 112 ? mod 551? 2 ?5 ? ?

同 ? i ? 的方法的得其解是 x ? 200 ? mod 551?

?原同余式的解是 x ? 200, 751,1302,1853, 2404 ? mod 2755 ?

? iii ? ?(1296,1935)=9,故原同余式有 9 个解。
由 144x ?

? 30 ? 125 ? mod 215 ? 得 x ? 80 ? mod 215 ? 2 ?5 ? ?

?原同余式的解是 x ? 80 ? 215t ? mod1935? , t ? 0,1?8.
? x ? 4 y ? 29 ? 0(mod143) 的解。 ?2 x ? 9 y ? 84 ? 0(mod143)

2.求联立同余式 ?

解:据同余式的有关性质,

? x ? 4 y ? 29 ? 0(mod143) ? x ? 4 y ? 29(mod143) ?? ? ?2 x ? 9 y ? 84 ? 0(mod143) ?17 y ? ?1(mod143) ? x ? 4 y ? 29(mod143) ? x ? 4(mod143) 为所求的解。 ?? ?? ? y ? 42(mod143) ? y ? 42(mod143)
3.(i)设 m 是正整数, (a, m) ? 1 .证明
? ) 1 x ? b a( m ? ( m o d m )

是同余式 ax ? b(mod m) 的解 (ii)设 p 是质数, 0 ? a ? p ,证明

x ? b(?1)a ?1

( p ? 1)? ( p ? a ? 1) (mod p) a!

是同余式 ax ? b(mod p) 的解. 证明: (i) ? (a, m) ? 1 , ? ax ? b(mod m) 有唯一解. 而据欧拉定理,得 a? ( m) ? 1(mod m) ,
31 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? ax ? b( m o m ) d
) ? a? ( m ? 1 ax ? ba? ? m( ? ) 1

(mom ) d

即 x ? ba? ( m)?1 (mod m) 是 ax ? b(mod m) 的解. (ii) ? 0 ? a ? p ? (a, p) ? 1 即 ax ? b(mod p) 有唯一解 又 ?a 个连续整数之积必被 a !所整除, 故可令 ab(?1) a ?1

( p ? 1)? ( p ? a ? 1) ?k a!

则 b(?1)a ?1 ( p ? 1)?( p ? a ? 1) ? k (a ? 1)!

? b(?1)a ?1 ( p ? 1)?( p ? a ? 1) ? b(?1) 2( a ?1) (a ? 1)!(mod p)
即 b(?1)2( a ?1) (a ? 1)! ? k (a ? 1)!(mod p)

? k ? b(mod p)
即 x ? b(?1) a ?1

( p ? 1)? ( p ? a ? 1) (mod p) a!

是 ax ? b(mod p) 的解.

设 p 是 素 数 , 0 < a < p, 证 明 :

x ? b(?1) a ?1

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

是 同 余 方 程 ax ? b (mod p)的 解 。

( p ? 1)( p ? 2) ??? ( p ? a ? 1) 是 整 数 , 又 由 ( a , p) = 1 知 方 程 a x ? a! ( p ? 1)( p ? 2) ??? ( p ? a ? 1) b ( m o d p) 解 唯 一 ,故 只 须 将 x ? b(?1) a ?1 ( m o d p ) 代 入 ax ? b a!
解 : 首 先 易 知 b(?1)a ?1 (mod p)验 证 它 是 同 余 方 程 的 解 即 可 。 4.设 m 是正整数, ? 是实数, 1 ? ? ? m,(a, m) ? 1 ,证明同余式

ax ? y (mod m), 0 ? x ? ? , 0 ? y ?
有解.

m

?
32 / 77

《初等数论》习题解答(第三版)广东石油化工学院

证明: 因 (a, m) ? 1. 故同余式 ax ? 1(mod m) 必有解 x0 , (i) (ii) 若 0 ? x0 ? ? ,则结论成立; 若 ? ? x0 ,令 m ? q1 x0 ? x1 , 0 ? x1 ? x0 , 则 ax1 ? ?(ax0 )q1 ? ?q1 (mod m) 又若

x1 ? ? , 则由 q1 ?

m ? x1 m ? ,结论成立. x0 ?

若 ? ? x1 令 x0 ? q2 x1 ? x2 则 ax2 ? 1 ? q1q2 (mod m).

0 ? x2 ? x1

又若 x2 ? ? , 则由 m ? q1 x0 ? x1 ? q1 (q2 x1 ? x2 ) ? x1 即 m ? (1 ? q1q2 ) x1 ? q1 x2, 故 1 ? q1q2 ? 结论成立。 若 ? ? x2 , 又令 x1 ? q3 x2 ? x3 , 0 ? x3 ? x2 . 则 ax3 ? ?(q1 ? q2 ? q1q2 q3 )(mod m) 重复上述讨论:即若

m ? q1 x2 m ? x1 ?

x3 ? ? , 则结论成立,

若 ? ? x3 . 又令 x2 ? q4 x3 ? x4 , 0 ? x4 ? x3 ``````

? x ? 2(mod 3) ? 例解同余方程组 ? x ? 3(mod 5) ? x ? 2(mod 7) ?
解:?模3,5,7两两 互质,故原方程组对模 m ? 3 ? 5 ? 7 有唯一解

33 / 77

《初等数论》习题解答(第三版)广东石油化工学院

35M 1? ? 1(mod 3)得M 1? ? 2(mod 3) ? 21M 2 ? 1(mod 5) ? M1M1? ? 1(mod 3) 即 M 2 ? 1(mod 5) ? 15M 3 ? 1(mod 7) ? M 3 ? 1(mod 7)
根据孙子定理方程组的解是

x ? 2 ? 35 ? 2 ? 1? 21? 3 ? 1?115 ? 2 ? 233 ? 23(mod105)
注意到

x0 ? x1 ? x2 ? , ?
故有限步后,必有 axn ? y(mod m)

其中 0 ? xn ? ? , y ?

m

?

, 即结论成立。

? 2. 孙子定理
试解下列各题: (i) 十一数余三,七二数余二,十三数余一,问本数。 (ii) 二数余一,五数余二,七数余三,九数余四,问本数。 (杨辉:续古摘奇算法(1275)。 )

? x ? 3(mod11) ? 解: (i)依题意得 ? x ? 2(mod 72) ? x ? 1(mod13) ?
则据孙子定理,上述方程组有唯一解 (mod11? 72 ?13)

72 ? 73M 1? ? 1(mod11)得M 1? ? 1; ? ? 由 11 ?13M 2 ? 1(mod 72)得M 2 ? ?1; ? ? 11 ? 72 M 3 ? 1(mod13)得M 3 ? ?1;
故原方程组的解是 x ? 3 ? 936 ? 2 ? (?1) ?143 ? 1? (?1) ? 792 ? 1730(mod10296).

? x ? 1(mod 2) ? x ? 2(mod 5) ? (ii)依题意得 ? ? x ? 3(mod 7) ? x ? 4(mod 9) ?
? x ? 1? 315 ? 2 ?126 ? 3? 6 ? 90 ? 4 ? 4 ? 70 ? 3307 ? 157(mod 630).
2、 (i)设 m1 , m2 , m3 是三个正整数,证明:
34 / 77

《初等数论》习题解答(第三版)广东石油化工学院

?? (m1 , m3 ), (m2 , m3 ) ? ? ?? m1 , m2 ? , m3 ? ?

?.

(ii)设 d ? (m1 , m2 ). 证明:同余式组

x ? b( m o dm ) x ? , 1 1

2

b ( m om d 2

) (1)

有解的充分与必要条件是 d b1 ? b2 . 在有解的情况下,适合(1)的一切整数可由下式求出:

x ? x1,2 ? mod ? m1 , m2 ??
其中 x1,2 是适合 ?1? 的一个整数。

? iii ? 应用 ? i ? , ? ii ? 证明同余式组 x ? bi ? mod mi ? , i ? 1, 2,?, k

? 2?

有解的充分与必要条件是 (mi , m j ) | (bi , b j ), i, j ? 1, 2,?, k ,并且有解的情况下,适合 (2) 的一切 整数可由下式求出:

x ? x1,2,?,k (mod ? m1 , m2 ,? mk ?)
其中 x1,2,?,k 是适合 (2) 的一个整数。 证明: ? i ? ? (m1 , m3 ), (m2 , m3 ) ? ?

(m1 , m3 )(m2 , m3 ) (m , m )(m2 , m3 ) ? 1 3 ((m1 , m3 ), (m2 , m3 )) (m1 , m2 , m3 )
2 3

(? m1 , m2 ? , m3 ) ? (

(m m , (m ,1m )2 ) 3 (m m 1, m2m ,1m m ) m m1m2 3 , m3 ) ? 1 2 ? (m1 , m2 ) (m1 , m2 ) (m1 , m2 )

(m1 , m2 , m3 ) ( 1 m2 , m1 m3 , m2 m3) m ? ( ( 1 ,m2 ,m3 ) 1 m2 , ( 1 ,m2 ,m3 ) 1 m3 , ( 1 ,m2 ,m3 ) 2 m3 ) m m m m m m
2 2 , , )( ( ? ? (m12 m2 , m1 m2, m1 m,3 m1 2m3 2m2 m3 m2 , 3 m1 m2 m3 , m1 )m2 2 m

m1)m3 m2)m3 (

? (m12 , m1 m3 , m1 m2, m2 m) ( m2, m3) 3
2 2 ? (m12 m2 , m1 m2, m2 m,3 m2 2m3 2m1 m33 ,m1 1 m )3 , , 2 mm 2

m m ? (m1 , m2 , m3 ) ( 1 m2 , m1 m3 , m2 ? 3)


( m1 , m2 ) (m1 , m3 ) ( 2 ,m3 ) m

(m1 , m3 )(m2 , m3 ) (m1m2 , m1m3 , m2 m3 ) ? (m1 , m2 , m3 ) (m1 , m2 )

( , ? ( m ? ? (m1 , m3 ) , m2 m3 ?) ? m1 ?, 2

m3 ) . ,
35 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? ii ? 设 (1) 有解 c ,即 c ? b1 (mod m1 ), c ? b2 (mod m2 )
故此得 b1 ? b2 (mod(m1 , m2 )) ,必要性成立; 反之,设 d | b1 ? b2 即 b1 ? b2 (mod d ) 则由§ 定理,知方程 m1 y ? b2 ? b1 (mod m2 ) 必有解, 1 设其解为 y ? y0 (mod m2 ) ,即 m1 y0 ? b2 ? b1 (mod m2 ) 令 x1,2 ? b1 ? m1 y0 则易见:

x1,2 ? b1 (mod m1 ) 且 x1,2 ? b2 (mod m2 )
即 (1) 有解 x1,2 ,充分性得证。 进一步,若 (1) 有解 x, y ,则

x ? y (mod m1 ), x ? y (mod m2 )
即 x ? y 是 m1 , m2 的公倍数,当然也是 ? m1 , m2 ? 的倍数,

? x ? y (mod ? m1 , m2 ?)
故若 x1,2 是 (1) 的一个解,则 (1) 的任一解 x 必满足

x ? x1,2 (mod ? m1 , m2 ?) 。
(iii) 若同余式组 x ? bi (mod mi ), i ? 1, 2,?, k 有解,
则?

? x ? bi (mod mi ) ? ? x ? b j (mod m j ) ?

也有解。从而由 (ii) 知必有

(mi , m j ) | (bi , b j ), i ? 1, 2,?, k ,必要性成立。
下证充分性。首先,推 (i ) ,用归纳法易证:

?(m1 , mk ), (m2 , mk ),?, (mk ?1 , mk )? ? (? m1, m2 ,?, mk ?1 ? , mk )
又由 (ii) 知 k ? 2 时,充分性也成立;

36 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? x ? b1 (mod m1 ) ? 现设同余式组 ?? ? x ? b (mod m ) k ?1 k ?1 ?
即 b ? bi (mod mi ),1 ? i ? k ? 1。

有解 x ? b(mod ? m1 ,? , mk ?1 ?) ,

设 bi ? b ? li mi ,1 ? i ? k ? 1;又由条件知 (mi , mk ) | (bi ? bk ) , 而 bi ? bk ? (b ? bk ) ? li mi ,从而 (mi , mk ) | bi ? bk ,1 ? i ? k ? 1 , 所以 x 2 ? 41(mod16) , 即 (? m1 , m2 ,? , mk ?1 ? , mk ) ? b ? bk , 又由 (ii) ,则同余式组 ?

? x ? b(mod ? m1 ,? , mk ?1 ?) ? , ? x ? bk (mod mk ) ?
(※)

必有解 x ? c(mod ? m1 ,? , mk ?1 , mk ?)

显然 c ? bi (mod mi ),1 ? i ? k ,即(※)就是同余式组 (2) 的解,据归纳性原理,结论成立。后 一结论由上述过程亦成立。 § 3 高次同余式的解数及解法

1、 解同余式 6 x3 ? 27 x 2 ? 17 x ? 20 ? 0(mod 30) 。

? x 2 ? x ? 0(mod 2) ? ? ? ? ? ? ? ? ? ?(1) ? 解:原同余式等价于 ?2 x ? 2 ? 0(mod 3) ? ? ? ? ? ? ? ? ? ?(2) ? x3 ? 2 x 2 ? 2 x ? 0(mod 5) ? ? ? ? ? ?(3) ?

(1)有解x ? 0,1(mod 2) (2)有解x ? 2(mod 3) (3)有解x ? 0,1, 2(mod 5)
? x ? b1 (mod 2) ?? b1 ? 0,1 ? 联立 ? x ? b2 (mod 3)?? b2 ? 2 ? x ? b3(mod 5)?? b ? 0,1, 2 3 ?
据孙子定理,可得 x ? 15b1 ? 10b2 ? 6b3 (mod 30)
37 / 77

《初等数论》习题解答(第三版)广东石油化工学院

故原同余式共有 6 个解是:

x1 ? 20, x2 ? 5, x3 ? 26, x4 ? 11, x5 ? 2, x6 ? 17, (mod 30)
2、 解同余式 31x 4 ? 57 x3 ? 96 x ? 191 ? 0(mod 225) 解:? 225 ? 32 ? 52

? 4 x 4 ? 3 x 3 ? 6 x ? 2 ? 0( mod 32 ) ? 故原同余式等价于 ? 4 3 2 ?6 x ? 7 x ? 4 x ? 9 ? 0(mod 5 ) ?
1) 先解 4 x 4 ? 3x3 ? 6 x ? 2 ? 0(mod 3) 即 x 4 ? 1 ? 0(mod 3) 得 x ? ?1(mod 3)

? f ?( x) ? 16 x 3 ? 9 x 2 ? 6 ? f ?(1) ? 31, 3 ? 31 f ?(?1) ? ?1, 3 ? (?1)

f (1) ? ?5(mod 3) ? t1 ? 1(mod 3). 3 ? x1 ? 1 ? 3t1 ? 4(mod 32 ); 由f ?(1)t1 ? ? 又由f ?(?1)t2 ? ?5(mod 3) ? t2 ? 2(mod 3) ? x2 ? ?1 ? 3t2 ? 5(mod 32 ); 即第一式有两个解x1 ? 4, x2 ? 5
②再解 g ( x) ? 6 x 4 ? 7 x3 ? 4 x ? 9 ? 0 即 设

(mod 32 ).
(mod 5)

x 4 ? 2 x3 ? x ? 1 ? 0

(mod 5)

x ?1 ,

2

(mod 5) .
g ?(1) ? 41. g ?(2) ? 272,

g ?( x) ? 24 x3 ? 21x 2 ? 4.
而 5 ? 41

5 ? 272
(mod 5) (mod 5)
(mod 52 ).



41t1 ? 0(mod 5) ? t1 ? 0 272t2 ? ?27(mod 5) ? t2 ? 4
?3

? 第二式有两个解x3 ? 1, ? x ? b1 联立 ? ? x ? b2 (mod 9) (mod 25)

b1 ? 4 , 5 b2 ? 1, ?3
38 / 77

《初等数论》习题解答(第三版)广东石油化工学院

由孙子定理设 x ? 100b1 ? 126b2 即原四条式有 4 个解是 x ? 76,

(mod 225)

22, 176, 122

(mod 225).

§ 4.质数模的同余式 补充例子: 1. 解 同 余 方 程 : (ⅰ) (ⅱ) 3 x 1 1 ? 2 x 8 ? 5 x 4 ? 1 ? 0 ( m od 7 ) ; 4 x 2 0 ? 3 x 1 2 ? 2x 7 ? 3 x ? 2 ? 0 ( m o d 5 ) 。 原 同 余 方 程 等 价 于 3 x 5 ? 5 x 4 ? 2 x 2 ? 1 ? 0 ( m o d 7) , 用 x = 0 , ? 1 , (ⅱ) 原 同 余 方 程 等 价 于 2 x 4 ? 2 x 3 ? 3 x ? 2 ? 0 ( m od

解 : (ⅰ)

?2, 3 代 入 知 后 者 无 解 ; ?

5 ) , 将 x = 0, ? 1, ? 2 代 入 , 知 后 者 有 解 x ? ? 1 ( m o d 5) 。 2. 判 定 (ⅰ) (ⅱ) 2 x 3 ? x 2 ? 3 x ? 1 ? 0 ( m o d 5) 是 否 有 三 个 解 ; x 6 ? 2 x 5 ? 4 x 2 ? 3 ? 0 ( m od 5 ) 是 否 有 六 个 解 ? 2 x 3 ? x 2 ? 3 x ? 1 ? 0 ( m o d 5 ) 等 价 于 x 3 ? 3x 2 ? 4 x ? 3 ? 0 ( m o d 5 ) ,

解 : (ⅰ)

又 x 5 ? x = ( x 3 ? 3x 2 ? 4 x ? 3) ( x 2 ? 3 x ? 5 ) + ( 6 x 2 ? 1 2x ? 1 5) , 其 中 r ( x ) = 6 x 2 ? 12x ? 15 的 系 数 不 都 是 5 的 倍 数 ,故 原 方 程 没 有 三 个 解 ; 模 5 的同余方程,故原方程不可能有六个解。 (ⅱ) 因为这是对

定理 5 若 p 是素数,n?p ? 1,p ? a 则 | x n ? a (mod p) 有解的充要条件是
p ?1 n

(14)

a
若有解,则解数为 n。 证明

?1 (mod p)。

(15)

必要性 若方程(14)有解 x0,则 p ? x0,由 Fermat 定理,得到 |
39 / 77

《初等数论》习题解答(第三版)广东石油化工学院

a
充分性 若式(15)成立,则

p ?1 n

n ? ( x0 )

p ?1 n

= x0p ? 1 ?1 (mod p)。
p ?1 n p ?1 n p ?1 n

x p ?1 ? x ? x (( x n )

?a

?a

? 1)

? ( x n ? a ) P ( x) ? x(a

p ?1 n

? 1) ,

其中 P(x)是关于 x 的整系数多项式。由定理 4 可知同余方程(14)有 n 个解。证毕。

1、 设 n ︱ p ? 1 , n ? 1 , (a, p) ? 1 .证明同余式

xn ? a
有解的充分必要条件是 a

( m o dp )
p ?1 n

?1

(mod p) ,并且在有解的情况下就有 n 个解。

证明: ?)若同余式有解,令其解为x ? x0 (mod p), 设 p ? 1 ? kn.

? (a, p) ? 1,? ( x0 , p) ? 1
(mod p)

则 x0 p ?1 ? x0 kn ? 1 但 x0 p ?1 ? a

(mod p)

?a

p ?1 n

? x0 p ?1 ? 1

(mod p);

?)a

p ?1 n

?1

(mod p)
(mod p) 可得 x p ?1 ? a
p ?1 n

则由 x n ? a

?1

(mod p) 。

它有 p ? 1 个解。

又? n ︱ p ? 1
令 g ( x) ? ? x

? ?

( p ?1) ? n

? ax ( p ?1) ? 2 n ? a

p ?1 ?2 n

xn ? a

p ?1 ?1 n

? ? ?

则 x p ?1 ? ( x n ? a) g ( x) ? 0

(mod p)

? g ( x) ? 0

(mod p)
40 / 77

《初等数论》习题解答(第三版)广东石油化工学院

无 多 于 ( p ? 1?) 个 解 , 而 x p ?1 ? 1 ? 0 n

( m o d 恰 )有 p ? 1 个 解 , p

x p ?1 ? a 0 ?

( m o 必有 n 个解。 p d )

2.设 n 是整数, (a,m)=1,且已知同余式 x n ? a(mod m) 有一解 x ? x0 (mod m) ,证明这个同余式的一切解可以 表成 x ? yx0 (mod m) 其中 y 是同余式 y n ? 1(mod m) 的解。

证明:设 x ? x0 , x ? x1 (mod m) 均是 x n ? a(mod m) 的解, 则 x1n ? x0 n ? a(mod m) ,

?(a,m)=1 , ? ( x0 ,m)= ( x1 ,m) = 1
则由第三章定理 3.3 知,必存在 y,使

yx0 ? x1 (mod m) ,

? y n x0 n ? x1n ? x0 n (mod m) .
故原同余式的任一解可表示为 x ? yx0 (mod m) 而 y 满足 y n ? 1(mod m) 3 . 设 ( a , m) = 1 , k 与 m 是 正 整 数 , 又 设 x 0 k ? a ( m o d m) , 证 明 同 余 方 程 x k ? a( m o d m ) 的 一 切 解 x 都 可 以 表 示 成 x ? yx0 (mod m), 中 y 满 足 同 余 方 程 yk ? 1 (mod m)。 其 解 : 设 x 1 是 x k ? a ( mo d m ) 的 任 意 一 个 解 , 则 一 次 同 余 方 程 y x 0 ? x 1 ( m o d m ) 有 解 y , 再 由 y k a ? y k x 0 k ? ( y x 0 ) k ? x 1 k ? a ( mo d m ) 得 y k ? 1 ( m o d m ) , 即 x 1 可 以 表 示 成 x ? yx 0 ( m o d m) , 其 中 y 满 足 同 余 方 程 y k ? 1 ( m o d m ) ; 反 之 , 易 知 如 此 形 式 的 x 是 x k ? a( m od m ) 的 解 。

41 / 77

《初等数论》习题解答(第三版)广东石油化工学院

第五章 二次同余式与平方剩余 § 一般二次同余式 1 1、 在同余式 y 2 ? A ? 0(mod p? ) 中,若 p? | A ,试求出它的一切解来。 解:若 p? | A ,则 A ? 0(mod p? ) ,上同余式即为

y 2 ? 0(mod p? )
从而 p | y ,即有 p
?
2

?? ? ?2? ? ?

| y。
?? ?

? ? ?? ? 易见,当 ? ? 2 ? 为偶数时, ? ? ? ? ,则 p ? 2 ? ? p ? ,上同余式有解: ?2?

x ? 0, p ? , 2 p ? ,?, ( p ? ? 1) p ? (mod p? ) ,共有 n ? 2m ? 1 ? p 个解
当 ? ? 2? ? 1 为奇数时, p ? 2 ? ? p ? ,上同余式有解:
?? ? ? ?

x ? 0, p ? ?1 , 2 p ? ?1 ,?, ( p ? ? 1) p ? ?1 (mod p? ) ,共有 n ? 2m ? 1 ? p 个解。
2 、 证 明 : 同 余 式 ab ax 2 ? bx ? c ? 0(mod m), (2a, m) ? 1

(1) 有 解 的 充 分 必 要 条 件 是

x 2 ? q(mod m), q ? b2 ? 4ac
证明:因 (2a, m) ? 1,故 a 用 4a 乘 (1) 后再配方,即得

有 ( 2 ) 解,并且前一同余式的一切解可由后一同余式的解导出。

(2ax ? b)2 ? q ? 0(mod m), q ? b 2 ? 4ac
仍记 2ax ? b 为 x ,即有

x 2 ? q(mod m)
由以上讨论即知若 x ? x0 (mod m) 为 (1) 的解, 则 x ? 2ax0 ? b(mod m) 为 (2) 的解,必要性得证。 反之,若 (2) 有一解 x ? x0 (mod m) ,即有:
2 x0 ? 8 ? 0(mod m), q ? b 2 ? 4ac

42 / 77

《初等数论》习题解答(第三版)广东石油化工学院

由于 (2a, m) ? 1,故 2ax ? b ? x0 (mod m) 有解 x ? x1 (mod m) 即有: (2ax1 ? b)2 ? (b2 ? 4ac) ? 0(mod m) 即有: 4a(ax12 ? bx1 ? c) ? 0(mod m) 由 a ,即有: ax12 ? bx1 ? c ? 0(mod m) 即 x ? x1 (mod m) 为 (1) 的解,充分性得证。 由充分性的讨论即知 (1) 的解可由 (2) 的解导出。

§ 2

单质数的平方剩余与平方非剩余 1、 求出模

? ? ( d ) 的平方剩余与平方非剩余。
d a

m

解: p ? 37,

p ?1 ? 18 ,由书中定理 2 知,模 p ? 37 的简化剩余系中 18 个平方剩余分别与 2

序列 12 , 22 ,?,182 例 2.试判断下述同余方程是否是有解。 (1) ? 2 ? 27(mod 37) (2) ? 2 ? 2(mod 37) (3) ? 2 ? 3(mod17) 中之一数同余,而

12 ? 1 , 22 ? 4, 32 ? 9, 42 ? 16, 52 ? 25, 62 ? 36, 7 2 ? 12, 82 ? 27, 92 ? 7,
2 1 0 ? 2 6 112 ? 10, 122 ? 33, 132 ? 21, 142 ? 11, 152 ? 3, 162 ? 34, 172 ? 30, ,

2 18 ? 28.

故模 37 的平方剩余为: 1,3,4,7,9,10,11,12,16,21,25,26,27,30,33,34,36 而其它的 18 个数为模 37 的平方非剩余: 2,5,6,8,13,14,15,17,18,19,20,22,23,24,29,31,32,35 2. (i ) 应用前几章的结果证明:模 p 的简化剩余系中一定有平方剩余及平方非剩余存在,

43 / 77

《初等数论》习题解答(第三版)广东石油化工学院

(ii) 证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。 (iii) 应用 (i ) 、 (ii) 证明:模 p 的简化剩余系中平方剩余与平方非剩余的个数各为

p ?1 。 2

证明: (i ) 因为 12 ? 1(mod p), 1 为模 p 的简化剩余系中的平方剩余。若模 p 的简化剩余系中均 为平方剩余,考虑模 p 的绝对最小简化剩余系: ? 它们的平方为模 p 下的

p ?1 个数: 2 p (? 1 2 ,? 2 ) , ? . . (2 ) ( 2 . ) 2

p ?1 p ?1 ,..., ?1,1,..., 2 2

由假设模 p 的简化剩余系中任一个数与上

p ?1 个数同余,而模 p 的简化剩余系中有 p 个数, 2
p ?1 2

故必有两个互相同余,矛盾。从而必有平方非剩余存在。

(ii)


p ?1 2

a, b















a

? 1(mod p),

b

p ?1 2

? 1(mod p)



(ab)

? ?1(mod p), ( p ? 1) ? r ? r ?
p ?1 2

p ?1 , 从而 ab 也为平方剩余。若 a 为平方剩余,b 为平方 2

非剩余,则 a 故 (ab)
p ?1 2

? 1(mod p), b

p ?1 2

? ?1(mod p)

? ?1(mod p), 从而 ab 为平方非剩余。

(iii) 设 a1 ,..., ar 为模 p 的简化剩余系中的平方剩余; ar ?1 ,..., a p ?1 为模 p 的简化剩余系中的平方
非剩余。由 (ii) 知, ar ?1a1 ,..., ar ?1ar 为平方非剩余,显然互不同余。故 r ? ( p ? 1) ? r , 反之,由

ar ?12 , ar ?1ar ? 2 ,..., ar ?1a p ?1 为平方剩余知 ( p ? 1) ? r ? r , 故 r ?
3.证明:同余式 x 2 ? a mod p? , ? a, p ? ? 1 的解是

p ?1 ,得证。 2

?

?

? x ? ? p Q? m o d ?p? ,其中

? 2 ? a ? ? ? 2? a? p?
?

?

2

? 2? a? ? ? ,Q ?
?

? 2

?a

?

2 a

22 ? a ? m o dp? Q Q , ??

?1

? m op d ?

2 证明:若 x 2 ? a mod p? 有解,则 x ? a ? mod p ? 有解,

?

?

44 / 77

《初等数论》习题解答(第三版)广东石油化工学院

设其解是: x ? 2 ? mod p ? ,即有:

22 ? a ? m o d ? , p
令 22 ? a ? kp ? 2 2 ? a 而 2? a

?

?

?

? k ? p? ? 0 ? mod p? ?

?

?

?

1 2 ? 2? ? C? 2? ?1 a ? C? 2? ?2

? a?

2

???

? a?

?

? p? Q a

, p, Q 为整数

?

2? a

?

?

? p ?Q a

由此两式即得:

?2 ? a ? ? ?2 ? a ? p?
?

?

?2 ? a ? ? ?2 ? a ? Q?
?

2

?

2 a

两式相乘得:

?2

2

? a ? ? p 2 ? aQ 2 ? p 2 ? aQ 2 ? 0 ? mod p? ?
?

? p 2 ? aQ 2 ? mod p? ?
取 Q? 使得: QQ? ? 1 mod p?
2 ? 则 p ? Q? ? ? a mod p 2

?

?
故其解为 x ? ? pQ? mod p?

?

?

?

?

2 4.证明同余式 x ? 1 ? 0 ? mod p ? , p ? 4m ? 1 的解是

x ? ? ?2 ? 2 ?? m o d 1 ? m p ?
证明:首先我们证明对任意 n : p ? n 有下式:

? n ? 1? !?

p ? n ! ? ?1 ? ? ? ?
n

mo? d p

因为 ? ?1? k ? p ? k ? mod p ? ,于是

? n ? 1? ! ?? ?1 ? ?
n ?1

p ??1 ? p ?n ?? ? ?1

m o?d p

因此由威尔生定理得:
45 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? n ? 1?!? p ? n ?! ? ? ?1? ? p ? 1?! ? ? ?1? ? ?1?
n ?1 n ?1

? ? ?1n ? ? mod p ?
其次由 p ? 4m ? 1,可令 n ? 2m ? 1 ? p ,代入上式 即有

? 2m ! ?

2

? ? 1 m opd ? ?

故原同余式的解为 x ? ? ? 2m ? !? mod p ? § 勒让得符号 3 1.用本节方法判断下列同余式是否有解

?i ? x2 ? 4 2 9 m o d 5 6 3 ? ? ? ii ? x 2 ? 6 8 0 m o d 7 6 9 ? ? 2 ? iii ? x ? 5 0 3 m o d 1 ?0 1 3 ?
解: ? i ? ?

其中 503,563,769,1013 都是质数

? 429 ? ? ? 1 ,有解。 ? 563 ? 680 ? ? ? 1 ,有解。 ? 769 ?

? ii ? ? ?

? iii ? ? ?

503 ? ? ? 1,有解。 ? 1013 ?

2、求出以 ?2 为平方剩余的质数的一般表达式;以 ?2 为平方非剩余的质数的一般表达式。
p ?1 p ?1 ? ?2 ? ? ?1 ?? 2 ? ? ? ? ?? ? ? ? ?1? 2 8 解: ? ? ? p ? ? p ?? p ?
2

?2 为模 p 平方剩余时,必有

p ?1 p2 ?1 ? ? 2n 2 8

?i ? ? ii ?

p ? 4k ? 1 ,必有 p ? 8k ? ? 1 ,故 p ? 8m ? 1 p ? 4k ? 3 ,必有 p ? 8k ? ? 3 ,故 p ? 8m ? 3

?2 为模 p 平方非剩余时,必有

p ?1 p2 ?1 ? ? 2n ? 1 2 8

?i ?

p ? 4k ? 1 ,必有 p ? 8k ? ? 3 ,故 p ? 8m ? 5
46 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? ii ?

p ? 4k ? 3 ,必有 p ? 8k ? ? 1 ,故 p ? 8m ? 7

3、设 n 是正整数, 4n ? 3 及 8n ? 7 都是质数,说明

24 n?3 ? 1(mod8n ? 7)
由此证明: 23 | 211 ? 1, 47 | 223 ? 1,503 | 2251 ? 1 。 证明:当 p ? 8n ? 7 时,由本节定理 1 的推论知 2 为平方剩余,应用欧拉判别条件即有

2

p ?1 2

? 1(mod p)

由 p ? 8n ? 7 ,即得出 24 n ?3 ? 1(mod8n ? 7) 而 23 ? 8 ? 2 ? 7, 47 ? 8 ? 5 ? 7,503 ? 8 ? 62 ? 7 都是形如 8n ? 7 的素数,并且

11 ?

23 ? 1 47 ? 1 503 ? 1 ,所以 , 23 ? , 251 ? 2 2 2

23 | 211 ? 1, 47 | 223 ? 1,503 | 2251 ? 1 。
§ 前节定理的证明 4 1、 求以 ?3 为平方剩余的质数的一般表达式,什么质数以 ?3 为平方非剩余? 解:由互反律
p ?1 2

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

因此 ? ?1?

?3? ? p? , ? ? 当它们同为 1或同时为 ?1 时, ? ? ? 1 , ?3? ? p? ?3? ? ? ?1 ? p?
p?1 2

一为 1,一为 ?1 时, ?

p ?1 显然,当 为偶数,而 p ? 1(mod 4) 时, (?1) 2 p ?1 当 是奇数,即 p ? ?1(mod 4) 时, (?1) 2
p?1 2

? 1,

? ?1 。

再因为 p 是奇质数,关于模 3 我们有 p ? 1 或 p ? ?1 , 当 p ? 1(mod 3) 时, ?

? p ? ?1? ? ? ? ? ?1 ? 3 ? ? 3?
47 / 77

《初等数论》习题解答(第三版)广东石油化工学院

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

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

这样 3 为平方剩余时, p 为下方程组的解

? p ? 1(mod 3) ? p ? ?1(mod 3) 或? ? ? p ? 1(mod 4) ? p ? ?1(mod 4)
由孙子定理,即可知 p ? 1 或 ?1 (mod12) ,立即 当 p ? 12n ? 1 时, 3 为平方剩余。

3 为平方非剩余时, p 为下方程组的解
? p ? ?1(mod 3) ? p ? 1(mod 3) 或? ? ? p ? ?1(mod 4) ? p ? 1(mod 4)
由孙子定理,即可知 p ? 5 或 ?5 (mod12) ,立即 当 p ? 12n ? 5 时, 3 为平方非剩余。 因为 (
p ?1 ?3 ?1 3 3 ) ? ( )( ) ? (?1) 2 ( ) p p p p



3 3 p ?1 p ?1 为偶数, ( ) ? 1 ,或 为奇数, ( ) ? ?1 时,即 p p 2 2

p ? 12n ? 1 或 12n ? 5 时, ?3 为平方剩余,
类似 p ? 12n ? 1 或 12n ? 5 , ?3 为平方非剩余。 2、求以 3 为最小平方非剩余的质数的一般表达式。 解:由上题知以 3 为平方非剩余的质数 p 满足:

p ? ?5(mod12)

1 又由 3 为模 p 的最小平方非剩余,故 ( )=
从而 p ? ?1(mod8) (§ T1 推证) 3 h
48 / 77

2 p

《初等数论》习题解答(第三版)广东石油化工学院

满足 p ? ?5(mod12) 的素数 p 形如 24m ? 5, 24m ? 7, 24m ? 17, 24m ? 19 , 其中只有 24m ? 7, 24m ? 17 满足 p ? ?1(mod8) 故 p ? 24m ? 7 或 24m ? 17 时, 3 为它的最小平方非剩余。 § 雅可比符号 5 1、 判断§ 习题 1 所列各同余式是否有解。 3 略 2、 求出下列同余式的解数:

(i ) x 2 ? 3766(mod 5987) , (ii) x 2 ? 3149(mod 5987) 其中 5987 是一个质数。
解: (i ) (

3766 2 ?1883 2 1883 )?( )?( )( ) 5987 5987 5987 5987 2 5987 ? 748 ? 8 ? 3 ,故 ( ) ? ?1 5987

(

1883?1 5987 ?1 ? 1883 5987 5987 338 2 )(?1) 2 ( ) ? ?( ) ? ?( ) 5987 1883 1883 1883

2 169 169 1883 24 6 ? ?( )( )?( )?( )?( )?( ) 1883 1883 1883 169 169 169 2 3 3 169 4 ?( )( )?( )?( ) ? ( ) ?1 169 169 169 3 3
故?

? 3766 ? ? ? ?1 ,即 ? i ? 的解数为 0. ? 5987 ?

? ii ?
3.

? 3149 ? ? ? ? 1 ,故解数为 2. ? 5987 ?

? i ? 在有解的情况下,应用定理 1,求同余式
x 2 ? a(mod p) , p ? 4m ? 3 的解。

? ii ? 在有解的情况下,应用

§ 定理 1 及§ 定理 1 的推论,求同余式 2 3

x 2 ? a(mod p) , p ? 8m ? 5 的解。
解:同余式 x 2 ? a(mod p) 有解,故
1

a2

( p ?1)

? 1(mod p)
49 / 77

《初等数论》习题解答(第三版)广东石油化工学院

?i ?

a

1 ( p ?1) 2

?a ? a

1 ( p ?1) 2

? a(mod p)

由 p ? 4m ? 3 知 (a m?1 )2 ? a(mod p) 故 x ? ?a(mod p) 即为原同余式的解。

? ii ?

由 p ? 8m ? 5 知 ( p ? 1) ? 4m ? 2 ,故

1 2

a 4 m? 2 ? 1 ? 0(mod p)
故 (a 2 m?1 ? 1)(a 2 m?1 ? 1) ? 0(mod p) 因此 (a 2 m?1 ? 1) ? 0(mod p) 或 (a 2 m?1 ? 1) ? 0(mod p) 若前式成立,那末 a 2 m?1 ? a ? a(mod p) 即

(a m?1 )2 ? a(mod p)

若 a 2 m?1 ? 1(mod p) 则原同余式的解是 x ? ? a m?1 (mod p) 即 x ? ? a m?1 (mod p) 为原同余式的解。

1 若后式成立,那末 a 2 m?1 ? a ? ?a(mod p)
由§ 定理 1 的推论知,2 是模 p 的平方剩余,即 3
1

22
于是:

( p ?1)

? 24m?2 ? ?1(mod p)

24 m? 2 ? a 2 m? 2 ? a(mod p)

2 若 a 2 m?1 ? ?1(mod p) 则原同余式的解是
x ? ?22 m?1 a m?1 (mod p)
故 x ? ?22 m?1 a m?1 (mod p) 为原同余式的解. § 合数模的情形 6

1. 解同余式

2 ) ? i ? x2 ? 5 9 ( m o d 1 ,5? ii ?

x ? 41(mod 64)

解:从同余式 x 2 ? 59(mod125) 得 x ? 2(mod 5)
50 / 77

《初等数论》习题解答(第三版)广东石油化工学院

令 x ? 2 ? 5t1 代入 x ? 59(mod 25) 得出

(2 ? 5t1 ) 2 ? 59(mod 25)
从而 20t1 ? 5(mod 25) 即有 4t1 ? 1(mod 5) 故 t1 ? 4(mod 5) , t1 ? 4 ? 5t2 再令 x ? 2 ? 5t1 ? 2 ? 5(4 ? 5t2 ) ? 22 ? 25t2 代入

x2 ? 5 9 ( m o d 1 2 5 )
得出

( 2 2 2 25 2 ? ? t )

5 9 ( m o d 1 即5 ) t2 ? ?50(mod125) , 2 100
故 t2 ? 2(mod 5)

从而 4t2 ? ?2(mod 5)

所以 x ? 22 ? 25 ? 2 ? 72 为所给同余式的解 从而所有的解为: x ? ?72(mod125) (ⅱ) x 2 ? 41(mod 64)

41 ? 1(mod8) ,故有四解
记 x ? 1 ? 4t3 代入 x 2 ? 41(mod16) ,即有: (1 ? 4t3 ) 2 ? 41(mod16) 解得 t3 ? 1(mod 2) 记 x ? 1 ? 4(1 ? 2t4 ) ? 5 ? 8t4 ,代入 x 2 ? 41(mod 32) 即有: (5 ? 8t4 ) 2 ? 41(mod 32) ,解得: t4 ? 1(mod 2) 又记 x ? 5 ? 8 ?1 ? 2t5 ? ? 13 ? 16t5 ,代入 x 2 ? 41(mod 64) 即有 ?13 ? 16t5 ? ? 41(mod 64) ,解得: t5 ? 0(mod 2)
2

故 x ? 13(mod 64) 为其一解 其余三解为: x ? 13 ? 32 ? 45(mod 64)

x ? ?1 3 ( m o d 6 4 )
51 / 77

《初等数论》习题解答(第三版)广东石油化工学院

x ? ?4 5 ( m o d 6 4 )
2. (ⅰ)证明同余式 x 2 ? 1(mod m) 与同余式 ( x ? 1)( x ? 1) ? 0(mod m) 等价, (ⅱ)应用(ⅰ) 举出一个求同余式 x 2 ? 1(mod m) 的一切解的方法。 证明: (ⅰ)显然
? ? (ⅱ)记 m ? 2? p1 1 ? pk k

x 2 ? 1(mod m) 有解,等价于方程组
x 2 ? 1(mod 2? ), x 2 ? 1(mod pi?i ), i ? 1, 2,?, k
有解 易见 x 2 ? 1(mod 4) 的解为 x ? 1,3(mod 4)

x 2 ? 1(mod8) 的解为 x ? 1,3,5,7(mod8) x 2 ? 1(mod 2? ), ? ? 3 的解为 x ? 1,1 ? 2? ?1 , ?1, ?1 ? 2? ?1 (mod 2? )
x 2 ? 1(mod pi?i ) ? x ? 1 ? 0(mod pi?i ) 或 x ? 1 ? 0(mod pi?i )
二者不能同时成立,否则 p ? 2 矛盾 故它有两个 x ? ?1(mod pi?i ), i ? 1, 2,?, k 解,联立方程组即可求出一切解。 第六章 原根与指标 1. 设 p 是单质数,a 是大于 1 的整数,证明: (i) a p ? 1 的奇质数 q 是 a-1 的因数或是形如 2px+1 的整数,其中 x 是整数 (ii) a p ? 1 的单质因数是 a+1 的因数或是形如 2px+1 的整数,其中 x 是整数 证明(i)设 q a p ? 1 则 a p ? 1(mod q) 设 a 对模 q 的质数是 ?

? P 是质数 从而 ? ? 1 或 p

若 ? ? 1 ,则 a p ? 1(mod q) ,故 q a p ? 1 ; 若 ? ? p ,而 ? ? ? q ? ? q ? 1 ,q-1 为偶数,
52 / 77

《初等数论》习题解答(第三版)广东石油化工学院

记 q-1=2x,则 p 2x ,又假设 p x 故 q=2px+1 得证。 (ii)设 q 为 a p ? 1 的奇质因数,则 a p ? ?1(mod q) 从而 a 2 p ? 1(mod q) ,从而 a 对模 q 的指数 ? 2 p .故 ? ? 1 ,2,p,2p 之一 若 ? ? 1 ,则 a ? 1(mod q) ,从而 a p ? 1(mod q) 即有 1 ? ?1(mod q) ,不可能,故 ? ? 1 若 ? ? 2 ,则 a 2 ? 1(mod q ) ,而 a 2 ?1(mod q ) (否则 ? ? 1 ) 故 a ? ?1(mod q) ? q a ? 1 若 ? ? p ,则 a p ? 1(mod q) ,而有 1 ? ?1(mod q) ,不可能 若 ? ? 2 p ,则由 ? ? (q ) ? q ? 1 ,q-1=2m ? p m 记 m=px,则 q=2px+1,得证 2. 设 a 对模 m 的指数是 ? ,试证 a ? 对模 m 的指数是 证明:设 a ? 对模 m 的指数为 ? ,则
? a ? ? ? ( a ?) ? 1 ( m om d

? (? , ? )

)

? ? ?? ? ?? ? ? k ?

? ? ? (? , ? ) (? , ? )

而?

? ? ? ? ? , ? ? ? 1 ,股 (? , ? ) ? (? , ? ) (? , ? ) ?
? ? ?

? ,? 反之 a ? ? ? ,? ? ? a ? ? ? a? ? ? ,? ? ? 1? mod m ?

? ?

? ?

?

故?

? ? ,从而 ? = 得证 ??,? ? ??,? ?

例 1 求 1,2,3,4,5,6 对模 7 的指数。 根据定义 1 直接计算,得到 ?7(1) = 1,?7(2) = 3,?7(3) = 6, 53 / 77

《初等数论》习题解答(第三版)广东石油化工学院

?7(4) = 3,?7(5) = 6,?7(6) = 2。
例 1 中的结果可列表如下: a ?7(a) 1 1 2 3 3 6 4 3 5 6 6 2

这样的表称为指数表。这个表就是模 7 的指数表。 下面是模 10 的指数表: a ?10(a) 1.写出模 11 的指数表。 解 : 经 计 算 得 ? 1 1 ( 1 ) = 1 , ? 1 1 ( 2) = 1 0 , ? 1 1 ( 3 ) = 5 , ? 1 1 ( 4 ) = 5 , ? 1 1 ( 5 ) = 5 , ? 1 1 ( 6) = 1 0 , ? 1 1 ( 7) = 1 0 , ? 1 1 ( 8 ) = 1 0 , ? 1 1 ( 9) = 5 , ? 1 1 ( 1 0 ) = 2 , 列 表 得 a 1 1 2 10 3 5 4 5 5 5 6 10 7 10 8 10 9 5 10 2 1 1 3 4 7 4 9 2

?11(a)

2. 求 模 14 的 全 部 原 根 。 解 : x ? 3, 5 ( m o d 14 ) 是 模 1 4 的 全 部 原 根 。

1. 求 模 29 的 最 小 正 原 根 。 解 : 因 ?(29) = 28 = 22?7, 由
? (29)

2

2

? 214 ? 1(mod 29), 2 ?

? (29)
7

? 24 ? 1(mod 29) ?

知 2 是 模 29 的 最 小 正 原 根 。 2. 分 别 求 模 293 和 模 2?293 的 原 根 。 解 : 由 2 是 模 29 的 原 根 及 2 2 9
? 1

? = 228 = 228 ? 1 (mod 292)知 2 是 模 293 的 原 根 ;
54 / 77

《初等数论》习题解答(第三版)广东石油化工学院

由 2 是 模 2 9 3 的 原 根 及 2 是 偶 数 知 2 + 2 9 3 是 模 2 ? 29 3 的 原 根 。 3 . 解 同 余 方 程 : x 1 2 ? 1 6 ( m o d 1 7) 。 解 : 易 得 3 是 模 1 7 的 原 根 , 3 i ( i = 0 , 1 , 2 , ? , 1 5) 构 成 模 17 的 简 化 剩 余 系 , 列表为 i 7 3 ( m o d 1 7) 11 i 15 3 ( m o d 1 7) 6 由 上 表 知 3 8 ? 1 6 ( m od 1 7 ) , 设 x ? 5
y i i

0 1 8 16

1 3 9 14

2 9 10 8

3 10 11 7

4 13 12 4

5 5 13 12

6 15 14 2

( m od 1 7 ) , 则 1 2y ? 8 ( mo d 16) , 由 此 解

得 y 1 ? 2 , y 2 ? 6 , y 3 ? 1 0 , y 4 ? 1 4 ( m o d 1 6) , 查 上 表 得 x 1 ? 9, x 2 ? 1 5, x 3 ? 8 , x 4 ? 2 ( m o d 1 7) 。

? 3 指标及 n 次剩余
1.设 q1 , q2 , ???, qn 是 ? (m) 的一切不同的质因数,证明 g 是模 m 的一个原根的充要条件是 g 对 模 m 的 qi (i ? 1, 2, ???, n) 次非剩余。 证明:必要性,设 g 为模 m 的一个原根 由 ? 2 Th5 知 g ? ( m ) ? 1(mod m), i ? 1, 2, ???, m 若 g 为模 m 的 qi 次剩余,则存在 x0 ,使得

x0 qi ? g (mod m), ( x0 , m) ? 1
又由欧拉定理 x0? ( m ) ? 1(mod m)
? ( m) ? ( m)

故g

qi

? ( x0 qi )

qi

? x0? ( m) ? 1(mod m) ,矛盾!

充分性,若 g 不为模 m 的一个原根,由 ? 2 Th5 知
? ( m)

存在 qt ,使得: g

qt

? 1(mod m)
55 / 77

《初等数论》习题解答(第三版)广东石油化工学院

设 g ' 为模 m 的一个原根,则对上式两边关于 g ' 取指标:

? ( m)
qt

Ind g ' g ? 0(mod ? (m))

? Ind g ' g ? 0(mod qt )


I n d' g ? ? g

t

q ,则由指标的定义即有:

? ( g ' ) qt ? g ( m o m ) d
q 故 x ? ( g ' )? (mod m) 即为同余式 x t ? g (mod m) 的解

从而 g 为 qt 次剩余,矛盾。 2.证明 10 是模 17 及模 257(质数)的原根,并由此证明把 的长度分别是 16 及 256. 证明: ? (17) ? 16 ,它的有且只有质因子 2,而
36 ? 17 ? ? 10 ? ? 2 ?? 5 ? ?2? ? ? ? ? ?? ? ? ? ?1? ? ? ? ? ? ? ?1 ? 17 ? ? 17 ?? 17 ? ? 5 ? ?5?

1 1 化成循环小数时,循环节 , 17 257

从而 10 不是模 17 的平方剩余,由上题知 10 是模 17 的原根。

? (257) ? 256 ? 28 ,由且仅有质因子 2,而
? 10 ? ? 2 ?? 5 ? ? 257 ? ? 2 ? ? ??? ?? ??? ? ? ? ? ? ?1 ? 257 ? ? 257 ?? 257 ? ? 5 ? ? 5 ?
故同上理 10 也是模 257 的原根。 由 ch 3§ Th2.3 的证明可知, 4 的指数,从而 t=16,256 3.试利用指标表解同余式 证毕

1 1 , 的循环节的长度,t,这是 10 关于模 17,模 257 17 257

x15 ? 14(mod 41)
解:同余式 x15 ? 14(mod 41) 等价于:

15 Ind x ? Ind14(mod 41)
查表知 Ind14 ? 25 ,故:
56 / 77

《初等数论》习题解答(第三版)广东石油化工学院

15 I n dx ? 2 5 ( m o d 4 0 )
由于 ?15,40 ? ? 5 | 25 ,故上式由 5 个解, 解之得: Ind x ? 7,15, 23,31,39(mod 40) 查表知:原同余式的 5 个解为:

x ? 2 9 , 3 , 3 0 , 3 1, 7 ( m o d 4 1)
4. 设模 m (m. 的原根是存在的, >2) 试证对模 m 的任一原根来说,?1 的指标总是 ? ( m) . 证明:模 m 的原根存在,故 m=4, p? 或 2 p ? 设 g 为模 m 的一个原根,则 g ? ( m ) ? 1(mod m)
1

1 2

从而 ( g 2

? ( m)

?1)( g 2

1

? ( m)

? 1) ? 0(mod m)

? ??

? i ? 若 m=4, ? ? 4 ? ? 2 ,则模 m 有且只有一个原根 3,
31 ? ? 1 ( m o d ,) m
故 ?1 的指标为 1 ?

? ? m?
2

? ?1? ? 1 若 m ? p? , p 为奇质数,则由 ? ?? 知

? ?9? ? 0 或 p | g 2

1

? ( m)

?1
1

但二者不能同时成立,否则 p | ( g 2
1

? ( m)

? 1)( g 2

1

? ( m)

?1) ? 2 ,矛盾!

若 p | g2

? ( m)

?1, p | g 2
?

1

? ( m)

? 1, 又由(*)知

p |g ?g
1 ? ( m) 2

1 ? ( m) 2

,与 g 的指数为 ? (m) 矛盾。 ? 1 (mod m)
1

从而 p | g 2

? ( m)

? 1, p | g 2

1

? ( m)

? 1 ,从而 p? | g 2

1

? ( m)

?1

? g2

1

? ( m)

? ?1 (mod m)

57 / 77

《初等数论》习题解答(第三版)广东石油化工学院

故-1 的指标为 ? ( m) 。

1 2

(iii) 若 m ? 2 p? , g 为 2 p ? 的原根,则 g 为奇数
类似于 (ii) 的讨论,我们有

p? | g 2
从而 从而

1

? ( m)

?1 , p? | g 2
1

1

? ( m)

?1

2 p? | g 2
1

? ( m)

?1

g2

? ( m)

? ?1 (mod m)
1 2

故-1 的指标为 ? ( m) 。 5、设 g , g1 是模 m 的两个原根,试证:

(i )

ind g1 g ? ind g g1 ? 1 (mod ? (m) ) ;
(mod ? (m) ) 。

(ii) ind g a ? ind g g 1?ind g1 a
证明: (i ) 由指标的定义知:

g

i n gd 1 g

? g1 (mod m)

两边对原根 g1 取指标:

ind g1 g


ind g g1

? ind g1 g1 (mod ? (m) )

ind g1 g ? ind g g1 ? 1 (mod ? (m) )

(ii) 由指标的定义知:

g1

i n gd 1

?a
a

(mod m)

两边对原根 g 取指标:

ind g g


i n gd 1

? ind g a
a

(mod ? (m) ) (证毕)

ind a g ?

i n d ? g 1g n d(mod ? (m) ) i a 。 g 1

58 / 77

《初等数论》习题解答(第三版)广东石油化工学院

第九章 数论函数 § 1. 可乘函数 1. f ( x) 是一个可乘函数, 设 证明 F ( x) ? 可乘函数.

? f (d ) 也是一个可乘函数.由此说明 s(a),
dx

? (a) 是

d 证明: 首先我们证明: ( x1 , x2 ) ? 1 , d1 跑过 x1 的全部因子, 2 跑过 x2 的全部因子, d ? d1d 2 设 若 则
跑 过 mn 的 全 部 因 子 , 事 实 上 , 因 为 d1 x1 ,
' d 2 x2 , 故 d1 d 2 x1 x2 , 且 当 d1' x1 , d 2 x2 ,

?d1 ,


' ' d 2 ? ? ?d1' , d 2 ? 时, 由于 ( x1 , x2 ) ? 1 , d1d 2 ? d1' d 2 , 得 反之任给 d x1 x2 , 由于 ( x1 , x2 ) ? 1 ,

(d , x1 ) ? d1
1



(d , x2 ) ? d 2
d x


1 d





d ? d1d , 2 d x

1

, d x1



2



2此

F(

x , ?x ) 2 ?
d
1

? ? ?d ) f(
x
2

f( 2
2

d

) d

x

1

1

2

x

? ? ? f (d1 ) f (d 2 )
d1 x1 d2 x2

? ? f (d1 ) ? f (d2 ) ? F ( x1 ) F ( x2 )
d1 x1 d2 x2

故 F ( x) 为一个可乘函数. 若 f ( x) ? x ,它为可乘函数. ,且 F (a) ? 若 f ( x) ? 1 ,它为可乘函数,且 F (a) ? 故 S (a), ? (a) 为可乘函数. 2. 设 f ( x) 是一个定义在一切正态数的函数,并且 F ( x) ?

(此为 65 页)

? f (a) ? S (a) .
da

? f (d ) ? ? ( a) .
da

? f (d ) 是一个可乘函数,证明
dx

f ( x) 是可乘函数.
证 明 : 反 证 , 假 设 f ( x) 不 是 可 乘 函 数 , 则 存 在 一 对 正 态 数 m, n , (m, n) ? 1 , 使 得 , f ( m n) ? f ( m f ( n) 于 是 我 们 可 以 选 择 这 样 一 对 m, n , 使 得 mn 最 小 . 若 mn ? 1 , 则 )

) fa , f (1)? f (1)f (1)即 f 1 1 , F 1 ? ?( ) ( ? 又 ( )
d1

1 ( ? ) f

,F ( x) 为可乘函数, 故有 f (1 ? F (1) ? 1

矛盾!
59 / 77

《初等数论》习题解答(第三版)广东石油化工学院

若 mn>1 ,则对所有正态数对 a,b ,(a,b)=1,ab<mb ,有

f ( a b ) f= ( fa ) ( b )
于是有: F (mn) ?

?? f (ab)
am bn

?

? ?
am

f ( a b? )

f( m n )

a m b n , ab mn ?

?

f ( a) f ( b? )

f(mn )

a m b n , ab mn ?

=

? f (a)? f (b) ? f (m) f (n) ? f (mn)
bn

= F (m) F (n) ? f (m) f (n) ? f (mn) 因为 f (mn) ? f (m) f (n) ,故 F (mn) ? F (m) F (n) 此与 F ( x) 为可乘函数矛盾!

3.证明:

? ? ?? ? a ? ? a ? ?
? da

证明:首先易证,若 d 为 a 的正约数,那么 a a 的完全剩余系中与 a 的最大公约数是 d 的个 数为 ? ?

?a? ?。 ?d ?
a a a , ,? , 也是 a 的所有正约数,于是 d1 d 2 dr

其次,若 d1 , d 2 ,?, d r 为 a 的所有正约数。那么
r r

?? ? d ? ? ?? ? d
i ?1 i i ?1

?a? ? ? i?

最后,在 a 的完全剩余系中住一数与 a 的最大公约数必定是 d1 , d 2 ,?, d r 中某一个,而完全 剩余系中与 a 最大公约数为 d i 的数有 ? ?

?a ? di

? ? 个,所以 ?

?? ? d ? ? ?? ? d
i ?1 i i ?1

r

r

?a? ??a ? i?
60 / 77

《初等数论》习题解答(第三版)广东石油化工学院

4.试计祘和式

? x , m ? ?1

x ?1

?

m

x2

解:此题较复杂,下分数步解之: s 1 M o b i u?反演公式 设 f 和 g 是两个数论函数,且 f ? n ? ? 事实上,

? ? ? d ?g ? d ? ,则 g ? n ? ? ? f ? d ? 反之亦然 ? ?
dn

?n?

dn

? f ? d ? ? ? f ? d ? ? ? ? ? ? cd ? g ? c ? ? ? ? ?
dn dn dn c n d

?n?

? n ?

? n ? ? n ? ? ? ? ? ? g ? c ? ? ? g ? c ?? ? ? ? ? cd ? ? cd ? n cd n cn d
c

? g ?n?
反之,类似可得。参见习题 5 及 6 。 ②若 (x) 是定义在闭区间 ? 0,1? 上的函数,n 正整数,记 f
n k F(n) ? ? f( ) , n k ?1

F * ( n)? ?
k ?1

n

n F( ) , k n ) ( ,? d

1

则 F * ( n) ?

? ? (d )F ( d )
d n

n

事 实 上 , 由 ① , 只 要 证 明 F ( n) ?

?
d n

n F *( ) , 但 这 几 乎 是 明 显 的 , 因 为 如 果 分 数 d

? 2 n a 化成既约分数,就得到形如 的分数,这里 1 ? a ? b , b 是 n 的一个约数.每 , ,? , , n n n b
一个这样形式的分数都可得到一次也好一次. ③ 记

?? (m )? ? x2 , (x ,m?) ,1 则
x ?1

m

?2 (m)
m2

m x ? ? ( ) 2 , ( x, m) ? 1 x ?1 m

记 F * (m) ?

x ? (m) x ?1

n

2

则 F ( m) ?

?(m)
x ?1

m

x

2

?

?x
x ?1

m

2

m

2

?

m(m ? 1)(2m ? 1) (m ? 1)(2m ? 1) ? 6m 2 6m
61 / 77

《初等数论》习题解答(第三版)广东石油化工学院

那么 F ( ) ? 这样由②知:

m x

1 m x 1 1m 1 x (3 ? 2 ? ) ? ? ? 6 x m 2 3 x 6m
m

?2 (m)
m
2

?

x m

? ? ( x) F ( x )
x m

?

[ ? ?(x ) 2 ?

1

1m 1x ? ] 3x 6m

?

1 1 m 1 ( ) ?m? ( x ) ? 3 ? m ? (x )? 6 ? ? x x 2x x x x m

由本节推论 2.2 2.3,即有:

? 2 (m) m 2? (m) ?

1 3

1 ? (1 ? p) 6 pn

5. (x) 是任一函数,并且: f

g (a )? ? f d ) (
d a

试证: f (a) ?

? ? ( d )g (d ) ? ? ? (d )g ( d )
d a d a

a

a

证明:设

a ? d ' , 即 dd ' ? n ,则 d ??(d )g (d ' ) ? ? ?(d )? f (c) ? ? ?(d ) f (c)
d a d a c d' cd a

? ? f (c )? ? d ) (
ca d n c

由推论 2.3 知,其内部之和只有当 c=a 时为1,c<a 时,为0,故上式右边等于 f (a ) . 设是 f ( x) 任一函数,并且:

a f (a ) ? ? w( )g (d ) d da
证明: g (a) ?

? f (d )
da

证明:其证法与上习题类似,我们有:

? f (d ) ? ? f ( d ) ? ?? w( cd )g (c)
da da da c n d

a

a

62 / 77

《初等数论》习题解答(第三版)广东石油化工学院

? ? w(
cd a

a )g (c) cd

a ? ? g (c ) w ( ? g a ( ) ? cd ) n cn d
c

7.设 F ( x), G( x) 是定义在实数上的两个函数,并且对于任何不小于 1 的实数 x 来说:
? ? x G ( x) ? ? F ( ) n n ?1
x

则 F ( x) ?

? w(n)G( n )
n ?1

? x?

x

反之,亦然. 证明:
?x? ? ? ?n? ? ? x x ? ? ? w(n)G( n ) ? ? ?w( n ) ?1 F ( mn ) ? n ?1 n ?1 ? m? ? ? ?

? x?

? x?

x ? w( 1 ? F ( ) ? w ) m m ?1

? x?

? ? x x ) ? ? ? w(? x?) ? F ( ) (? F ( 2 ) 2m ? x? m ?1 m ?1
x

? x?

(?)

记 m ? 2k ,则 n k ,并且 k 遍取数目 1, 2,?, ? x ? ,则

? x ? ? ? ? F ( )? w( n ) ? 1? k ?? x ? ? ? ? k nk ? x x x x ? F ( ) w(1) ? F ( )( w(1) ? w(2) ) ? F ( )( w(1) ? w(2) ) ? ? ? F ( ) ? w( n ) 1 2 3 ? x ? n ? x?

?

( ?? )

比较 (?), (??) 两式即有

?w
n ?1

? x?

(n)

? ? x ? x ? G ( ) ? ? ? F ( )? w( n ) ? n 1? K ?? x? ? k n k ? ? ?

上式右边除第一页 k ? 1时)=F(x),其余诺项都等于 0(推论 2.3)右上式右边等于 F ( x) ( 类似可证明它的逆定理成立。

63 / 77

《初等数论》习题解答(第三版)广东石油化工学院

初等数论试卷 一、 单项选择题: 分/题× 题=20 分) (1 20 1.设 x 为实数, ? x ? 为 x 的整数部分,则( A. ? x ? ? x ? ? x ? ? 1 ; C. ? x ? ? x ? ? x ? ? 1 ; )

B. ? x ? ? x ? ? x ? ? 1 ; D. ? x ? ? x ? ? x ? ? 1 . )

2.下列命题中不正确的是(

A.整数 a1 , a2 ,? , an 的公因数中最大的称为最大公因数; B.整数 a1 , a2 ,? , an 的公倍数中最小的称为最小公倍数 C.整数 a 与它的绝对值有相同的倍数 D.整数 a 与它的绝对值有相同的约数 3.设二元一次不定方程 ax ? by ? c (其中 a, b, c 是整数,且 a, b 不全为零)有一整数解

x0 , y0 , d ? ? a, b ? ,则此方程的一切解可表为(
a b t , y ? y0 ? t , t ? 0, ?1, ?2,?; d d a b B. x ? x0 ? t , y ? y0 ? t , t ? 0, ?1, ?2,?; d d b a C. x ? x0 ? t , y ? y0 ? t , t ? 0, ?1, ?2,?; d d b a D. x ? x0 ? t , y ? y0 ? t , t ? 0, ?1, ?2,?; d d
A. x ? x0 ?

)

4.下列各组数中不构成勾股数的是( ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( ) A. a1 ? b1 ? mod m ? , a2 ? b2 ? mod m ? ? a1 ? a2 ? b1 ? b 2 ? mod m ? ; B. a1 ? b1 ? mod m ? , a2 ? b2 ? mod m ? ? a1a2 ? b1b 2 ? mod m ? ; C. a1 ? b1 ? mod m ? ? a1a2 ? b1a 2 ? mod m ? ;
2 2 D. a1 ? b1 ? mod m ? ? a1 ? b1 ? mod m ? .

6.模10的一个简化剩余系是( A. 0,1, 2,?,9;

) B. 1, 2,3, ?,10;
64 / 77

《初等数论》习题解答(第三版)广东石油化工学院

C. ?5, ?4, ?3, ?2, ?1,0,1, 2,3, 4;

D. 1,3, 7,9. )

7. a ? b ? mod m ? 的充分必要条件是( A. m a ? b ; C. m a ? b ; B. a ? b m ; D. a ? b m .

4 3 8.设 f ? x ? ? x ? 2 x ? 8 x ? 9 ,同余式 f ? x ? ? 0 ? mod 5 ? 的所有解为(

)

A. x ? 1 或 ?1; C. x ? 1 或 ?1? mod 5 ? ;

B. x ? 1 或 4; D.无解.

9、设 f(x)= an x n ? ?? ? a1 x ? a0 其中 ai 是奇数, 若x ? x0 ? mod p? 为 f(x) ? 0 ? mod p ? 的一个 解,则:( ) A. ? ? ? ? mod p ? 一定为f ( x) ? 0 mod p ? , ? ? 1的一个解 B. ? ? ? 0 mod p ? , ? ? 1, 一定为f ( x) ? 0 mod p ? 的一个解 C. 当p不整除f ( x)时, f ( x) ? 0 mod p? 一定有解x ? x0 mod p? , 其中x? ? x0 ? mod p ? D. 若x ? x0 mod p? 为f ( x) ? 0 mod p? 的一个解, 则有x? ? x0 ? mod p ?
n 10. 设f ( x) ? an x ? ?? ? a1 x ? a0 , 其中ai 为奇数, an ? 0 ? mod p ? , n ? p, 则同余式 ?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

f ( x) ? 0 ? mod p ?的解数 : (



A.有时大于 p 但不大于 n; B.可超过 p C.等于 p D.等于 n 11.若 2 为模 p 的平方剩余,则 p 只能为下列质数中的 :( A.3 B.11 C.13 12.若雅可比符号 ?

) D.23

?a? ? ? 1 ,则 ( ?m?

)

2 A. 同余式x ? a ? mod m ? 一定有解, 2 B. 当 ? a, m ? ? 1时,同余式x ? a ? mod p ? 有解 ; 2 C. 当m ? p(奇数)时,同余式x ? a ? mod p ? 有解 ;

65 / 77

《初等数论》习题解答(第三版)广东石油化工学院
2 D. 当a ? p(奇数)时,同余式x ? a ? mod p ? 有解 .

13. 若同余式x 2 ? a mod 2? , ? ? 3, ? 2, a ? ? 1有解, 则解数等于 ( A. 4 B. 3 C. 2 D. 1 14. 模 12 的所有可能的指数为;( ) A.1,2,4 B.1,2,4,6,12 C.1,2,3,4,6,12 15. 若模 m 的单根存在,下列数中,m 可能等于: ( ) A. 2 B. 3 C. 4 D. 12 16.对于模 5,下列式子成立的是: ( ) A. ind3 2 ? 2 C. ind3 5 ? 0 B. ind3 2 ? 3 D. ind310 ? ind3 2 ? ind3 5 )

?

?

)

D.无法确定

17.下列函数中不是可乘函数的是: ( A.茂陛鸟斯(mobius)函数 w(a) ; B. 欧拉函数 ? ? a ? ; C.不超过 x 的质数的个数 ? ? x ? ; D.除数函数 ? ? a ? ;

18. 若 x 对模 m 的指数是 ab , a >0, ab >0,则 x? 对模 m 的指数是( A. a B. b C. ab D.无法确定 ) 19. f ? a ? , g ? a ? 均为可乘函数,则( A. f ? a ? g ? a ? 为可乘函数; C. f ? a ? ? g ? a ? 为可乘函数; B.

)

g ?a?

f ?a?

为可乘函数

D. f ? a ? ? g ? a ? 为可乘函数 )不成立 C. ? ? 2 ? ? ?1 D. ? ? 9 ? ? 0

20.设 ? ? a ? 为茂陛乌斯函数,则有( A. ? ?1? ? 1 B. ? ? ?1? ? 1

二.填空题: (每小题 1 分,共 10 分) 21. 3 在 45 ! 中的最高次 n= ____________________; 22. 多元一次不定方程: a1 x1 ? a2 x2 ? ? ? an xn ? N ,其中 a1 , a2 ,…, an ,N 均为整数,

n ? 2 ,有整数解的充分必要条件是___________________;
66 / 77

《初等数论》习题解答(第三版)广东石油化工学院

23 . 有 理 数

a , 0 ? a ? b , ? a, b ? ? 1 , 能 表 成 纯 循 环 小 数 的 充 分 必 要 条 件 是 b

_______________________; 24. 设 x ? x0

? mod m ? 为一次同余式 ax ? b ? mod m ? ,a

? 0 ? mod m ? 的一个解,则它的所有

解为_________________________; 25. 威尔生(wilson)定理:________________________________________; 26. 勒让德符号 ?

? 503 ? ? =________________________________________; ? 1013 ?

27. 若 a, p ? ? 1 ,则 a 是模 p 的平方剩余的充分必要条件是_____________(欧拉判别条件); 28. 在模 m 的简化剩余系中,原根的个数是_______________________; 29. 设 ? ? 1, g 为模 p? 的一个原根,则模 2 p ? 的一个原根为_____________; 30. ? ? 48 ? ? _________________________________。 三.简答题: 分/题× 题=20 分) (5 4 31.命题“任意奇数的平方减 1 是 8 的倍数”对吗?说明理由。 32.“若 a, m ? ? 1 , x 通过模 m 的简化剩余系,则 ax 也通过模 m 的简化剩余系”这命题是否正 确?正确请证明,不正确请举反例。 33.求模 17 的简化剩余系中平方剩余与平方非剩余。
? ? ? 34.设 a ? p1 1 p2 2 ? pk k 为 a 的标准分解式,记 S ? a ? 为 a 的正因数的和,? ? a ? 为 a 的正因数的

?

?

个数,则 S ? a ? =?

? ? a ? =? 为什么?

四.计算题。 分/题× 题=28 分) (7 4 35. 求不定方程 6x+93y=75 的一切整数解。

? x ? 1? mod 5 ? ? 36. 解同余方程组 ? y ? 3 ? mod 6 ? ? z ? 2 ? mod 7 ? ?
37.解同余式 x 2 ≡11(mod125) 38.求模 13 的所有原根。 五、证明题: 分/题× 题=14 分) (7 2 39、试证: x 2 ? 2 y 2 ? z 2 , (x,y)=1 y 是偶数的整数解可写成:

x ? ?(a 2 ? 2b2 ) y ? 2ab

z ? a 2 ? 2b2
67 / 77

《初等数论》习题解答(第三版)广东石油化工学院

这里 a ? b ? 0 , ? a, b ? ? 1 ,并且 40、设 a 为正整数,试证:

一为奇数,一为偶数。

? ? (d ) ? ? ? ( d ) ? a
d |a d |a

a

其中

?
d |a

表示展布在 a 的一切正因数上的和式。

六、应用题: 分) (8 41、求 30!中末尾 0 的个数。 参考答案:一.单项选择:ABCDD;DACCB;DCAAD;BCBAB。 二. 填空题: 21. 21; 22.? a1 , a2 ,? , an ? | N ; 23.? b,10 ? ? 1 ; 24.x0 ? t 25. ? p ? 1? !+1 ? 0 ? mod p ? , p 为素数;26.1; 27. a
p ?1 2

m , t ? 0, ?1, ?2,? ; ? a, m ?

? 1? mod p ? ;28. ? ?? ? m ? ? ;29. g 与 g ? p? 中的单数;30.16

三.简答题:31.答:命题正确。?

? 2m ? 1?

2

? 1 ? ?? 2m ? 1? ? 1? ?? 2m ? 1? ? 1? ? ? ? ?

? 2m ? ? 2m ? 2 ? ? 4m ? m ? 1? 而 m ? m ? 1? 必为 2 的倍数。
86 页 32.正确.证明见教材 P47 。 33 . 在 摸 p 的 简 化 剩 余 系 中 与 12 , 22 ,? , ?

? p ?1 ? ? 同余的数是数 p 的平方剩余, ? 2 ?
2

p ? 17,

1 ? p ? 1? ? 8 , 12 ? 1, 22 ? 4,32 ? 9, 42 ? 16 , 52 ? 8, 62 ? 2, 72 ? 15,82 ? 13 2

故 1,2,4,8,9,13,15,16 为摸 17 的平方剩余,而 3,5,6,7,10,11,12,14 为摸 17 的平方非剩余。 34. s ? a ? ?

??
k i ?1

1 ? pi ? pi2 ? ? ? pi?i ? ?
i ?1

?

k

p?i ?1 ? 1 pi ? 1

? ? a ? ? ??1 ? 1??? 2 ? 1?? ?? k ? 1?
证明:若 f ? a ? 为可乘函数,则

? f ?? ? ? ? ?1 ? f ? p ? ? ? f ? p? ? ? . ?
k
i

i

i

|a

i ?1

分别令 f ? a ? ? a. f ? a ? ? 1 ,它们为可乘函数,即得出。
68 / 77

《初等数论》习题解答(第三版)广东石油化工学院

四.计算题 35.解:因为 ? 6,93? ? 3 | 75 ,故原不定方程有解。 又原方程即 2 x ? 31y ? 25 ,而易见方程 2 x ? 31y ? 1 有解
' ' x0 ? 16, y0 ? ?1 。所以原方程的一个解是 x0 ? 400, y0 ? ?25

所以,原方程的一切整数解是: (



x ? 400 ? 31t r ? ?25 ? 2t

t 是整数

36.解:因为模 5,6,7 两两互质,由孙子定理得所给同余方程组关于模 5× 7=210 有唯一解,分别解同余方程: 6×

42 x ? 1? mod 5 ? , 35 x ? 1? mod 6 ? , 30 x ? 1? mod 7 ? ,得 x ? 3 ? mod 5? , x ? ?1? m o d?6 x ? 4 ? mod 7 ? ,

因此所给同余方程组的解是:

x ? 42 ? 3 ?1 ? 35 ? ? ?1? ? 3 ? 30 ? 4 ? 2 ? mod 210 ?
即: x ? 261 ? 51? mod 210 ?
2 37.解:从同余方程 x ? 11? mod 5? 得x ? 1? mod 5? ,

再从 ?1 ? 5t1 ? ? 11? mod 52 ? , 得10t1 ? 10 ? mod 52 ? ,
2

因此t1 ? 1? mod 5 ? , 于是1 ? t1 ? 6 ? mod 52 ? ,
2 2 2 是 ? ? 11 mod 5 的解, 又从 6 ? 5 t2

?

?

?

?

2

? 11 ? mod 53 ?

得 300t2 ? ?25 mod 53 , 因此12t2 ? ?1? mod 5 ?
2 即 t2 ? 2 ? mod 5 ? , 所以x ? 6 ? 5 ? 2 ? 56

?

?

是所给方程的一个解,于是所解为:

x ? ?5 6? m o d 1?2 5
2 38.解: ? ?13? ? 12 ? 2 ? 3,

解毕。

g1 ? 2, g2 ? 3 为其质因数

? ?1 3 ?
2

?6,

? ? 1 ?3
3

? 4 ,故 g 为模 13 的原根的主要条件是:

69 / 77

《初等数论》习题解答(第三版)广东石油化工学院

g 6 ? 1? m o d 1 , g 4 ? 1? mod13? ?3 ? ?
用 g=1,2,……12 逐一验证,得:2,6,7,11 为模 13 的原根, 因为 ? ?12 ? ? 4 ,故模 13 原根只有 4 个,即为所求。 五、证明题: 39.证明:易验证所给的解为原方程的解,因 y 为偶数,原方程可化为:

z ? x z x ? ?r ? ? ?? ? 2 2 ? 2 ?


2

? z ? z ? x z? x ? z x ? ?x ? , , ?z ? ?| ? ? 2 ? ? 2 2 ? ? 2

? z ? x z? , ? 2 ? 2


x ? z x ? ? z ? , ?| ? 2 ? ? 2
,所以(

?x ?x ? ?

z?x z?x , )=1 2 2 z?x 2 =b 2

由书中引理,我们可假设

z?x = a2 , 2
X= a 2 -b 2 ,

显然 a >b, ( a ,b)=1, 于是 z= a 2 + b 2 ,y=2 ab

因子为奇数,所以 a ,b 一定是一为奇,一为偶,证毕 40.证明:假定 d1 ,---, d k 为 a 的所有正约数,那末

a a ,---, 也是 a 的所有正约数,于是 d1 dk

? ? (d ) = ? ? ( d )
d a
d a

a

再因为在 a 的完全剩余系中任一数 a 的最大公约数 必定是 d1 ,---, d k 中某一个数,而完全剩余系中与 a 的最 大公约数为 d i 的数有 ? (

m ) ,所以: di
证毕
70 / 77

?? ( d ) = m
d a

m

《初等数论》习题解答(第三版)广东石油化工学院

六.应用题: 41.解:5 在 30!中的最高次幂= ?

? 30 ? ? 30 ? ? 30 ? + 2 + 3 ? 5 ? ?5 ? ?5 ? ? ? ? ? ?
=6+1+0=7

2 在 30!的最高次幂= ?

? 30 ? ? 30 ? ? 30 ? ? 30 ? ? 30 ? + 2 + 3 + 4 + 5 ? 2 ? ?2 ? ?2 ? ?2 ? ?2 ? ? ? ? ? ? ? ? ? ?

=15+7+3+1+0=26 10=2× 5,故 30!的末尾有 7 个零。

2007 年 4 月广东省高等教教育育自学考试 初等数论试卷 一、 单项选择题。 (本大题共 15 小题,每小题 2 分,共 30 分) 1.-36,420,48 三个数的公因数是( ) A.±1,±3,±4,±5,±6,±12 B. ±1,±2,±3,±4,±6,±,12 C. ±2,±3,±4,±6 D1,2,3,4,5,6,12 2.设 a,b ? Z (整数集),p 是素数,且 p ab 。则( ) A a,b 中恰有一个是 p 的倍数 B.a,b 中没有 p 的倍数 C.a,b 中必有一个是 p 的倍数 D. a,b 都是 p 的倍数 3.设 a,b 是非零整数,d=(a,b),则下列成立的是( ) A 犏,

轾 b a = ab 犏d d 臌 轾 b a ab = 2 犏d d d 臌

B. 犏,

轾b ab a = 犏d d d 臌 轾b ab a = 2 犏d d d 臌

C. 犏,

D. 犏,

4. 设a, b, c, v ? Z 且au A. (ad, bd ) = d C. (ad, bd ) = ab 5.对任意实数 a ,必有( )

bv = 1, 则对于任意 d ? Z + (正整数集)( )
B. (ad, bd ) = abd

ad D. 轾 , bd = d 犏 臌 B. 轾a = a 犏 臌
D.

A. 轾a = 轾a + 1 犏 犏 臌 臌 C. 轾a = 轾a 犏 犏 臌 臌
6.下列不定方程中,有整数解的是( )
71 / 77

{a }

{- a } = - {a }

《初等数论》习题解答(第三版)广东石油化工学院

A. 27x + 75y + 33z = 48 C. 42x - 70y + 14z = 33 7.设 a,b 挝Z , m

B. 27x + 75y + 65z = 72 D. 100x + 20y + 45z = 32

Z + ,a

b(mod m ) 则( )
B.(a,b)=(b,m) D.(a-b,m)=(a,m) ) B. D.

A.(a,b)=(a,m) C.(a,m)=(m,b) 8.下列集合中,是模 15 的简化剩余系的是( A. C.

{1, 2, 3, 5, 7, 8,11,13} {1, 4, 8, 7,11,13,14}

{1, 2, 37, 8} {29,14, - 2, 2,19,,19, 7, 8}

9.下列同余式中成立的是( ) A. 3648 ? 1(mod 49) C. 472 ? 4(mod 72) B. 2720 ? 1(mod 25) D. 3541 ? 1(mod 41)

10.设同余式 ax ? b(mod m ) 有解,则下述断语中正确的是( ) A. 该同余式有模 m 的 m-1 个解 B. 在模 m 的一组完全剩余系中,有(b,m)个数满足该同余式 C. 在模 m 的一组完全剩余系中,有(a,m)个数满足该同余式 D. 在模 m 的一组完全剩余系中,有(ab,m)个数满足该同余式 11.设素数 p>2,a,b 分别是模 p 的平方剩余和平方非剩余,则下列成的是( ) A.ab 是模 p 的平方非剩余 C a 2b 是模 p 的平方剩余 12.设对模 m 的指数为 k.,则( ) A. k m C. k a 13.若模 m 的原根存在,则 m 可能是( A.15 的倍数 B.81 的 2 倍 ) B.16 的倍数 D.42 的倍数 B. m k D, k j (m ) B. ab2 是模 p 的平方非剩余 D. a 2b2 是模 p 的平方非剩余

14.若 x 对模 m 的指数是 ab,a>0,b>0,则 x b 对模 m 的指数是( )

A.

ab m

B.b
72 / 77

《初等数论》习题解答(第三版)广东石油化工学院

C. a - b

D.a

15.设 g 是模 m 的一个原根, c = j (m ) .K 是模 c 的一个非负完全剩余系,则 L= ( ) A.模 m 的一个完全剩余系 B 模 m 的一个简化全剩余系 C 模 c 的一个完全剩余系 D 模 c 的一个简化全剩余系 二. 填空题(本大题共 10,每小题 2 分,共 2 分) 16.设 a = 24 创35

{g , t ? K }是
t

53 ? 112, b

22 创56

74

132, c = 3 创53

75

133 , 则 轾b, c = a, 犏 臌

镲 a a 17.若 a,b,是两个整数,b>0,设 m = 犏 , r = 镲 ,则用 m,r 表达的 b 除 a 的带余式是 睚 镲 b 镲 铪
. 18.

轾 犏 b 臌



100 ! 的标准分解中 7 的指数为 32 !
a b

.

19.有理数 (0 < a < b,(a, b) = 1) 能表示成纯循环小数的充分必要条件是 . 20.设 m = p1 1 p2 2 L pk k , p1, p2 , L pk 是 m 的互不相同的素数,则 j (m ) = . 21. 设 a,b,c,m 都 是 整 数 , ab ? ac(mod m ) , 则 当 时,
a a a

b ? c(mod m ) .
22.设 m = p1 1 p2 2 L pk k , p i 为互异的奇素数(i=1,2….,k), (a, m ) = 1 ,则同余式 x 2 ? a(mod m ) 有解时,解数为 . 23.设 m 是偶数,则模 m 有原根的充分必要条件是 24.设 a 对模 m 的指数为 t,则 a k ? 1(mod m ) 成立的充分必要条件是 25.若 a1, a 2 , L , at 是与 m 互素的 t 个整数,则 ind (a1, a 2 , L , at ) ? . .
a a a

(mod j (m ))

三、计算题。 (本大题共 4 题,第 26,27 小题各 5 分,第 28,29 小题各 7 分,共 24 分) 26.解不定方程 123x + 57y = 531的整数解. 27.求 3 对模 52 的指数.

73 / 77

《初等数论》习题解答(第三版)广东石油化工学院

ì x ? 2(mod 3) ? ? ? 28.解同余方程组 ? x ? 3(mod 4) í ? ? x ? 3(mod 5) ? ? ?
29.对哪些奇素 p,3 是模 p 的二次剩余? 四、应用题(本题 10 分) 30.今天是星期三,试求经过 t = (2002003 + 12100 )1999 天后是星期几? 五、证明题(本大题共 2 题,每小题 8 分,共 30 分) 31.求证 3 是模 17 的原根. 32.已知 383 是素数,求证 x 2 ? 219(mod 383)有解 。 2007 年 4 月广东省高等教教育育自学考试 初等数论试题答案及评分参考 一、 单项选择题 1—5BCDAB 6—10ACDBC 11—15ADCDB 二、填空题
4 5 16. 2 创3

56 创75
禳 镲 a 镲 b 镲 铪

112

133

镲 (或a = bm + br ) 17. a = b 犏 + bg 睚 犏
18.12 19. (b,10) = 1或存在一个正整数t,使得 10t ? 1(mod b)成立 。 20. ( p1 1 - p1 21(a,m)=1 22. 2k 23.m=2,4 或 2p a ,其中 a 为正整数,p 为素数 24. t k 25. inda1 + idna 2 + L + idnat 三、计算题 26.解: (123,57)= 3 531 ,所以方程有整数解。
74 / 77
a a1- 1

轾 a b 臌

)( p2 1 - p2

a

a2- 1

) L ( pk

ak

- pk

ak - 1

) 或 m (1 -

1 1 1 )(1 ) L (1 ) p1 p2 pk

《初等数论》习题解答(第三版)广东石油化工学院

化简方程得 解得

4 1+ 1y = 9

. 177

(1 分)

4 1= 1 ? 2 9 1 9= 3 6 ?

3 1
19 - (41 - 19 创2)
19 13

于是 1 = 19 - 3 ? 6

6

= 4 1? (

6) +

故 41 ? ( 6 ? 177) 知方程有特解 一般解为 ? í

19 创 16 177 = 177

x 0 = - 6 ? 177, y 0

13 177 (3 分)

ì x = - 6 ? 177 19t ? ( t = 0, 北 2, L ) 分) (5 1, ? y = 13 ? 177 41t ? ?

27、解: j(52) 24 ,24 的正因数为 = 1,2,3,4,6,8,12,24 (2 分)

32 依次检验: 31 汉 3,

9,3 汉27,4 3 3

29 mod 52) (
(4 分) (5 分)

36 ? 1 ( m o d 5 2 )
故 3 对模 52 的指数是 6 28、 解: m 1 = 3, m 2 = 4, m 3 = 5, m = 60

M 1 = 2 0 ,M 2 = 1 5M 3 = ,
' ' ' 而 M 1 = 2, M 2 = 3, M 3 = 3

12
(3 分)

故此同余组的解为

x 捍2

20 ?

2

创 15 + 3创3 3

12

3( m o d 6 0)
(7 分)

? 2 3( m o d 6 0)
29、解:显然 p ? 5 ,由二次互反律,有

骣鼢 3 珑鼢 = 珑鼢 珑鼢 p 桫 p 由于 ? ÷ = ? ÷ ? ÷ ?3 ÷ 桫 骣

3骣 p (- 1 )2 3 桫

1 p·

1 2

=

骣 p -( 3 桫

p2 1)

1

(1 分)

{

1, 如p? 1(mod3) - 1,如p 2(mod3)

75 / 77

《初等数论》习题解答(第三版)广东石油化工学院

(- 1)
所以

p- 1 2

{

1,如 p? 1(mod4) - 1,如 p 3(mod4)

(3 分)
p- 1 2 ( 1) -

骣鼢 骣 3 珑鼢 1 ? p = 珑鼢 珑鼢 p 3 桫 桫
?

{

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

或?

{

p 汉 - 1(mod 3) 2 p 汉3 - 1(mod 4)

(5 分)

酆p

1( m o d 1 2 )
(7 分)

所以只有当 p 罕 (mod 12) 时,3 是模 p 的二次剩余 四、应用题 30、解: 要求 t 模 7 的余数

200 汉 4( m od 7) , 12
由欧拉定理

5( m o d 7 )
1(mod 7) 45
4

46 汉1(mod 7), 56 4333? 6 春45
4

(2 分) (5 分) (7 分)

于是 2002003 汉 42003
1 1 2 0 0?

2(mod 7)

? 5100 5 6 165 春

5

2( m o d 7 )

于是 t ? 41999

466? 333 春41

4(mod 7)

(9 分) (10 分)

于是再过 t 天就是星期日 五 证明题

31、证:求得 j (17) = 16 = 24 ,其不同素因数只有 2

(2 分)

j (17) = 8 2
而3
j (17) 2

(4 分)

= 38 汗16

1(mod 17)

(6 分) (8 分)

所以 3 是模 17 的一个原根 32、证: 219 = 3 73 ,于是

骣1 9 骣 3 骣73 2 珑 鼢 = 珑 鼢 珑 8 3 桫3 8 3桫 3 8 3 3 鼢 桫 鼢
由二次互转律
3骣3 鼢 骣 珑 鼢 383 (- 1) 2 = 珑 鼢 珑 鼢 桫3 383 桫 1 · 3 -8 3 2 1

(1 分)

= -

骣 383 桫2
76 / 77

《初等数论》习题解答(第三版)广东石油化工学院

骣 骣1 2 = - 珑鼢 = 珑鼢 鼢 珑 鼢 桫3 = - (- 1) = 1 3 桫
骣 3鼢 骣 8 3 7 3 珑 鼢 = = 珑 鼢 珑83 桫 73 3 桫 鼢 骣1 8 珑 鼢 = 珑 鼢 珑 鼢 73 桫 鼢
1

(4 分)

骣 · 22 ÷ 3 骣 2 ? ÷= ? ÷ ? ÷ ? 73 桫 73 桫
(7 分) (8 分)

= ( - 1)
所以

2 7 38

= 1

骣 ÷ ?219 ÷ = 1 ? ?383 ÷ 桫 ÷

故同余方程 x 2 ? 219(mod 383) 有解

77 / 77



推荐相关:

福师期末考试《初等数论》复习题及参考答案

福师期末考试《初等数论》习题及参考答案本复习题页码标注所用教材为:教材名称 初等数论 单价 14.20 作者 闵嗣鹤,严士健 版本 第三版 出版社 高等教育出版社 ...


数论课程标准

第三单元同余理论 (第三章、 第四章) 质、 剩余类及完全 剩余类、 同余式...建议教材 本课程以国家规划教材——闵嗣鹤 严士健编的《初等数论》蓝本,以《初等...


初等数论教学大纲

《初等数论》教学大纲 Elementary number theory 一、本大纲适用专业数学与应用...闵嗣鹤严士健, 《初等述论》(第版), 高等教育出版社,2003 2. 主要参考...


抽屉原理

[3]闵嗣鹤,严士健.初等数论(第三版)[M].北京:高等教育出版社,2011. [4]...[8]王坤.浅谈抽屉原理及其简单应用[J].《科技信息》,2011,(18):108-109. ...


第四章选修3课程的作用和定位_2

五、文献参考 [1] 闵嗣鹤 严士健:初等数论(第三版) ,高等教育出版社,2003 [...也是解决某些数学问题的常见的思路,但是,这与我们做习题的 过程有很大的不同。...


孙子定理的应用和推广

,。。。 ' x ≡ bk mod m k 同解 ( ) ( ) ( ) 参考文献:闵嗣鹤 严士健 《初等数论》 (第三版) 《孙子算经》 秦九韶 《数书九章》 Title: The...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com