kl800.com省心范文网

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


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

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

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

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 ) ( n? 2 ) ? n( ? 1 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 q ?1 q ?1 综上所述,存在性 , t ? a ? bs ? a ? b ,则同样有 t ? 2 , 2 2

若 b ? 0 ,则令 s ? ?

得证. 下证唯一性 当 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.应用§ 1 习题 4 证明任意两整数的最大公因数存在,并说明其求法,试用你的所说的求 法及辗转相除法实际算出(76501,9719) . 解:有§ 1 习题 4 知:

?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§ 1 习题 4 知在(1)式中有

0 ? rn?1 ? rn ?

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

?1 ?

b n , ?2 ? b, 2n

?n ? l o g 2b?

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 是任意两个正整数,且
?n ?1 ?2 a ? p1 ? p2 ?? ? pn , ? i ? 0 , i ? 1, 2,?, k ,

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

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

.

∴ ∴ 推广

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

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

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



j ? 1, 2,? , k

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

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

其中 p1, p2, ?, pk 是互不相同的素数,?i,?i(1 ? i ? k)都是非负整数,有
?k ?1 (a, b) ? p1?1 p2 ? pk , ?i ? min{? i , ? i }, 1 ? i ? k, ?1 [a, b] ? p1?1 p2 ? 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 ,
n

2k

2k l

∴ 2n ? 1 为合数矛盾,故n一定为2的方幂. § 5 函数[x],{x}及其在数论中的一个应用 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 ?
? 30 ? ? 30 ? ? 30 ?

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

?13 ? ?

? 30 ? ? 30 ? ? 30 ? ? 30 ? ? ? 2 ? ? ? ? 2 ? 0 ? 2 , ?13 ? ? ? ? ? 2 ? ? ? ? 2 ? 0 ? 2 ? ? 13 ? ?13 ? ? 13 ? ?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 ? s r , ? s ?1
当 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 x? 2 5 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
故一般解为

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

)

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? 或 ? ? ?1 ? ? ? ab ? ? ab ? ?N?

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

? 0, 0 ?

而 ? ??0 ? ab ?

?N?

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

? 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, 故原方程有整数解 (x 0 , y0) , 一般解是 要求 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 = ?2abd, n = ?(a2 ? b2)d, m = ?(a2 ? b2)d 或 l = ?(a2 ? b2)d, m = ?2abd, m = ?(a2 ? b2)d, 由 此 得 (x, y) = ?

(

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

代 入 方 程 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? , d / zy d ?z /3 ? 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. 解 不 定 方 程 : x2 ? 3y2 = z2, x > 0, y > 0, z > 0, (x, y ) = 1。 解 : 设 (z ? x, z ? x) = d, 易 知 d = 1 或 2。 由 (z ? x)(z ? x) = 3y2 得 z ? x = 3da2, 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 = |b2 ? 3a2|,y = 2ab,z = b2 ? 3a2,

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

| b, a, b 一 奇 一 偶 。 反 之 , 易 验 证 (ⅰ)或 (ⅱ)是 原 a > 0, b > 0, (a, b ) = 1, 3 ?
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 4
2 2 4 4 2

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

2

4

4

2

b

2

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

2

2

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

原方程正整数的解有:

? a , ?a ? , ? ?a ,0, ?a ? ? ?4ab(a ? b ), ?(a ? b ? 6a b ), ?(a ? b ) ? , ?0, ? ?(a ? b ? 6a b ), ?4ab(a ? b ), ?(a ? b )? ,
0, 0? , ? 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 是 x2 ? y2 = z4 的 满 足 (x, y) = 1, 2?x 的 正 整 数 解 , 则 x = 2ab, y = a2 ? b2, z2 = a2 ? b2, a > b > 0, (a, b) = 1, a, b 一 奇 一 偶 , 再 由 z2 = a2 ? b2 得 a = 2uv, b = u2 ? v2, z = u2 ? v2 或 a = u2 ? v2, b = 2uv, z = u2 ? v2, u > v > 0, (u, v) = 1, u, v 一 奇 一 偶 , 于 是 得 x = 4uv(u2 ? v2), y = |u4 ? v4 ? 6u2v2|, z = u2 ? v2, 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 则

? ? ?
,?,

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

? ?? ?
1,?,? k

1 ,?,? k

?k ?1 y1 ? yk (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 , 进一步,则
?k ?k ?1 ?1 ??1?? k x1 ? xk ? B?? ?? k y1 ? yk (mod m)
1

a b m ? (mod ), b d d

最后据性质丁,可得:

? ? ?
,?,

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

? ?? ?
1,?,? k

1 ,?,? k

?k ?1 y1 ? yk (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?
2

证明: (数学归纳法)设 a ? 2m ? 1 (1) n ? 1 时, a 2 ? ? 2m ? 1? ? 4m ? m ? 1? ? 1 ? 1? mod 8 ? , 结论成立。 (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
? ? 2k ? 2 t ? ? 2 ? 2k ? 2 ? t
2
k? 4 ? t2 ? 2 2 ? t ? 2k ? 3

?

k

??

k

? ?

k

??

k

?

? t ? 2k ?3 ? t ? 2k ?1 ? 1?
3 ? 0 ? m o dk ? 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 2 ? 2 ? ? M k xk
通过模 m1m2 ? mk ? m 的完全剩余系,其中 m ? mi M i , i ? 1, 2,?, k 证明: (数学归纳法) (1) 根据本节定理 3,知 k ? 2 时,结论成立。

, (2) 设 对 整 数 k ? 1 , 结 论 成 立 , 即 若 m1 , m2?
' ' x1 ,x s ' ? M1 x' ? 1 ,x2 , ? 1 M x2 ?? 2 ? M k ? xk ? ,当 1

, 两 两 互 质 , 令 km ? 1

k1 ?

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

余系时, s ' 必过模

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 个值,且若 ? ? m1 x2 ? (mod m1m2 ) ? m1 ( x2 ? x2 ? ) ? x1 ? ? x1 (mod m1m2 ) x1 ? m1 x2 ? x1

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

? ? x1 x1 (mod m2 ) m1

? , x2 ? x2 ? ,即 k ? 2 时结论成立; ? x1 ? x1
(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

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

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

?(mod m1 ) ; x2 ? m2 x3 ? ? ? m2 ? mk ?1 xk ? x1 ? x1 ? ? m2 x ?3 ? ?mod m ? x2 ? ? m? ? 2 km ? 1 k(x 2 ?(mod m1 ) , x2 ? x2 ? (mod m2 ) ,…, xk ? xk ? (mod mk ) ? x1 ? x1 ? , x2 ? x2 ? ,…, xk ? xk ?。 ? x1 ? x1
所以 x1 ? m1 x2 ? ? ? m1m2 ? mk ?1 xk 过模 m1m2 ? mk 的完全剩余系。 3.简化剩余系与欧拉函数 1.证明定理 2:若 a1 , a2 ,?, a? ( m) 是 ? (m) 与 m 互质的整数, 并且两 ? 对模 m 不同余,则 a1 , a2 ,? , a? ( m ) 是模 m 的一个简化剩余系。 证明:
k

m )

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

?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 ? ? ?? 。 ? 2 ? ? m ? ? a? ? 1

? a? ?

1

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

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

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

展布在 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 ? 2 ? 2 ? ? M k?k
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 2? ? ha p

?

mod 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 ?

《初等数论》习题解答(第三版)
?1 ?s 进一步,设 m ? p1 ,则 ? ps

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

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

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

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

?

?

? p?

? ?

? 1? mod p? ? .
,? i

? a, m ? ? 1


i



? a, ?p? ?
i

?i

1 ?

?

1

, s ?2

a,

? pi?i

? ? ? 1 mod ? . pi?

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 ? 15
4 ?4 x ? ?20 ? mod15 ?

1 5x ? x ? ? 2 ? 0 mod ?15
? 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 .证明
? (m ? ) 1 x? ba ( m o dm )

是同余式 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 )
) 1 ? a? ( m ? ? 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 知 方 程 ax ? 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) ? ? 1(mod 5) 21M 2 ? ? 1(mod 5) M1M1? ? 1(mod 3) 即 M 2 ? ? 1(mod 7) 15M 3 ? ? 1(mod 7) M3
根据孙子定理方程组的解是

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; ? ? 1(mod 72)得M 2 ? ? ?1; 由 11 ?13M 2 ? ? 1(mod13)得M 3 ? ? ?1; 11 ? 72 M 3
故原方程组的解是 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 ? , 1 ( m o dm 1 )x

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 m ) 3 (m m 1, m2m ,1m m m1m2 3 ) , m3 ) ? 1 2 ? (m1 , m2 ) (m1 , m2 ) (m1 , m2 )

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

m1)m ( 3 m2)m3

? (m12 , m1 m3 , m1 m2, m2 m) , m3) 3 ( m2
2 2 2 ? (m12 m2 , m1 m ,3 m2 2m ,3 2m1 m , 33 ,m m mm 2, m2 m 11 2 )3

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


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

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

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

m ,3

).
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 ) 则由§ 1 定理,知方程 m1 y ? b2 ? b1 (mod m2 ) 必有解, 设其解为 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 3 2 ? ? 4 x ? 3 x ? 6 x ? 2 ? 0(mod 3 ) 故原同余式等价于 ? 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, § 4.质数模的同余式 补充例子: 1. 解 同 余 方 程 : (ⅰ) (ⅱ)

(mod 225)

22, 176, 122

(mod 225).

3 x 1 1 ? 2 x 8 ? 5 x 4 ? 1 ? 0 ( m od 7 ) ; 4x20 ? 3x12 ? 2x7 ? 3x ? 2 ? 0 (mod 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 ) 是 否 有 六 个 解 ? 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)等 价 于 x3 ? 3x2 ? 4x ? 3 ? 0 (mod 5),

解 : (ⅰ)

又 x 5 ? x = ( x 3 ? 3 x 2 ? 4 x ? 3) ( x 2 ? 3 x ? 5 ) + ( 6 x 2 ? 1 2 x ? 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?) n 个 解 , 而 x p ?1 ? 1 ? 0

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

x p ?1 ? a ?0

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

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 是 正 整 数 , 又 设 x0k ? a (mod m), 证 明 同 余 方 程 xk ? a(mod 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 ? (b 2 ? 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 10 ? 2 6 11 , 2 ? 10, 122 ? 33, 132 ? 21, 142 ? 11, 152 ? 3, 162 ? 34, 17 2 ? 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

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

(ii)


p ?1 2

a, b















a

p ?1 2

? 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

?

?

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

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

?

2

? 2? a? ? ? ,Q ?
?

? 2

?a

?

2 a

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

?1

? mo p 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 ? ?1 2 ? ?2 ? 2? ? C? 2 a ? C? 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? ? 1 ?2 ?? 2 m?? m o d 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 ? mod 5 ?63 ? ii ? x 2 ? 6 8 0 ? mod 7 ?69 ? iii ? x 2 ? 5 0 3 ? m o d 1 ?0 1 3
解: ? i ? ?

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

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

? ii ? ? ?

? iii ? ? ?

2、求出以 ?2 为平方剩余的质数的一般表达式;以 ?2 为平方非剩余的质数的一般表达式。
p ?1 p ?1 ? ?2 ? ? ?1 ? ? 2 ? ? 2 8 ? ? ? 1 解: ? ? ? ? ? ?? ? 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) (§ 3T h 1 推证)
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、 判断§ 3 习题 1 所列各同余式是否有解。 略 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 ? ? 3149 ? ? ? ? 1 ,故解数为 2. ? 5987 ?

? ii ?
3.

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

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

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

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)
由§ 3 定理 1 的推论知,2 是模 p 的平方剩余,即
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. 解同余式

25 )? ? i ? x2 ? 5 9 ( m o d 1 , ? 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 )
得出

(22 ? 2 t25 2 ? )

100 59(mod 25 ) t2 ? ?50(mod125) ,1 即
故 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) 的一切解的方法。 证明: (ⅰ)显然
?k ?1 (ⅱ)记 m ? 2? p1 ? pk

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(mod 8) 的解为 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

? 1 (mod 292)知 2 是 模 293 的 原 根 ; = 228 = 228 ?
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 2 y ? 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

? ( x0qi )

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 )


Ind g ?? g'

t

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

? qt (g' ) ? g (mom 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§ 4 Th2.3 的证明可知, 的指数,从而 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 m d ,)
故 ?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 ? g a

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

58 / 77

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

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

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

? (a) 是

d 2 跑过 x2 的全部因子, 证明: 首先我们证明: 设 ( x1 , x2 ) ? 1 , 若 d1 跑过 x1 的全部因子, 则 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 ,得 d1d2 ? d1'd2' ,反之任给 d x1x2 ,由于 ( 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, ? ) ? 2 x
d
1

x

2

x

?? f ( ?d )
1

f 2(
2

d

) d

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 , 则

( ) ? ?( f) a , 即 f1 又 F1 f (1)? f (1)f (1) ( ) 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

?

a m , b n ab ? mn

?

f(ab )?

f( m n )

?

a m , b n ab ? mn

?

f ( a) f ( b? )

f(mn )

=

? f (a)? f (b) ? f (m) f (n) ? f (mn)
am 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

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

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

?n?

dn

? f ?d ? ? ? f ? ? ? ? ? ? ? ? g ?c? ?d ? ? cd ?
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 。 ②若 ( 是定义在闭区间 ? 0,1? 上的函数,n 正整数,记 f x)
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 的一个约数.每 , ,? , , b n n n
一个这样形式的分数都可得到一次也好一次. ③ 记

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

m

?2 (m)
m2

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

记 F * ( m) ?

x ( ) ? x ?1 m

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 ? ( x ) ? ? ? (x )? ? ? x ( x ) ? 2x m 3 x m x 6 x m

由本节推论 2.2 2.3,即有:

? 2 (m) m2? (m) ?

1 3

1 ? (1 ? p) 6 pn

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

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 ( ) ? ? ? w( n ) ? F ( ) ? ? n mn ? n ?1 n ?1 ? m ?1 ? ?

? x?

? x?

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

? x?

? ? x x ) ? ? ? w(? x?) ? F ( ) (? 2 ) F( 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 nk ?

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

63 / 77

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

初等数论试卷 一、 单项选择题: (1 分/题× 20 题=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 ? ? _________________________________。 三.简答题: (5 分/题× 4 题=20 分) 31.命题“任意奇数的平方减 1 是 8 的倍数”对吗?说明理由。 32.“若 a, m ? ? 1 , x 通过模 m 的简化剩余系,则 ax 也通过模 m 的简化剩余系”这命题是否正 确?正确请证明,不正确请举反例。 33.求模 17 的简化剩余系中平方剩余与平方非剩余。
?k ?1 ? 2 p2 ? pk 34.设 a ? p1 为 a 的标准分解式,记 S ? a ? 为 a 的正因数的和,? ? a ? 为 a 的正因数的

?

?

个数,则 S ? a ? =?

? ? a ? =? 为什么?

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

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

x ? ?(a 2 ? 2b 2 ) 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 ? ?

??
i ?1

k

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× 6× 7=210 有唯一解,分别解同余方程:

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

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

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

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


2

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

? z ? x z? , ? 2 ? 2

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

?x ? ?x ?

而错误!未找到引用源。 ,所以( 由书中引理,我们可假设

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

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

z?x 2 =b 2
z= a 2 + b 2 ,y=2 ab

显然 a >b, ( a ,b)=1, 于是

因子为奇数,所以 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 犏,

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

B. 犏,

轾 ab a b = 犏 d d d 臌 轾 ab a b = 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 , bd = d D. 轾 犏 臌 -a = aB. 轾 犏 臌
D.
71 / 77

- a = 轾 - a + 1 A. 轾 犏 犏 臌 臌 -a = 轾 -a C. 轾 犏 犏 臌 臌
6.下列不定方程中,有整数解的是( )

{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

a, b, c = 133 , 则 轾 犏 臌

镲 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

镲 17. a = b 犏 + bg 睚 (或a = bm + br ) 犏
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=

. 7 17

(1 分)

4 1= 1 ? 9 2 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, 北 (5 分) 1, 2, L ) ? y = 13 ? 177 41 t ? ?

27、解: j(52) = 24 ,24 的正因数为 1,2,3,4,6,8,12,24 (2 分)

32 依次检验: 31 汉 3,

9, 33 汉27, 34

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

创 3 15 + 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 p 珑 鼢 = 1? 珑鼢 鼢 珑 p鼢 3 桫 桫
?

{

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

或?

{

p汉 2 - 1(mod 3) 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
100 12 ?

2(mod 7)

? 6 16 5100 5 春 5

5

2( m o d 7 )

于是 t ? 41999

466? 333 春41

4(mod 7)

(9 分) (10 分) (2 分)

于是再过 t 天就是星期日 五 证明题

31、证:求得 j (17) = 16 = 24 ,其不同素因数只有 2

j (17) = 8 2
而3
j (17) 2

(4 分)

= 38 汗16

1(mod 17)

(6 分) (8 分)

所以 3 是模 17 的一个原根 32、证: 219 = 3 73 ,于是

骣 21 9 骣 3 骣73 珑 鼢 = 珑 鼢 鼢 鼢 桫3 8 3桫 3 8 3 珑 383 桫
由二次互转律
3骣3 鼢 骣 383 珑 鼢 = (- 1) 2 珑 珑 鼢 桫3 383 鼢 桫 1 · 3 -8 3 2 1

(1 分)

= -

骣 383 桫2
76 / 77

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

骣 2鼢 骣 - 1 鼢 = - 珑 = = - (- 1) = 1 珑 鼢 珑 鼢 3 桫 桫3
骣 骣 73 383 珑 鼢 = = 珑 鼢 鼢 鼢 桫 73 珑 383 桫 骣1 8 珑 鼢 = 珑 鼢 鼢 珑 鼢 73 桫
1

(4 分)

骣 · 22 ÷ 3 骣 2 ? ÷ = ? ÷ ? ÷3 桫 ? 7 73 桫
(7 分) (8 分)

= ( - 1)
所以

2 73 8

= 1

骣 219 ÷ ? ÷= 1 ? ? ÷ 383 ÷ 桫

故同余方程 x 2 ? 219(mod 383) 有解

77 / 77


初等数论课后习题答案

《初等数论(闵嗣鹤)》习题解答 2010 修改版 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...

《初等数论(闵嗣鹤、严士健)》课后习题解答

| a, d ?? | b ,所以 ( a, b) 的 2 / 57 《初等数论》习题解答(第三版)广东石油化工学院 因数都是 a , b 的公因数,从而 a , b 的公因数与 ...

初等数论练习题答案

初等数论练习题答案_教育学_高等教育_教育专区。初等数论练习题答案 原点教育培训...x ≡ 29(mod (2)a≡2010(mod9) (3)a 的十进位表示的各位数字之和可被...

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

广西师范大学 赵继源主编的《初等数论》习题 1—1 中的部分题目 3 .已知 a ...试除时,用数的整除特征考虑:2,3,5 显然不能整除它,由上 节第 8 题结论,...

初等数论 第三版(闵嗣鹤)习题解答

初等数论 第三版(闵嗣鹤)习题解答_理学_高等教育_教育专区。湛江师范学院(岭南师范学院)数学专业 初等数论 课后答案(完整版)《初等数论(闵嗣鹤)》习题解答 2010 修...

02013初等数论练习题及答案

02013初等数论练习题答案_理学_高等教育_教育专区。本人认真做过的初等数论习题...(2010)=528。 20 2、数 C100 的标准分解式中,质因数 7 的指数是_3。 C...

王慧兴初等数论各章习题参考解答

王慧兴初等数论各章习题参考解答_理学_高等教育_教育专区。王慧兴《初等数论》各章习题参考解答 第一章习题参考解答 1.解:因为 25 的最小倍数是 100,9 的最小...

《初等数论》习题解答

初等数论答案 55页 免费 初等数论(第三版)+闵嗣鹤... 11页 免费 初等数论(...《初等数论》习题初等数论》第1章第 1 节 1. 证明定理 1。 2. 证明:...

初等数论练习题答案

初等数论练习题答案_政史地_高中教育_教育专区。初等数论练习题答案 信阳职业...(3)a 的十进位表示的各位数字之和可被 9 整除 (4)划去 a 的十进位表示...

初等数论第2版习题答案

《初等数论(闵嗣鹤、严士健... 77页 免费 高等几何课后答案(第三版) 17页 1...第一章 §1 1 证明: a1 , a 2 L , a n 都是 m 的倍数。 ∴ 存在...