《初等数论》习题解答（第三版）广东石油化工学院

∴216?2562?65536?154?mod641? ∴232?1542?23716??1?mod641? 即641∣232?1

5、若a是任一单数，则a2?1mod2n?2，?n?1? 证明：（数学归纳法）设a?2m?1

（1）n?1时，a2??2m?1??4m?m?1??1?1?mod8?， 结论成立。

（2）设n?k时，结论成立，即： ?2m?1??1?0mod2而a2k?12kn??2?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

3 ?0modk? 2????故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成立，则有

n

a2? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，

其中q?Z，所以

kk

a2= (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

解：?i?1535625?33?54?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时，

s?t u1?pvu?1?2?spt?vmod?p．结论成立。

s22、 若m1,m2,余类，则

,mk是k个两两互质的正整数，x1,x2,,xk分别通过模m1,m2,,mk的完全剩

M1x1?Mx2?2通过模m1m2?Mkxk

,k

mk?m的完全剩余系，其中m?miMi，i?1,2,证明：（数学归纳法）

（1） 根据本节定理3，知k?2时，结论成立。

（2） 设对整数k?1，结论成立，即若m1,m2,,两两互质，令km?,mk?1的完全剩

s'?M1x'1?Mx2'?余系时，s'必过模

2,x?Mk?xk?'，1当x11,x2,k1?分别通过模m1,m2,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,?m2m3,mk的完全剩余系时，

mk的完全剩余系。

x2?m2x3?因为(m1,m2mk?1xk过模m2mk)?1，由本节定理2得， ?m2mk?1xk)亦过模m2mk的完全剩余系。

m1(x2?m2x3?当x1,x2,2有m1m2,xk?1,xk分别过模m1,m2,,mk?1,mk的完全剩余系时，

mk个值，且据归纳假设，

?m1?m1mk?2xk?1?m1??1?m1mk?2xkmk?1xk ?(modm1mk?1xk 24 / 77

若x1?m1x2???m1x2???x1mk)

《初等数论》习题解答（第三版）广东石油化工学院

?(modm1)； x2?m2x3??x1?x1??m2x?3? ?x2?m2?m2mk?1xk

k??modmm1k(x2km )?(modm1)，x2?x2?(modm2)，…，xk?xk?(modmk) ?x1?x1?，x2?x2?，…，xk?xk?。 ?x1?x1所以x1?m1x2??m1m2mk?1xk过模m1m2mk的完全剩余系。

3．简化剩余系与欧拉函数 1．证明定理2：若a1,a2,,a?(m)是?(m)与m互质的整数，

,a?(m)是模m的一个简化剩余系。

并且两?对模m不同余，则a1,a2,证明：

a1,a2,又

,a?(m) 两?对模m不同余，所以它们分别取自模m的不同剩余类，

,a?(m)恰是?(m)个与m互质的整数，即它们恰取自与模m互质的全部剩余类。

a1,a2,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，

。 ?(m)）

?ai?ai??（i?1,2,?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