王进明初等数论习题解答

2 22

证：令a=(10x+y), 则a2=(10x+y)≡y (mod 10). 令=0,1…9， y 的个位不能是2, 3, 7, 8. 因此，数字 a

(1≤a≤9) 的平方 a习题2-2 3. 352

的末位数字也没有2, 3, 7, 8.

?30?242?11?22.3n?3m?3m?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 13 14 15 16 17 18 1 1 1 1 1 1 1 1 1 2 2 3 3 4 2 2 3 3 4 5 5 5 3 3 4 4 5 5 5 5 6 6 7 7 7 7 8 6 最 小 简 化 剩 余 系 7 7 7 7 8 9 9 8 8 9 9 9 9 10 10 10 11 φ (m) 4 10 4 12 6 8 8 16 6 11 11 11 11 11 11 12 13 13 13 14 13 14 15 15 16 17 12 13 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?是偶数. 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）.

4. 240 = 3×5×16，由条件，( p，3 ) = ( p，5 ) = 1，∴ p4≡1（mod5），p4≡（p2）2≡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）.

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.

11. p是不等于 2和 5的质数，k是自然数，证明：

p|9999.

?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）. 11. 9999?10?p?1?k?1. 由条件，（10，p）= 1，∴ 10p-1≡ 1（mod p）.

?p?1?k个9∴ （10p-1）k≡ 1（mod p）. ∴ p|99?(m)99.

?p?1?p个912. 设（m，n）=1，证明：m证：∵（m，n）= 1，∴n称可得 m

?(n)?(n)+ n≡1（mod mn）.

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

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

?(n)+n

?(m)≡ 1（mod m）. 对

+n

?(m)≡ 1（mod n）. ∴ m

x+n

?(m)≡ 1（mod mn）.

13. 已知 a =18，m =77，求使 a≡1（mod m）成立的最小自然数 x. x=30.

?(77)??11?1??7?1??60,由定理，满足要求的最小自然数 x必为60?的约数。验算可知。

习题3-1

1．解下列不定方程：

（1）7x－15y=31； （2）11x+15y=7； （3）17x+40y=280；

（4）525x+231y=42； （5）764x+631y=527； （6）133x－105y=217. 解：（1）辗转相除得15=7×2＋1, ∴ 1 = 15－7×2= 7×(－2)－15×(－1)， ∴ 因此原方程的一个解是 x0＝－2×31＝－62， y0＝－1×31＝－31;

原方程的通解为??x??62?15t这里t为任意常数.

y??31?7t?（2）辗转相除得15=11×1＋4, 11=4×2＋3, 4=3+1 ∴ 1 = 4－3=4－(11－4×2)= 4×3－11=

(15－11×1) ×3－11=15×3 + 11×(－4)，

∴ 因此原方程的一个解是 x0＝－4×7＝－28， y0＝3×7＝21;

原方程的通解为??x??28?15t这里t为任意常数.

?y?21?11t（3）用分离整数法：x?280?40y8?6y?16?2y?.

1717观察可知y =－10时，x = 36 + 4= 40. ∴ 原方程的通解为??x?40?40t这里t为任意常数.

?y??10?17t2. 解下列不定方程：（1）8x-18y+10z=16； （2）4x-9y+5z=8； （3）39x-24y+9z=78；

（4）4x+10y+14z+6t=20； （5）7x-5y+4z-3t=51.

3. 解下列不定方程组：（1） x+2y+3z=10， （2） 5x+7y+3z=25，

x-2y+5z=4； 3x- y-6z=2；

（3） 4x-10y+ z=6， （4） 10x+7y+ z=84，

x-4y- z=5； x-14y+ z= -60；

4. 求下列不定方程的正整数解：（1）5x－14y=11； （2）4x+7y=41； （3）3x+2y+8z=21. 5. 21世纪有这样的年份，这个年份减去 22 等于它各个数字和的495倍，求这年份.

6. 设大物三值七，中物三值五，小物三值二，共物一百三十八，共值一百三十八，问物大中小各几何？ 7. 买2元6角钱的东西，要用1元、5角、2角、1角的四种钱币去付，若每种钱币都得用，则共有多少种付法？

8. 把 239分成两个正整数之和，一个数必是 17 的倍数，另一个数必是 24的倍数，求这两位数. 9. 一个两位数，各位数字和的 5倍比原来大 10，求这个两位数.

10. 某人 1981年时的年龄恰好等于他出生那一年的年号的各位数字之和，这个人是在哪一年出生的？ 11. 一个四位数，它的个位数上数比十位数字多 2，且此数与将其数字首尾颠倒过来所得的四位数之和为 11770，求此四位数 . 习题 3-2

1．求 x2+ y2= z2中 0< z<60的所有互质的解.

2．求三个整数 x，y，z（x> y> z>0），使 x- y，y- z，x- z都是平方数 . 1．

b a x y z 1 2 3 4 5 1 4 1 6 2 3 2 5 2 7 3 4 4 5 9 15 35 5 8 21 45 7 12 12 20 28 24 40 17 37 13 29 53 25 41 2. 设 x- y= a2，y- z= b2，x- z= c2，则 a2+ b2= c2，因此给出 a，b的值即可求得x，y，z.