例1. 12 证明对任何整数n, 证 只要证对任意正整数n有 即可.
由于
f(n)?7n?1n3?1n5均是一个整数.
15357n?5n3?3n5?0(mod15) (1.6.2)
7n?5n3?3n5?n?2n3?n3?n(mod3),
而
n3?n?n(n?1)(n?1)?(n?1)?n(n?1)
是3的倍数, 故
7n?5n3?3n5?0(mod3). (1.6.3)
又
7n?5n3?3n5?2n?2n5?2(n?n5)(mod5)或
, 而
n5?n?(n?1)n(n?1)(n2?1)时,
及当
n?0?1或
?2(mod5). 当
n?0或
?1(mod5)(n?1)n(n?1)?0(mod5)n??2(mod5)时, (n2?1)?0(mod5), 因此不论n为何整数, 均有n5?n?0(mod5), 故
7n?5n3?3n5?0(mod5). (1.6.4)
因为(3,5)?1,所以由性质定理vii) 及(1.6.3)与(1.6.4)即可推得(1.6.2)成立. ▋
练习1.7
1. 1) 求19992) 求19992. 证明32000365的最后两位数字.
表示成17进制数时的个位数及最后两位数.
2000?41999?0(mod5).
3. 证明若一个三位数的数字（0到9之间的数）是相邻的三个数字, 且百位上的数字大于个位上的数字, 则该位数与它的数字次序相反的三位数的差等于是198.
4. 设十进制自然数21a39b8（其中0?a,b?9）为99的倍数, 求a与b. 5. 设n为正整数, 证明330|62n?52n?11.
?1, 求n6. 假设131|11?n??
16
§1. 8 同余类与剩余类
定义1. 9 设m是一给定的正整数, 则任意整数a关于模m同余0或1, 或2,???, 或m?1. 于是我们可将整数集划分成m个类：所有与r(0?r?m?1)同余的整数归为一类. 显然, 在同一类中的任两个
整数关于模m一定同余, 而不在同一类中的任两个整数关于模m一定不同余. 每一个这样的类称之为模
m的同余类或模m的剩余类. 从每个类中任取出一数, 则得到的这m个数就称为模m的完全剩余系, 又
简称m的完系.
若记r?m?为r所在的模m的同余类（或在明确模m的情况下简记为r）, 则有下列性质定理.
定理1. 10 设m是一给定的正整数, 则有 i) ii)
r?m???r?kmk???. r?m??s?m??mr?s.
iii) 对任意两整数r,s,或者riv)
?m??s?m?, 或者r?m??s?m???.
k个数a1,a2,???,ak构成的完系的充要条件是k?m,且当i?j时有ai??aj(modm).
以上性质由定义可直接得知.
根据完系的定义, 对于给定的正整数m, 模m的完系有无限个,下面我们给出几个常用的完系. 1) 模m的最小非负完全剩余系：
0,1,?,m?1.
2) 模m的最小正完全剩余系：
1,2,?,m
3) 模m的最大非正完全剩余系：
?(m?1),?(m?2),?,?1,0.
4) 模m的绝对值最小完全剩余系：
m为偶然时：?m,?,?1,0,1,?,m?1 或 ?m?1,?,?1,0,1,?,m.
2222m为奇数时：?m?1,?,?1,0,1,?,m?1. 22定理1. 11 若a1,a2,?,am是m的一个完系,
a与b是任意两整数且(a,m)?1, 则
aa1?b,aa2?b,?,aam?b
亦是m的完系.
证 由定理3. 2—iv), 只要证明对任何i如果aai?j,有aai?b??aaj?b(modm) 即可.
?b?aaj?b(modm), 则有aai?aaj(modm). 因(a,m)?1,由定理3.2—vii)即得
17
ai?aj(modm)▋
,这与
a1,a2,???,am为
m的完系矛盾,所以
aai?b?aaj?b(momd. )
例1. 13 若a1,a2,???,am是m的完系, 数之和为1m(m?1).
a,b??且(a,m)?1, 则aai?b除以m的最小非负余
2证 由定理3. 3知aa1?b,aa2?b,???,aam?b是m的一个完系. 因此aai?b （i?1,2
,???,m）除以m而得的m个最小非负余数构成m的一个完系, 即它们构成m的最小非负完全剩余系，
所以它们的和为0?1?2?????(m?1)1m(m?1). ▋ 2在模m的同余类中, 有些类中的每个数均与m互素, 如1所在的同余类中每个数均与m有互素. 若
?m?8, 则同余类1,3,5,7中的每个数均与8互素, 这样的同余类我们将给它们一个特定的名称.
定义1. 10 设m是一个大于1的正整数, 定义
i）模m的同余类r称为模m的一个简化同余类；如果(r,m)?1.
ii） 在模m的所有简化同余类中各取一数, 我们称这组数为模m的一个简化剩余系, 又称简系. 如果r是模m的一个简化同余类,
a是r中任一整数, 则a?r?0(modm), 即存在整数k使
a?r?km, 从而由(r,m)?1得(a,m)?1. 因此模m的同余类是模m的一个简化同余类的充要条
件该余类中的每个数均与m互素, 且由此可知,
定理1.12 i)
m的简系中的每个数皆与m互素, 于是我们有下列定理：
k个整数a1,a2,???,ak构成m的简系的充要条件是：
k??(m)；ii) (ai,m)?1；iii) ai??aj(modm), i?j.
证 (必要性) 由简系的定义知
a1,a2,???,ak是从模
m的所有简化剩余类中各取一数而构成
的.1,2,???,m是模m的一个完全剩余类, 于是模m的所有简化剩余类组成的集合是
?r|(r,m)?1,1?r?m?.
由Euler函数的定义可知：满足上面集合中条件的r共有?(m)个, 因此模m的简化剩余类共有
?(m), 故k??(m), 即i) 成立, 而ii) 及iii) 由简系的定义即知成立.
(充分性) 由必要性证明知，模m的简化剩余类共有?(m),条件i)及ii)说明a1,a2,
???,ak是模m的简化剩余类中选取的?(m)个整数,再由条件iii)即知:a1,a2,???,ak是从模m的全部
?(m)个简化剩余类中各选取的一数而成,所以依定义,a1,a2,???,ak是的一个简系. ▋
18
利用定理1. 12 我们便有下列结论：
定理1.13 设a与b是满足(a,m)?1及m|b的两整数, 若a1,a2,???,a??m?是m的简系, 则
aa1?b,aa2?b2,???,aa??m??b
亦是m的一个简系.
证 利用定理1.12, 由(a,m)?1及m|b便得(aai. 且若当?b,m)?(aai,m)?(ai,m)?1, 于是由
得(a,m?)1,
i?j时, 有
aai?b?aaj?b(modm), 则
aai?abj(modm)ai?aj(modm)这与a1,a2,???,a??m?为m的简系矛盾. 故aai?b?aaj?b(modm), 所以
aa1?b,aa2?b2,???,aa??m??b
构成m的简系. ▋
定义1.11 设m是一正整数, 则所有不超过m且与m互素的?(m)个数构成m的一个简系, 我们称该系为m的最小正简化剩余系（可简称最小正简系或缩系）.
例如, 8的最小正简系为1, 3, 5, 7.15的最小正简系为1, 2, 4, 7, 8, 11, 13, 14.
例1. 14 若
p为奇数, m是任一正整数且满足2m?1(modp), 证明
1m?2m?????(p?1)m?0(modp)
证 因
p为素数, 故1,2,???,p?1是p的简系, 又(2,p)?1, 从而由定理1.13知
2?1, 2?2, ???, 2?(p?1)
也是
p的简系, 因此得
1m?2m?????(p?1)m?(2?1)m?(2?2)m?????(2?(p?1))m(modp).
即有
(2m?1)(1m?2m?????(p?1)m)?0(modp),
亦即
p|(2m?1)(1m?2m?????(p?1)m),
但
p?(2m?1), 所以必有
p|1m?2m?????(p?1)m,
于是
19
1m?2m?????(p?1)m?0(modp). ▋
例1. 15 设m?m1m2,(m1,m2)?1, 数, 则
i) 当x跑遍m1的完系,ii) 当x跑遍m1的简系,我们只证明ii).
证 首先, 设x1,x2,???,x?a与b是满足条件(a,b)?1, m1|b及m2|a的任意两整
y跑遍m2的完系时,ax?by跑遍m的完系. y跑遍m2的简系时,ax?by跑遍m的简系.
?m1?是m1的简系, x1,x2,???,x??m2?是m2的简系, 则
{ax?by|x?{x1,???,x?(m1)}, y?{y1,???,y?(m2)}}
共有?(m1)?(m2)个数, 即?(m1m2)（??(m)）个数, 定理1.12的第i) 条成立.
其次, 如果
axi?byj?ax??byk(modm1m2),
. 再由
那么
, axi?byj?ax)??byk(mod1m从而有
, xi?x?(modm1)由
m1|b得axi?ax?(modm1)(a,b)?1知(a,m1)?1,
即有
i??. 同理可证j?k. 因此, 定理1.12的第iii)条成立.
最后证(axi?byj,m1m2)?1成立.
?1及m1|b知(a,m1)?1, 故(axi,m1)?1. 再由m1|b可得
因为(xi,m1)?1, 又由(a,b)(axi?byj,m1)?1.
同理可证
(axi?byj,m2)?1.
因此, 由(m1,m2)?1, 即得
(axi?byj,m1m2)?1.
从而根椐定理1.12便知
axi?byj（i?1,???,?(m1),j?1,???,?(m2)）
是m?m1m2的简系. ▋
特殊情形, 可取a?m2,b?m1.
定理1. 15（Euler定理） 设m是任一给定的正整数，a是任一整数且(a,m)?1, 则有
20