《初等数论》习题解答（第三版）
162 ∴2?256?65536?154?mod641? 322 ∴2?154?23716??1?mod641?
即641∣232?1 5、若a是任一单数，则a2n?1?mod2n?2?，?n?1?
2证明：（数学归纳法）设a?2m?1
（1）n?1时，a2??2m?1??4m?m?1??1?1?mod8?， 结论成立。
（2）设n?k时，结论成立，即： ?2m?1??1?0mod2而a2k?12k?k?2???2m?1?k2k?1?2k?2t，?t?z?
k?1?a2?1a2?1?a2?1a2?1?2
?k??2k????? ?2k?2t???2?2k?2?t
k?4 ?t2?22?t?2k? 3 ?t?2k?3t?2k?1?1
32 ?0modk?
????故n?k?1时，结论也成立；∴n?1时，结论也成立。
证明：若2?|a，n是正整数，则a2? 1 (mod 2n + 2)。 (4) 设a = 2k ? 1，当n = 1时，有
a2 = (2k ? 1)2 = 4k(k ? 1) ? 1 ? 1 (mod 23)，
即式(4)成立。
设式(4)对于n = k成立，则有
na2? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，
其中q?Z，所以
kka2= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，
其中q ?是某个整数。这说明式(4)当n = k ? 1也成立。
由归纳法知式(4)对所有正整数n成立。
21 / 77
k?1 《初等数论》习题解答（第三版）
?i?1535625； ?ii?1158066
34解：?i?1535625?3?5?7?13；
?ii?1158066?2?3272?13?101
§2 剩余类及完全剩余系
1、 证明x?u?ps?tv，u?0,1,2,?,pt?1，t?s是模ps的一个完全剩余类。
证明：显然对u,v的不同取值，x共有ps?t?pt?ps个值，故只需证这样的ps个值，关于模ps的两两互不同余。
若u1?ps?tv1?u2?ps?tv2modps
???u1?u2?ps?t?v1?v2??modps?
?ps?t∣u1?u2，即u1?u2?modps?t??u1?u2 ?ps?tv1?ps?tv2?modps??v1?v2?modpt??v1?v2
∴u1?u2或v1?v2时，
u? u1?ps?tv1?2?spt?vmod?p．结论成立。
s22、 若m1,m2,?,mk是k个两两互质的正整数，x1,x2,?,xk分别通过模m1,m2,?,mk的完全剩
余类，则
M1x1?Mx2?2??Mkxk
通过模m1m2?mk?m的完全剩余系，其中m?miMi，i?1,2,?,k 证明：（数学归纳法）
（1） 根据本节定理3，知k?2时，结论成立。
,（2） 设对整数k?1，结论成立，即若m1,m2?'',xs'?M1x'?1,x2,?1Mx2??2?Mk?xk?，1当x1,两两互质，令km?k1?分别通过模m1,m2,?,mk?1的完全剩
余系时，s'必过模
m'?m1m2...mk?1的完全剩余系，其中miMi'?m'(i?1,2...k?1)。
22 / 77
《初等数论》习题解答（第三版）
现增加mk,使(mi,mk)?1 (i?1,...k?1)，
令Mi?Mkmk(1,...k?1)，m'?Mk?m1m2...mk?1，m?mkMk?m1m2...mk 则易知(m1,m2,...,mk)?(mk,Mk)?1， 再令x?Mkxk?mks'，
当xk过模mk的完全剩余系，s'过模Mk的完全剩余系时，据本节定理3，x必过模
m?mkMk?m1m2...mk的完全剩余系，即对k结论成立。
3n?1?1)中每一个整数有而且只有一种方法表示成 3、（i）证明整数?H,...?1,?0,1,...,H(H?3?13nxn?3n?1xn?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个值，且两两互不相等，否则
3nxn'?3n?1xn?1'?...3x1'?x0'?3nxn?3n?1xn?1?...3x1?x0
'?3n(xn'?xn)?3n?1(xn?1'?xn?1)?...3(x1'?x1)?x0?x0?3|x0?x?x0?x.此即
'0'0
3n?1(xn'?xn)?3n?2(xn?1'?xn?1)?...(x'?x)?0?3|x?x1?x?x1?...?x?xn又?的最大值是3?3nn?1'1'1'n
3n?1?1?...3?1??H
3?1最小值是?3n?3n?1?...?3?1??H 所以，结论成立。
23 / 77
《初等数论》习题解答（第三版）
（ii）特制n?1个砝码分别重1,3,3,...,3斤，把要称的物体
2n???di?????i?1i?1rr?a?di??及取-1?的砝码放在天平的右盘，xi取1的砝码放在左盘，则从（i）的结论知，当xi取适当的值时，可使T?3nxn?3n?1xn?1?...3x?x0.之值等于你所要称的物体的斤数??H?。
4、若m1,m2,...,mk是K个两两互质的正整数，x1,x2,...xk分别过模m1,m2,...,mk的完全剩余系，则
x1?m1x2?m1,m2x3?...?m1,m2,...,mkxk.................?
通过模m1,m2,...,mk的完全剩余系。 证明：（数学归纳法）
（1）K?2时，x1,x2分别过模m1,m2的完全剩余系时，
x1?m1x2共有m1m2个值，且若
??m1x2?(modm1m2)?m1(x2?x2?)?x1??x1(modm1m2) x1?m1x2?x1??x1，且x2?x2???m1x1??x1x1(modm2) m1?，x2?x2?，即k?2时结论成立； ?x1?x1（2）设当x2,?,xk分别过模m2,?,mk的完全剩余系时，
x2?m2x3???m2m3?mk?1xk过模m2?mk的完全剩余系。
因为(m1,m2?mk)?1，由本节定理2得，
m1(x2?m2x3???m2?mk?1xk)亦过模m2?mk的完全剩余系。
当x1,x2,?,xk?1,xk分别过模m1,m2,?,mk?1,mk的完全剩余系时， 2有m1m2?mk个值，且据归纳假设， 若x1?m1x2???m1?mk?2xk?1?m1?mk?1xk
??m1x2????m1?mk?2xk??1?m1?mk?1xk?(modm1?mk) ?x1 24 / 77
《初等数论》习题解答（第三版）
?(modm1)； x2?m2x3???m2?mk?1xk ?x1?x1??m2x?3??modm??m?? ?x22km?1k(x2?(modm1)，x2?x2?(modm2)，…，xk?xk?(modmk) ?x1?x1?，x2?x2?，…，xk?xk?。 ?x1?x1所以x1?m1x2???m1m2?mk?1xk过模m1m2?mk的完全剩余系。
3．简化剩余系与欧拉函数
1．证明定理2：若a1,a2,?,a?(m)是?(m)与m互质的整数，
并且两?对模m不同余，则a1,a2,?,a?(m)是模m的一个简化剩余系。 证明：
km)
?a1,a2,?,a?(m) 两?对模m不同余，所以它们分别取自模m的不同剩余类，
又?a1,a2,?,a?(m)恰是?(m)个与m互质的整数，即它们恰取自与模m互质的全部剩余类。 2．若m是大于1的正整数，a是整数，(a,m)?1，?通过m的简化剩余系，
?a??1则?????(m)，其中?表示展布在?所通过的一切值上的和式。
2??m??证明：由定理3知，?通过m的简化剩余系：
a1,a2,?,a?(m)，其中0＜ai＜m且(ai,m)?1，
而??ai?ai。 ??（i?1,2,??(m)）
mm??若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