王进明初等数论习题详细解答2013.5第九版(可打印版)(5)

5.设m为正整数，整数集合｛x1,x2, …，xm｝为模m的一个完全剩余系，则 （1）当m为奇数时，x1+x2+…+xm≡0（mod m）; （2）当m为偶数时，x1+x2+…+xm≡

m（mod m） 2证：由3题知，模m的任一个完全剩余系均有xr =mkr+r，r= 0,1, 2,…, m－1。 x1+x2+…+xm≡1+2+…+m－1=

m(m?1)m(m?1),（1）当m为奇数时，≡0（mod m）; 22m(m?1)m2?2m?mmmm??m(?1)??（mod m）（2）当m为偶数时，。 222226．设m为大于2的整数，证明：{02,12,22, …, (m－1)2}一定不是模m的一个完全剩余系。

2222

(m－1)－1 = m (m－2), (m－2)－2 = m (m－4) , …,对模m两两不同余。解：由平方差公式，

7. 设m，s，t为正整数，且s >t，证明：整数集合{ x | x= u+mstv，0?u?mst－1 , 0?v?

mt－1}为模ms的一个完全剩余系。

－－

证：首先确定集合元素的u有mst 种取法，而u每次取定之后要加不同的mstv，v有mt 种

－

取法，因此元素总数为mst×mt = ms。然后可以验证题设的集合元素就是0到ms－1的ms个数，它们构成ms的非负最小完全剩余系。证毕。

－

－

8. 计算欧拉函数值?(m)：?(1236)； ?(1218)； ?(2001)； ?(4200) 解：?(1236)= ?(12×103), 103是质数，因此?(1236)=(22-2)(3－1)(103－1)=408.

?(1218)= ?(6×203) = ?(2×3×7×29)= 2×6×28=336 ?(2001)= (3－1)(23－1) (29-1)=1122 ?(4200)= ?(23×3×52×7)= (23-22)(3－1)( 52－5) (7－1)= 960

9. 设为大于2的整数，证明?(m)为偶数。

证：若m的质因数至少有一奇数，由公式，可知?(m)=

?p?p?1?为偶数。若m的

?i?1iii?1k质因数一个奇数也没有，而m大于2，必有m =2,??1，此时?(m)=2???1,也是偶数。

或证：设 m = p1α1p2α2… pkαk，∵ m >2，∴ 至少存在 i，αi> 1或存在 j，pj是奇数， ∴ p1α1- p1α1 -1，…，pkαk- pkαk-1中至少有一个为偶数，知 φ（m）必为偶数中

又证：若有?i?1,无论pi为奇为偶,有pi?i?pi?i?1=pi?i?1?pi?1?是偶数.所有的?i?1,则必有一个pi为奇数，因为如果m是质数，大于2的质数是奇数，?(m)?m?1是偶数；如果m是合数，pi中最多只有一个是2,那么至少有一个为奇数， 这时?(m)???pi?1?是偶数.

i?1k10. 11(略)

附）广西师范大学赵继源主编的《初等数论》将完全剩余系与简化剩余系分开在2-2,2-3

21

两节, 下面是广西师范大学赵继源主编的《初等数论》习题2-3中的部分题目 1.乘幂 20，21，22，?，29能否构成模 11的一个简化剩余系？ 解：i > j时，2－2=2(2

i

j

j

i－j

－1), 11?2, 通过验证可知，对任何i，j，也有11? (2

ji－j

－1)，

φ (11) = 10，而20，21，22，?，29为10个不同的整数，所以它们构成模 11的一个简化剩

余系

2.列表求出模 m 为 10，11，12，…，18等值时的最小简化剩余系及相应的φ (m). m 10 11 12 13 14 15 16 17 18 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 5 6 6 6 最 小 简 化 剩 余 系 7 7 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9 9 10 11 11 11 11 11 13 13 13 15 17 φ (m) 4 10 4 12 6 8 8 16 6 10 11 12 13 14 10 11 12 13 14 15 16 3.证明定理 2.7：简化剩余系的充分必要条件。 证明:（必要性）∵ x1，x2，…，xk是模 m 的简化剩余系，

∴ k=φ(m)，且当 i ≠ j时，xi?，（xi，m）=1，i = 1，2，…，φ(m). ?xj（mod m）（充分性）k=φ（m），∴ x1，x2，…，xk共有φ（m）个. 又 xi?，（i ≠ j，1?i，j? k），（xi，m）=1（i=1，2，…，k）， ?xj（mod m）

∴ x1，x2，…，xk各属于φ(m) 个不同的且与 m 互质的剩余类， ∴ x1，x2，…，xk是模 m 的简化剩余系. 4. 验证：（1）8，16，24，32，40，48是模 7的简化剩余系；

（2）11，13，77，99是模 10的简化剩余系. 解：（1）∵（4，7）=1，可化为2，4，6，8，5，12，又5≡12（mod 7），

∴ 8，16，24，32，40，48不是模 7的简化剩余系。

（2）10的最小简化剩余系是1, 3, 7, 9。11，13，77，99分别与1, 3, 7, 9关于模10同余。∴ 11，13，77，99是模 10的简化剩余系. 5. 当 m 取下列各值时，计算φ（m）的值 .

25，32，40，48，60，120，100，200，4200，9450.

答案：φ（25）= 20，φ（32）=16，φ（40）=16，φ（48）= 16，φ（60）=16，φ（120）= 32，

φ（100）= 40，φ（200）= 80，φ（4200）= 960，φ（9450）= 2160.

6. 若φ（m）是奇数，试求 m 的值. 解：(参看下一题) m = 1或 m =2. 7. 当 m >2时，证明φ（m）是偶数 . 8. 试证：使φ(m) =14的数 m 不存在.

证：φ(m) =14=2×7= p1α1 -1…pkαk-1 (p1－1)…(pk－1)，2,7是质数，所以必有p1=2，p1=7，这是不可能的。

9. 已知φ(m) = 4，求 m .

解：设m = p1α1p2α2… pkαk，由φ(m)= (p1α1- p1α1 -1)…(pkαk- pkαk-1)，φ(m) = 4=4×1=22，得 m = 5，φ(m) =5－1= 4，或 m =8=23，φ(m) = 22或 m = 10=5×2，φ(m) =4×1，或 m =12. 10. 如果 n =2m，（2，m）=1，那么φ（n）= φ（m）.

22

解 ∵（2，m）= 1，∴ φ（n）=φ（2m）=φ（2）φ（m）=φ（m）. 11. 若 m 是奇数，则φ（4m）=2φ（m）.

证：∵ m 是奇数，∴（4，m）= 1，则φ（4m）=φ（4）φ（m）.

∵ φ（4）= 2，∴ φ（4m）=2φ（m）.

12.（1）分母是正整数 n 的既约真分数的个数是多少？为什么？ （2）分母不大于 n 的既约真分数的个数是多少？为什么？ 解：（1）φ（n）. （2）φ（2）+φ（3）+ ? +φ（n）.

习题 2-3

1.举例说明欧拉定理中（a，m）=1是不可缺少的条件 . 解：当 a= 2，m =4时，?(4) =2，此时 22≡0（mod 4），可见（a，m）= 1是欧拉定理的不可缺少的条件.

2. 设 p，q是两个大于 3的质数，求证：p2≡ q2（mod 24）. 证：24=3×8，（3，8）= 1. 由条件，( p，3 ) = ( q，3 ) = 1，由费尔马小定理有 p2≡1（mod 3）， q2≡1（mod3）. ∴ p2 ≡ q2（mod 3）.

又 ∵ p，q 必为奇数，设p =2k+1，p2=4k(k +1)+1, 有p2≡1（mod 8）， 类似可得q2≡1（mod8）.∴ p2 ≡ q2（mod 8）. ∴ p2 ≡ q2（mod 24）. 3.设 p是大于 5的质数，求证：p4≡1（mod 240）.

2

证： 240 = 3×5×16，由条件，(p，3) = (p，5) = 1，∴ p4≡1（mod5），p4≡（p2）≡1（mod3）. 又 p为奇质数，从而 2 |（p2+ 1），8 |（p2-1），∴16 |（p4-1），即 p4≡1（mod 16）. 而（3，5）=（3，16）=（5，16）= 1. ∴ p4≡1（mod 240）. 4. 如果今天是星期一，从今天起再过1010天是星期几？

解：由欧拉定理，106≡1 (mod 7)，由普通除法知1010被6除余4, 即1010=6k+4, k∈Z, 故

101010=106k?4??106??64?64,而62≡1 (mod 7), ∴64≡1（mod 7）再过1010天是星期二.

5. 求下列各题的非负最小余数：（1）84965除以13； （2）541347除以17；

（3）477385除以19； （4）7891432除以18； （5）(127156+34)28除以111. 答案：（1）8. （2）10. （3）16. （4）1. （5）70. 解：（1）84965除以13；（13，8）=1, ∴ 812≡1（mod 13），84965=(812)413×89≡1×(-1)4 ×8（mod 13） 或解：82≡－1（mod 13），84965=(82)2482×8 ≡ (-1) 2482 ×8 ≡ 8（mod 13）。

x6. 已知 a =18，m =77，求使 a≡1（mod m）成立的最小自然数 x. 答案：x=30. 1860≡1 (mod 77) ,且满足要求的最小自然数 x必为60 的?(77)??11?1??7?1??60,由定理知，

正约数：1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 由验算可知x=30. 事实上, 由欧拉定理知，

186≡1（mod 7），1810≡1（mod 11）,6与10的最小公倍数是30,故有1860≡1 (mod 77) ,而 182≡16 (mod 77) , 183≡57 (mod 77) , 182≡162≡ 25(mod 77) , 185≡57×16≡65 (mod 77) , 186≡(183) 2≡572 (mod 77) , 1810≡185×182≡65×16≡1040≡39 (mod 77) ,(略) 7. 设（m，n）=1，证明：m证：∵(m, n)= 1，∴n对称可得 m

?(n)?(m)10k10?(n)+ n

?(m)≡1 (mod mn).

?(n)≡1（mod m），而 m≡ 0（mod m），∴ m

?(n)?(n)+n

?(m)≡ 1（mod m）.

+n

?(m)≡ 1 (mod n). 由同余性质可得 m+n

?(m)≡ 1（mod mn）.

23

广西师大本其他题目： 5.已知 p是质数，（a，p）=1，求证：（1）当 a 是奇数时，ap-1+(p－1)a ≡ 0（mod p）； （2）当 a 是偶数时，ap-1－(p－1)a ≡ 0（mod p）. 证：（1）由 p 是 质 数，（a，p）= 1，a 为 奇 数，有 ap-1≡ 1（mod p）.

(p－1)a ≡－1（mod p），∴ ap-1+ (p－1)a≡ 1－1≡ 0（mod p）. （2）由条件，ap-1≡1（mod p）, (p－1)a≡1（mod p），∴ap-1－(p－1)

?(n)≡1－1≡0（mod p）.

6. 已知 p，q 是 两 相 异 的 质 数，且 ap-1≡1（mod q），aq-1≡1（mod p）， 求证：apq≡ a（mod pq）. 证：∵ ap ≡ a（mod p），∴ apq ≡ (ap)q ≡ aq ≡ a（mod p）；同理，apq ≡ (aq)p ≡ ap ≡ a（mod q），

pq

而（p，q）= 1，故 a≡ a（mod pq）. 7. 如果（a，m）=1，x≡ ba

?(m)?1（mod m），那么 ax≡ b（mod m）.

8. 设 A 是十进制数 44444444的各位数字之和，B 又是 A 的各位数字之和，求 B 的各位

数字之和 .

9. 当 x∈Z 时，求证：（1）2730 | x13- x；（2）24 | x（x+2）（25x2-1）. 解答：7. ∵ x≡ba

?(m)?1(mod m)，∴ ax≡ aba

?(m)?1≡ a

?(m)b (mod m). ∵ (a，m) = 1，a

?(m)= 1

(mod m)，∴ ax≡ b（mod m）.

8. 设 B 的各位数字之和为 C，∵ lg44444444= 4444lg4444 < 4444×4= 17776，即44444444 的位数小于17776，∴ A ? 9×17776 = 159984，B < 1 + 9×5 = 46，C ? 4 + 6 = 10. 又 ∵（7，9）= 1，?(9) = 6，4444= 6×740+4，44444444 ≡ 7 4444 ≡ 74 ≡ (－2)4 ≡ 7（mod 9），∴ B 的各位数字之和为 7.

9.（1）∵ 2730=2×3× 5× 7× 13，2，3，5，7，13两两互质，x13- x= x（x12- 1）， ∴当 2 | x或 2 | x时都有 x（x12-1）≡ 0（mod 2），x（x12- 1）≡ 0（mod 13）. 又 ∵x13-x= x（x6- 1）（x6+ 1），∴ 当 7 | x或 7 | x时都有 x（x6- 1）（x6+ 1）≡ 0（mod 7）.而x13- x= x（x4- 1）（x8+ x4+ 1），∴ 当 5 | x或 5 | x时，都有 x（x4-1）（x8+ x4+ 1）≡ 0（mod5）.又 x13- x= x（x2-1）（x2+ 1）（x8+ x4+ 1），∴ 当 3 | x或 3 | x时，都有x（x2-1）（x2+ 1）（x8+ x4+ 1）≡ 0（mod3）. ∴ 2730 | x13- x. （2）解法一，同上。解法二： x（x+2）（25x2-1）= 24 x3（x+2）+ x（x+2）（x2-1）, x（x+2）（x2-1）= x（x-1）（x+1）（x+2），四个连续自然数的乘积必能被4!=24整除，证得。10. 设质数 p>3，x∈Z，试证：6p | xp- x.

?99. 11. p是不等于 2和 5的质数，k是自然数，证明：p|99??????p?1?p个9解答：10. ∵质数 p> 3，∴ （6，p）=1，xp- x= x（xp-1- 1）≡ 0（mod p）. 又 p- 1是偶数，

∴x（xp-1-1）≡ x（x2- 1）?（mod p）. 于是，当 2 | x或 2 | x 时，x（x2- 1）≡ 0（mod 2）；当 3 | x或 3 | x时，x（x2-1）≡ 0（mod 3）.故 x（xp-1- 1）≡ 0（mod 6）.从而6 | p（xp- x）.

?99?1011. 99??????p?1?k个9?p?1?k?1. 由条件，（10，p）= 1，∴ 10p-1≡ 1（mod p）.

?99. ∴ （10p-1）k≡ 1（mod p）. ∴ p|99??????p?1?p个9(王进明与赵继源本三、四章编排顺序相反) 习题3-1(P157)

24

1．试写出三个模数是20的一次同余方程，分别使它有唯一解，无解，有四个解。 解：7x≡50（mod 20）有唯一解，8x+5≡0（mod 20）无解， 4 x≡0（mod 20）有四个解。 2. 下列同余方程是否有解？为什么？如果有解，不出其所有解。

（1）7x+4≡0（mod 25）；（2）12x+1≡0（mod 9）；（3）34x≡1（mod 51）； （4）42x≡8（mod 138）；（5）174x≡65（mod 1309）.

解：（1）（7, 25）=1, 有唯一解。7x≡-4（mod 25）由欧拉定理，?(25)=20,故x≡719×(-4) ≡3 （mod 25）,化简过程：72≡-1（mod 25）故719×(-4) ≡718×7 (-4) ≡(-1)×7 (-4) ≡28≡3 （mod 25）. 用同余变形法解：x??4?25?3. 7（2）（12, 9）=3?1, 同余方程无解；（3）（34，51）=17?1, 同余方程无解；

（4）138=2×3×23,（42,138）=6不能整除8, 同余方程无解；

（5）174=2×3×29, 1309=7×11×17,( 174, 1309)=1.此题数字大，应该用大衍求一术。

1740130907121817419191183108023183 862n q P 1 0 1 2 7 7 3 1 8 4 1 15 5 10 158 6 2 331 7 1 489 x≡489×65=31785≡369（mod 1309） 3.求下列一次同余方程的所有解：（1）3x≡1（mod 17）；（2）1215x≡560（mod 2755）； （3）47x≡89（mod 111）；（4）38x≡6（mod 106）；（5）11x≡6（mod 13）. （6）3x≡5（mod 29）；（7）5x≡6（mod 24）（8）66x≡14（mod 74）； 解：（1）（3, 17）=1, 有唯一解。由3x≡1+17（mod 17）得，x≡6（mod 17）；

（2）（1215，2755）=5(243,551)= 5(35, 19×29), 方程恰有5解，先解243x≡112（mod 551）: 这个系数相当大，故应该用大衍求一术。辗转相除过程的竖式略，由如下表格

n q P 1 0 1 2 2 2 3 3 7 4 1 9 5 2 25 6 1 34 7 4 161 8 1 195 9 1 356

知x≡112×356≡200（mod 551）, 故原方程有解x≡200751, 1302,1853和2404（mod 2755）. （3）(47，111)=1,方程恰有一解x≡89（mod 111）；由欧拉定理，?(111)=72,故x≡4771×(89) ≡94（mod 111）,用同余变形法解：x?89?11120025136???????17（mod 111）

47?111?6488（4）38x≡6（mod 106）；先解19x≡3（mod 53）. 用同余变形法解有

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库王进明初等数论习题详细解答2013.5第九版(可打印版)(5)在线全文阅读。