2.1　同余类与剩余系的基本性质

由定义1立即推出：

定理1（i）r mod m=｛r+km：k∈Z｝；

（ii）r mod m=s mod m的充分必要条件是r≡s（mod m）；

（iii）对任意的r，s，要么r mod m=s mod m，要么r mod m与s mod m的交为空集.

定理1（ii）表明同余式就是同余类（看做一个元素）的等式，因此，1中关于同余式的性质都可表述为同余类的性质.这些将安排在习题中.

定理2对给定的模m，有且恰有m个不同的模m的同余类，它们是

0mod m，1mod m，…，（m-1）mod m.（1）

我们记由这些同余类为元素所组成的集合为

Z/mZ=Z_m=｛j mod m：0≤j≤m-1｝.（1′）

证由定理1（ii）知这是m个两两不同的同余类.对每个整数a，由第一章3定理1知

a=qm+r，0≤r＜m.

因此，由定理1（i）知，a∈j mod m，即a必属于（1）中的某个同余类.证毕.

同余类还有一种很方便有用的表示形式.设a是一个整数，V是一个整数集合.我们约定它们的和与积分别为集合

a+V=｛a+v：v∈V｝，（2）

aV=｛av：v∈V｝.（3）

这样，由定理1（i）知，可把同余类表为

r mod m=r+mZ.（4）

由定理2及鸽巢原理立即推出：

定理3（i）在任意取定的m+1个整数中，必有两个数对模m同余；

（ii）存在m个数两两对模m不同余.

证因为对模m共有m个由式（1）给出的同余类，所以m+1个数中必有两个数属于同一个模m的同余类，这两个数就对模m同余.这就证明了（i）.在每个同余类r mod m（0≤r＜m）中取定一个数x_r作代表，这样就得到m个两两对模m不同余的数x₀，x₁，…，x_m-1.这就证明了（ii）.

由定理3可引进以下概念：

定义2（完全剩余系）一组数y₁，…，y_s称为模m的完全剩余系（或简称为模m的剩余系），如果对任意的a有且仅有一个y_j是a对模m的剩余，即a同余于y_j模m.

由定义中y_j的唯一性知这s个数一定是两两对模m不同余.由定理3知，模m的完全剩余系是存在的，且s=m，以及给定的m个数是一组模m的完全剩余系的充分必要条件是它们两两对模m不同余.事实上，一组模m的完全剩余系就是在模m的每个同余类中取定一个数作为代表所构成的一组数；而对于给定的一组模m的完全剩余系y₁，…，y_m，

y₁mod m，…，y_mmod m（5）

就是模m的m个两两不同的同余类，以及

其中后两个求并号表示对模m的任意取定的一组完全剩余系｛y｝求并.

下面来讨论完全剩余系的各种表示形式，在2.2小节还要作进一上讨论.容易直接验证：

0，…，m-1；1，…，m；-［m/2］，…，-［-m/2］-1

（当m是偶数时也可取为-［m/2］+1，…，-［-m/2］）；

-m+1，…，0；-m，…，-1

等都是模m的完全剩余系，它们分别称为模m的最小非负（完全）剩余系；最小正（完全）剩余系；绝对最小（完全）剩余系；最大非正（完全）剩余系；最大负（完全）剩余系.由式（1）知，对任意取定的m个整数k_r（0≤r＜m），

r+k_rm，0≤r＜m（7）

是模m的一组完全剩余系，以及对模m的任给的一组完全剩余系，一定可以选取适当的k_r（0≤r＜m），使它由式（7）表出（为什么）.一般地，由式（5）知，当y_j（1≤j≤m）是任给的一组模m的完全剩余系时，对任取的整数h_j（1≤j≤m），

y_j+h_jm，1≤j≤m（7′）

是模m的一组完全剩余系；反过来，对模m的任意一组完全剩余系，一定可以选取适当的h_j（1≤j≤m），使它由式（7）表出（为什么）.例如：取k_r=0（0≤r＜m），式（7）就给出了模m的最小非负剩余系；取k₀=m，k_r=0（1≤r＜m），式（7）就给出了模m的最小正剩余系；取

k_r=0（0≤r≤m/2），k_r=-1（m/2＜r≤m-1），

式（7）就给出模m的绝对最小剩余系；取k_r=-1（0≤r＜m），式（7）就给出了模m的最大负剩余系；以及取k₀=0，k_r=-1（1≤r＜m），式（7）就给出模m的最大非正剩余系.再例如，取

y_j=j（1≤j≤m），h_j=j（1≤j≤m），

则由式（7′）得到模m的完全剩余系：

（m+1）·1，（m+1）·2，…，（m+1）·m；

取y_j=-j（1≤j≤m），h_j=j（1≤j≤m），则由式（7′）得到模m的完全剩余系：（m-1）·1，（m-1）·2，…，（m-1）·m；在式（7′）中我们取h_j=y_ja_j（1≤j≤m，a_j为任意整数），就得到模m的完全剩余系：

（a₁m+1）y₁，…，（a_mm+1）y_m.

在不同问题中选取适当形式的完全剩余系，对问题的解决有时是很有帮助的.显见，任意两组模m的完全剩余系，它们各自元素之和对模m是同余的.容易求出：这和同余于

0+1+…+（m-1）≡（m-1）m/2

关于不同模的同余类之间的关系，我们来证明一个基本结论，一般情形可由它推出.

定理4设m₁|m，那么对任意的r有

r mod m⊆r mod m₁，即r+mZ⊆r+m₁Z，

等号仅当m₁=m时成立.更精确地说，若l₁，…，l_d是模d=m/m₁的一组完全剩余系，则

等号右边各个并式中的d个模m的同余类两两不同.特别地有

这就是说，模m₁的一个同余类是d（=m/m₁）个模m的同余类的并.

证法1只要证明式（9）的第一式.我们把同余类r mod m₁中的数按模m来分类.对r mod m₁中任意两个数r+k₁m₁，r+k₂m₁，

r+k₁m₁≡r+k₂m₁（mod m）

成立的充分必要条件是（利用1性质Ⅶ）：

k₁≡k₂（mod d）.

由此就推出式（9）右边和式中的d个模m的同余类是两两不同的，且r mod m₁中的任一数r+km₁必属于其中的一个同余类.另一方面，对任意的j必有

（r+l_jm₁）mod m⊆（r+l_jm₁）mod m₁=r mod m₁.

这就证明了所要的结论.

证法2利用表示形式（4）及式（6）可给出一个简洁漂亮的证明.我们有

这就证明了式（9）.注意所有求并的集合都是两两不相交的（为什么）.

在定理4中取m₁=1，r=0，式（9）就是式（6），因此定理4是式（6）的推广.应该指出，第一章3中的例1就是定理2，而例3则是给出了定理4的具体例子：m₁=2，m=6，r=1，l_j=j-1（1≤j≤3）.定理4是经常用到的，用同余式语言可表述为（为什么）

定理4′设m₁|m，那么，对任意的r，

n≡r（mod m₁）

成立的充分必要条件是以下d=m/m₁个同余式有且仅有一个成立：

n≡r+jm₁（mod m），0≤j＜d.

例如，取m₁=2，奇数n≡1（mod2），若取m=4，则n≡1（mod4），n≡3（mod4）有且必有一个成立；若取m=8，则n≡1，3，5，或7（mod8）有且必有一个成立.取m₁=3，则n≡-1（mod3），若取m=6，则n≡-1或2（mod6）有且必有一个成立；若取m=15，则n≡-1，2，5，8，11（mod15）有且必有一个成立.

当给出了两个不同模的同余类r₁mod m₁，r₂mod m₂，要求它们的交集（即同时属于这两个同余类的整数组成的集合），我们就可以取m=［m₁，m₂］.这样，r₁mod m₁就是m/m₁个模m的同余类的并，r₂mod m₂就是m/m₂个模m的同余类的并.由此就可求出它们由若干个模m的同余类组成的交集.这实际上是第四章3孙子定理所讨论的内容，这里就不多说了.

在进一步讨论既约同余类、既约剩余系之前，先来给出第一章4例8的另一种解法，以说明引进同余类的概念是有好处的.

例1同第一章4例8.

我们的想法是把要涂色的集合M扩充到全体整数，满足：（a）属于同一个模n的同余类中的数涂相同的颜色；（b）仍保持条件（i），（ii）成立.这样，为使条件（ii）成立，必须满足新的条件：（iii）0和k要涂同一种颜色.这样，我们就对全体整数Z涂色，满足条件（a）及（i），（ii），（iii）.我们来考察这样的涂色有什么性质.

（Ⅰ）对任意的j∈Z，j和-j一定涂相同的颜色.因为必有i满足

0≤i＜n，使j≡i（mod n），

由（a）知j和i同色.当i=0时，-j≡j≡0（mod n），所以由（a）知j和-j同色；当0＜i＜n时，由（i）知i和n-i同色.由（a）知n-i和-i，同色，以及-i和-j同色，所以，亦有j和-j同色.

（Ⅱ）对任意的j∈Z，j和j±k同色，即属于同一个模k的同余类中的数涂同色.因为必有0≤i＜n使j≡i（mod n），由（a）知j和i同色，由（ii）和（iii）知i和|k-i|同色，进而由（Ⅰ）推出|k-i|和i-k同色，而由（a）知i-k和j-k同色，所以j和j-k同色.由此及（Ⅰ）推得，j和-j，-j-k，j+k都同色.这就证明了所要结论.

由（a）和（Ⅱ）知，任一j∈Z必和j+sn+tk同色，这里s，t是任意整数.由（n，k）=1知，必有s₀，t₀使得s₀n+t₀k=1，所以，j和j+1同色.这就证明了所有整数都涂同一种颜色.

这一解法比第一章4例8的解法要思路清晰、自然，且看出了这种涂色方法的实质是满足条件（a）和（Ⅱ）.

下面来引进既约同余类、既约剩余系的概念，为此先证明一个定理.

定理5模m的一个同余类中的任意两个整数a₁，a₂与m的最大公约数相等，即（a₁，m）=（a₂，m）.

证设a₁∈r mod m，a₂∈r mod m.由定理1（i）知a_j=r+k_jm，j=1，2.进而由第一章2定理8（iv）得

（a_j，m）=（r+k_j m，m）=（r，m），j=1，2.

这就证明了所要的结论.

定义3模m的同（剩）余类r mod m称为模m的既约（或互素）同（剩）余类，如果（r，m）=1.模m的所有既约同余类的个数记做φ（m），通常称为Euler函数.

定义4一组数z₁，…，z_t称为模m的既约（或互素）剩余系，如果（z_j，m）=1，1≤j≤t，以及对任意的a，（a，m）=1，有且仅有一个z_j是a对模m的剩余，即a同余于z_j模m.

由定理5知，既约同余类的定义是合理的，即不会因为一个同余类中的代表元素r取得不同而得到矛盾的结论.由定义及定理2（以m mod m代0mod m）立即推出：

定理6模m的所有不同的既约同余类是

r mod m，（r，m）=1，1≤r≤m.（11）

φ（m）等于1，2，…，m中和m既约的数的个数.

由于每个和m既约的数必属于某个模m的既约同余类，所以由定理6及鸽巢原理立即推出（证明留给读者）

定理7（i）在任意取定的φ（m）+1个均和m既约的整数中，必有两个数对模m同余；

（ii）存在φ（m）个数两两对模m不同余且均和m既约.

由定义4中z_j的唯一性知这t个数一定两两对模m不同余.由定理7知既约剩余系是存在的，且t=φ（m）.事实上，模m的既约剩余系就是在模m的每个既约同余类中取定一个数作代表所构成的一组数，因此它的一般形式是：

r+k_rm，（r，m）=1，1≤r≤m，（12）

其中k_r是任意取定的整数；而对于模m的一组既约剩余系z₁，…，z_φ（m），

z₁mod m，…，z_φ（m）mod m（13）

就给出了模m的φ（m）个两两不同的既约同余类.

应该指出的是：模m的一组完全剩余系中所有和m既约的数就组成模m的一组既约剩余系.这一点在考虑问题时是有用的.此外，任意给定的φ（m）个和m既约的数，只要它们两两对模m不同余就一定是模m的既约剩余系.Euler函数φ（m）在数论中是十分重要的.本章将从剩余类，剩余系的角度来讨论Euler函数的性质.如何求它的值是首先要解决的问题，下面来讨论最简单的情形.

当m=1时，模1的同余类只有一个：0mod1，它是既约同余类，所以φ（1）=1.0或任一整数就构成模1的既约剩余系.当m=2时，模2的同余类有两个：0mod2，1mod2.只有1mod2是既约同余类，所以φ（2）=1.1或任一奇数就构成模2的既约剩余系.模4的既约同余类是：1mod4，3mod4，φ（4）=2.1，3是模4的一组既约剩余系.模12的既约同余类是：1mod12，5mod12，7mod12，11mod12，φ（12）=4.1，5，7，11是模12的一组既约剩余系.当m=p^k，p是素数时有下面的结论.

定理8设p是素数，k≥1，那么

φ（p^k）=p^k-1（p-1），（14）

并且模p^k的既约同余类是

（a+bp）mod p^k，1≤a≤p-1，0≤b≤p^k-1-1.（15）

证由定理6知，φ（p^k）等于满足以下条件的r的个数：

1≤r≤p^k，（r，p^k）=1.

由于p是素数，所以有

由此及第一章4定理5知，（r，p^k）=1的充分必要条件是（r，p）=1，即p｜/r.因此，φ（p^k）就等于1，2，…，p^k中不能被p整除的数的个数.由于1，2，…，p^k中能被p整除的数有p^k-1个，所以，φ（p^k）=p^k-p^k-1，这就是式（14）.由带余数除法知，任一r：1≤r≤p^k，p｜/r，可表示为

r=bp+a，1≤a≤p-1，0≤b≤p^k-1-1.

反过来，对任意满足1≤a≤p-1，0≤b≤p^k-1-1的a，b，相应的r=bp+a必满足1≤r≤p^k，p｜/r.这就证明了式（15）.

例如：当m=3³时，φ（3³）=3³-3²=18，模3³的既约同余类是

（a+b·3）mod3³，1≤a≤2，0≤b≤8.

1，2，4，5，7，8，10，11，13，14，16，17，19，20，22，23，25，26就是模3³的一组既约剩余系.如果取绝对最小剩余，那么，±1，±2，±4，±5，±7，±8，±9，±10，±11，±13就是模3³的一组既约剩余系.如何进一步用既约剩余系的性质求一般的φ（m）将在3讨论.