n?a0?a1??...?ak(mod9)n?a0?a1?...?(?1)kak(mod11)由此计算12345×6789被9和11除的余数。
iii?1i?2证明：（1）因为ai10?ai?ai(10?1)?9ai(10?10?...?1)，a0?a0(mod9)所
以
ai10i?ai(mod9),(i?0,1,...,k)，
从而
n?a0?a110?a2102?...?akk10?a0?a1??...?ak(mod9)
（2）又因为aiii10?(?1)ai?a1i0??(??1)?a1i??1?1i10??2ii??i10?a0?a0(mod11)，所以
aii10?(?1)iai(mod11),(i?0,1,...,k)，
从而
n?a0?a110?a2210?...?ak10k?a0?a1?...?(?1)kak(mod11)
12345?1?2?3?4?5?15?6(mod9)
6789?6?7?8?9?30?3(mod9)
?12345?6789?6?3(mod9)?0(mod9).
所以12345×6789被9整除；
12345?5?4?3?2?1(mod11)?3(mod11) 6789?9?8?7?6(mod11)?2(mod11)
?12345?6789?6(mod11)
即12345×6789被11除余数为6。
3．解下列同余方程
（1）8x?5(mod23).（2）23x?7(mod37). 解：（1）8x?5?5?23?28(mod23)
?2x?7(mod23),(4,23)?1 ?2x?7?23?30(mod23) ?x?15(mod23).((2,23)?1)
（2）23x?7?7?11?37?414?23?18?(mod37)
?x?18(mod37).((23,37)?1)
4．对每个整数n证明
（1）n2?2(mod3).（2）n2?0或1(mod4).
11
?...??1i??，(1)（3）n?0,?1(mod9).（4）n?0,1(mod16). 证明：（1）设n?3m?i,i?0,1,2。 当i=0,时n?(3m)?9m?0(mod3);
当i=1,时n?(3m?1)?9m?6m?1?1(mod3); 当i=2,时n?(3m?2)?9m?12m?4?1(mod3); 所以n?2(mod3).
（2）设n?2m?i,i?0,1。 当i=0,时n?(2m)?4m?0(mod4);
当i=1,时n?(2m?1)?4m?4m?1?1(mod4); 所以n?0或1(mod4).
（3）设n?3m?i,i?0,1,2。 当i=0,时n?(3m)?27m?0(mod9);
当i=1,时n?(3m?1)?27m?9m?9m?1?1(mod9); 当i=2,时n?(3m?2)?27m?54m?36?8??1(mod9); 所以n?0,?1(mod9).
（4）设n?4m?i,i?0,1,2,3。 当i=0,时n?(4m)?256m?0(mod16);
当i=1,时n?(4m?1)?256m?256m?96m?16m?1?1(mod16); 当i=2,时n?(4m?2)?16(2m?1)?0(mod16);
当i=3,时n?(4m?3)?256m?768m?864m?432m?81?81?1(mod16);
44432444444324443333233323332222222222222222342所以n4?0,1(mod16).
5．设a为奇数，n?1，证明a2?1(mod2n?2). 证明：用数学归纳法。
当n=1时，设a?2k?1，a?(2k?1)?4k?4k?1?4k(k?1)?1,8|4k(k?1),
222n?a2?1(mod23)。
假设n时成立，即a2?1(mod2n?2).考虑n+1情况。 由a2?1(mod2n?2)知a2?1?2n?2h,h?Z，从而
nnna
2(n?1)?a??2n2?(1?2n?2h)2?1?2n?3h?22n?4h2?1?2n?3(h?2n?1h2),12
?a2(n?1)?1(mod2n?3)，由数学归纳法知，当a为奇数，n?1，有a2?1(mod2n?2).
n6．证明
（1）当n?3时?(n)为偶数。 （2）
i?1(i,n)?1?n1i?n?(n)
2eee证明：（1）设n?p11p22...prr是标准分解式，由引理1.2.7知，欧拉函数
?(n)??(pie?pie?1)，
iiri?1因为n?3，故标准分解式中必有某个是奇素数，比如pk,即pk?1是偶数，则
?(n)??(pie?pie?1)中的因数有pke?pke?1?pke?1(pk?1)是偶数，所以欧拉函数?(n)iikkkri?1为偶数。
（2）设{a1,a2,...,a?(n)}为模n的一个缩系，则有
i?1(i,n)?1?i??ak?1n?(n)ka,n(均，这里a1,a2,...?)与n互素且互不相等。由引理1.1.8知
1?(a,n)?(ak?n,n)?(n?ak,n),，n?a1,n?a2,...,n?a?(n)也互不相等，故{n?a1,n?a2,...,n?a?(n)}也是模n的一个缩系，则有
?(n)k?1?a??(n?a)?n?(n)??akkk?1k?1?(n)?(n)k，
从而
n?(n)?2?ak?2k?1?(n)i?1(i,n)?1?ni
由此
i?1(i,n)?1?n1i?n?(n)
27．设m,n?1,m?nt(t?Z).证明模n的每个同余类都恰好是模m的t个同余类之并集。 证明：设模n的同余类为a?{a?ln:l?Z},a?0,1,...,n?1，模m=nt 的同余类为
[b]?{b?sn:s?Z},b?0,1,...,m?1。对于某个模n的同余类a，若有x?a?ln?a，由
带余除法可设l?tq?r,0?r?t，于是
x?a?ln?a?(tq?r)n?a?rn?ntq?(a?rn)?mq?[a?rn]此说明
13
a?[a]?[a?n]?...?[a?(t?1)n]，反之若
x?[a]?[a?n]?...?[a?(t?1)n]?x?a?in?sm,0?i?t,s?Z?x?a?in?snt?a?(i?st)n?a，即有
[a]?[a?n]?...?[a?(t?1)n]?a，所以 a?[a]?[a?n]?...?[a?(t?1)n]
即模n的每个同余类都恰好是模m的t个同余类之并集。
习题１.３Ｂ（P31）
１.（１）对于环Zm中每个元素α，m个α相加为0。
（２）设p为素数，对于域Zp中每个非零元素α和正整数n,证明n个α相加为0当且仅当p|n.
m??????a?...?a?ma，而证明：（１）??a，m??ma?a?a?...a?a???????m，所以m??ma?0。 ma?0(mom)d（２）设??a,a?0.
若n??na?0，即有na?0(modp)，或p|na，而a?0.即p不整除a,p是素数，从而由p|na必有p|n
反之，若p|n，有p|na，从而有na?0(modp)即n??na?0。
习题集1.4（P37）
1. 解下列同余方程 (1) 32x?12(mod8). (2) 28x?124(mod116). (3) 5x?44(mod81).
解：（1）（32，8）=8不整除12，故原同余方程无整数解。 （2）(28,116)=4|124故原同余方程有整数解。
3131?3?29?56????8?21(mod29)777故原方程的全部整数解是x?21(mod29)，而对模116有4个解28x?124(mod116)?7x?31(mod29)?x?x?21,50,79,10 8（3）(5,81)=1,故原同余方程有整数解。
5x?44(mod81)?x?4444?81??25(mod81)，对模81有一个解x?25(mod81) 5514
2．解下列同余方程组
?x?2(mod4),??x?3(mod5), ?x?7(mod9).?解：（1）判断是否有解。因为4,5,9两两互素，故同余方程组有整数解。 （2）分别解M1y≡1(mod4),M2y≡1(mod5),M3≡1(mod9)其中
M1=45，M2=36,M3=20,b1=2,b2=3,b3=7,
y1?11?4411?3511?911?9??1(mod4),y2???1(mod5),y3?????5(mod9)45453636202022取N1=1,N2=1,N3=5,得
（3） 写出解的表达式
x?b1M1N1?b2M2N2?b3M3N3?2?45?1?3?36?1?7?20?5?898?178??2(mod180)，即原同余方程组的全部整数解是：x??2(mod180)
3. 用中国剩余定理解同余方程37x≡31(mod77) 解：原方程等价于同余方程组
?37x?31(mod7) ?37x?31(mod11)?3131?105???2(mod7),3737
3131?154x???5(mod11)3737x?再解同余方程组
?x??2(mod7), ??x?5(mod11)由于7，11互素，故同余方程组有解。M1=11,M2=7， 解同余方程11y?1(mod7),7y?1(mod11),
11?21??2(mod7),1111 11?22y????3(mod11)77y?取N1=2，N2=-3，于是
x?b1M1N1?b2M2N2??2?11?2?5?7?(?3)?5(mod77)
即原同余方程的全部整数解为x?5(mod77)
6．求2400被319除的余数。 解：319=11×29，故相当于解方程：
15