发布时间 : 星期六 文章王进明 初等数论 习题解答更新完毕开始阅读
（2）原式化为?x??x(x??x?)?0，整理后再由一元二次方程求根公式得 ?x??25?15?15?1x，与相乘后的积为整数，只能是x?。 2225. 15< x+ y<16.
6. 25！=222×310× 56× 73×112×13×17×19×23. 由定理1.29公式求出各个质数的指数。 7.（1）??199?1??199?2???????97??97??199?96??? ??97?5?1??5?2?5?96??解： 原式??2?1? ?2?2???2?96???????97??97?97????5?1??5?2??5?96??2?1?2?2??2?96???????97????97???97??
?5?1??5?19??5?20??9312???????????979797???????5?78??5?96????????97???97??=9312+0+…+0+19+40+57+76=9504.
（2）考虑1??5?38??5?39????????9797?????5?58????97??11?2232?111?1??200821?22?3?1
2007?2008?11??11??1??????????12??23?1??1?????20072008??1?=1.
20082???1?1?8. 1373个 .
9. 14人 . 10. 49盏 .
11?2232?1111?1??2。从而?2??22?23200822008?x??1??211. 高中时我们已知x?1?x?1???2x?1?x?1,
?2x?1?x??1时,?x???2,??2?x??1；
?1?x?1时,?x??2x,即??x??0??1?x?0,即?2?2x?0,而2x?Z,x?1时,?x??2,?2?x?3.?x??,x?0;
∴ －2≤ x<－1或 2≤ x<3或 x= －1/2 或 x= 0.
12. 解： 等式左边为73个数相加,而546?73?7?35.?7?x?8,
12
且可知等式左边从右向左有且只有满足x?由等式左边从右向左第35项x?y?8 10057?8移项得x?7.43. 100??100x??743.
习题2-1
5. 若69, 90和125关于某数 d 同余, 证明对于d, 81与 4同余. 证明：由69和90关于 d 同余, d | 90－ 69, d | 21,
90和125关于某数 d 同余, d | 125－ 90, d | 35, ∴ d | (21, 35) , d=1或7. 22
9. 由 (n, 8)=1可知,n为奇数. 设n=2k+1, n－1= 4k (k+1),8 | (n－1).
12. 4+1=5, 因此个位为4的2n, 加1后都能被5整除. 先考察n=1, 2, … , n 较小的情况:
2,4,8,16,32,64,128,256,512,1024,2048,个位为6的幂间隔4次得重复出现, 又6 ×4=24. 因此?24??4?1?24k?2?1能被5整除.
k
14.
+
即n=4k+2(k∈Z).
任意平方数的末位数字都不能是 2, 3, 7, 8的某一个.
2 22
证：令a=(10x+y), 则a2=(10x+y)≡y (mod 10). 令=0,1…9， y 的个位不能是2, 3, 7, 8.
2
因此，数字 a (1≤a≤9) 的平方 a的末位数字也没有2, 3, 7, 8. 习题2-2
3. 3?3?242?11?22.3?3?350nmm?3n?m?1??
4. 偶数m的最小非负完全剩余系中奇偶各半.任一组完全剩余系中各数必与0,1, …m－1中一个数同余,故均可写成mkr+r,r= 0,1, …m－1的形式.故亦奇偶各半. 其他的都是较基本的题目, 请看书后的答案或提示. 习题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
j
i－j
－1)，
φ (11) = 10，而20，21，22，…，29为10个不同的整数，所以它们构成模 11的一个简化剩余系
2.列表求出模 m 为 10，11，12，…，18等值时的最小简化剩余系及相应的φ (m). m 10 11 12 1 1 1 2 3 3 4 5 5 6 最 小 简 化 剩 余 系 7 7 7 8 9 9 10 11 φ (m) 4 10 4
13 14 15 16 17 18 1 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 5 5 5 5 5 6 6 7 7 7 7 7 8 8 8 9 9 9 9 10 11 12 11 11 11 11 13 13 13 15 17 12 6 8 8 16 6 13 14 10 11 12 13 14 15 16 3.证明定理 2.7.
证明:（必要性）∵ x1，x2，…，xk是模 m 的简化剩余系，
∴ k=φ(m)，且当 i ≠ j时，xi?xj（mod m），（xi，m）=1，i = 1，2，…，φ(m). （充分性）k=φ（m），∴ x1，x2，…，xk共有φ（m）个.
又 xi?xj（mod m），（i ≠ j，1≤i，j≤ k），（xi，m）=1（i=1，2，…，k），
∴ 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）是偶数 .
证：设 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为质数,?(m)?m?1,大于2的质数是奇数,m?1是偶数;如果m为合数,pi中最多只有一个是2(偶数),那么至少有一个为奇数,这时?(m)???pi?1?,显然是偶数.
i?1k
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）. 11. 若 m 是奇数，则φ（4m）=2φ（m）.
12.（1）分母是正整数 n 的既约真分数的个数是多少？为什么？ （2）分母不大于 n 的既约真分数的个数是多少？为什么？
解 10.∵（2，m）= 1，∴ φ（n）=φ（2m）=φ（2）φ（m）=φ（m）. 11. ∵ m 是奇数，∴（4，m）= 1，则φ（4m）=φ（4）φ（m）.
∵ φ（4）= 2，∴ φ（4m）=2φ（m）.
12.（1）φ（n）. （2）φ（2）+φ（3）+ … +φ（n）. 习题 2-4
1.举例说明欧拉定理中（a，m）=1是不可缺少的条件 . 2.求下列各题的非负最小余数：（1）84965除以13； （2）541347除以17；
（3）477385除以19； （4）7891432除以18； （5）(127156+34)28除以111. 解答：1. 当 a= 2，m =4时，?(4) =2，此时 22≡0（mod 4），可见（a，m）= 1是欧拉定理的不可缺少的条件 .
2.（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）。 3.设 p，q是两个大于 3的质数，求证：p2≡ q2（mod 24）. 4.设 p是大于 5的质数，求证：p4≡1（mod 240）. 解答：3. 24=3×8，（3，8）= 1. 由条件，( p，3 ) = ( q，3 ) = 1，由费尔马小定理有 p2≡1（mod 3）， q2≡1（mod3）. ∴ p2 ≡ q2（mod 3）. 又 ∵ p，q 必为奇数，由习题2-1第9题的结论，有p2≡1（mod 8），q2≡1（mod8）. ∴ p2 ≡ q2（mod 8）. ∴ p2 ≡ q2（mod 24）.
2
4. 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）. 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）.
6. 已知 p，q 是 两 相 异 的 质 数，且 ap-1≡1（mod q），aq-1≡1（mod p）， 求证：apq≡ a（mod pq）. 解答：5.（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. ∵ ap ≡ a（mod p），∴ apq ≡ (ap)q ≡ aq ≡ a（mod p）；同理，apq ≡ (aq)p ≡ ap ≡ a（mod q）， 而（p，q）= 1，故 apq≡ 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）.