酒烧吢头。 a,b,?,c，可类似地定义它们的最小公倍数［a,b,?,c］ 最小公倍数主要有以下几条性质： （1）与的任一公倍数都是（2）两个整数
的倍数，对于多于两个数的情形，类似结论也成立；
（但请注意，这只限
的最大公约数与最小公倍满足：
于两个整数的情形，对于多于两个整数的情形，类似结论不成立）； （3）若a,b,?,c两两互素，则［a,b,?,c］＝｜a,b,?,c｜； （4）若
，且a,b,?,c两两互素，则a,b,?,c｜
。
第四节 同余
同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方
面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。
基础知识
三个数论函数
对于任何正整数均有定义的函数，称为数论函数。在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数[x]及其性质，除数函数d(n)和欧拉(Euler)函数它的计算公式。
1． 高斯(Gauss)取整函数[]
设是实数，不大于的最大整数称为的整数部分，记为[记为｛｝。例如：［0.5］＝0，由性质1.性质2.性质3.设性质4.
，则
;
的定义可得如下性质：
； ；
；
;
]；
称为的小数部分，
等等。
和
性质5. ；
性质6.对于任意的正整数，都有如下的埃米特恒等式成立：
为了描述性质7，我们给出如下记号：若
。例如：我们有
a1a2ak； ，且
，则称为
恰好整除，记为
等等，其实，由整数唯一分解定理：任何大于1
的整数a能唯一地写成a?p1p2?pk,i?1,2,,?,k的形式，其中pi为质（素）数（pi?pj(i?j)）。我们还可以得到：性质7.若
，则
。
请注意，此式虽然被写成了无限的形式，但实际上对于固定的，必存在正整数，使得
，因而
，故
，而且对于
时，都有
。因此，
上式实际上是有限项的和。另外，此式也指出了乘数的计算方法。 2．除数函数d(n)
的标准分解式中，素因数的指数
正整数的正因数的个数称为除数函数，记为d(n)。这里给出d(n)的计算公式：
d(n)＝，为素数唯一分解定理中的指数。为了叙述
地更加明确，我们组出素数唯一分解定理。
算术基本定理（素数唯一分解定理）：任何一大于1的整数均可以分解为素数的乘积，
若不考虑素数乘积的先后顺序，则分解式是唯一的。
例如：。当一个整数分解成素数的乘积时，其中有些素数可以重复出现。例如在上面的分解式中，2出现了三次。把分解式中相同的素数的积写成幂的形式，我们就可以把大于1的正整数写成
（1）
此式称为的标准分解式。这样，算术基本定理也可以描述为大于1的整数的标准分解式是唯一的（不考虑乘积的先后顺序）。
推论1.若的标准分解式是（1）式，则
应说明（2）不能称为是能不含有某个素因数
推论2.设
是的正因数的充要条件是： （2）
的标准分解式，，其原因是其中的某些
）
，若是整数的次方，则也是整数的平方。
也是整数的次方。特别可能取零值（
也有可
，因而，且
地，若是整数的平方，则
3. 欧拉(Euler)函数设正整数0,1，??的标准分解式是 例如：
以下我们讲述同余的概念：
中与互素的个数，称之为的欧拉函数，并记为
，则
的计算公式是：
；
.
。若
同余的概念是高斯（Gauss）在1800年左右给出的。设所得的余数相同，则称为与关于模于模
不同余。
，若对模
同余，记作
是正整数，若用去除整数，
，否则，称为与关
定义1.（同余）设若不然，则称
和
，则称和对模
不同余，记作
同余，记作。例如：
；，
等等。
当
时，
，则称是对模
的最小非负剩余。
除得的余数相同。对于
由带余除法可知，和对模同余的充要条件是与被固定的模，模的同余式与通常的等式有许多类似的性质：
性质1.
的充要条件是
也即
。
性质2.同余关系满足以下规律： （1）（反身性）（2）（对称性）若（3）（传递性）若（4）（同余式相加）若（5）（同余式相乘）若
； ，则，
，，
； ，则
，则，则
；
；
；
反复利用（4）（5），可以对多个两个的（模相同的）同余式建立加、减和乘法的运算公式。特别地，由（5）易推出：若
，
为整数且
，则
；
但是同余式的消去律一般并不成立，即从是我们却有以下结果： （6）若
，则
未必能推出，可
，由此可以推出，若，则有
，即在与
次说明了互素的重要性）。
互素时，可以在原同余式两边约去而不改变模（这一点再一
现在提及几个与模相关的简单而有用的性质： （7）若（8）若（9）若
两两互素时，则有
，，
｜
，则，则，则
；
；
；
，特别地，若
性质3.若，则；；
性质4.设是系数全为整数的多项式，若，则。
这一性质在计算时特别有用：在计算大数字的式子时，可以改变成与它同余的小的数字，使计算大大地简化。如例3。 定义2.设
，
是使
成立的最小正整，则称
为对模
的阶。
在取定某数后，按照同余关系把彼此同余的整数归为一类，这些数称为模的剩余类。一个类的任何一个数，都称为该类所有数的剩余。显然，同类的余数相同，不同类的余数不相同，这样我们就把全体整数按照模划分为了个剩余类：
。在上述的
余，可以得到
个数
，称为模
个剩余类中，每一类任意取一个剩
的一个完全剩余系。例如关系模7，下面的
每一组数都是一个完全剩余系：
0，1，2，3，4，5，6； -7，8，16，3，-10，40，20；
显然，一组整数成为模于模
-3，-2，-1，0，1，2，3。
的完全剩余系只需要满足两个条件（1）有
;即除数为
个数；（2）各数关时，余数可能取到的
两两不同余。最常用的完全剩余系是最小非负完全剩余系及绝对值最小完全剩余系。
模的最小非负完全剩余系是：0，1，2，???,
数的全部值。 当
为奇数时，绝对值最小的完全剩余系是：
；
当为偶数时，绝对值最小的完全剩余系有两个：
； 。
以上只是我们个人对同余及剩余类的理解，为了方便大家研究，我们把有关材料上的具体概念给出，希望大家好好地研究： 定义3.（同余类）设为模
的同余类。
说明：整数集合可以按模
来分类，确切地说，若和模
同余，则
和
属同一
，每一个这样的类
类，否则不属于同一类，每一个这样的类为模恰与0,1,……，因此模
共有
中的一个模
的一个同余类。由带余除法，任一整数必
这
个数彼此模
不同余，
。
同余，而0,1,……，
个不同的同余类，即
例如，模2的同余类共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式和
（为任意整数）。
是正整数，把全体整按对模，其中
的余数分成
类，相应的，称为模
个集合的一个
定义4。（剩余类）设记为：
剩余类。以下是几条常用性质： （1）
且
； 的一个里；
，则
的充要条件是
称为模
。
的完全剩余系，如果对任意有且仅
（2）每一个整数仅在（3）对于任意
定义5.（完全剩余系）一组数有一个设
是对模
为模
的剩余，即
。换一种说法更好理解： 中任取一个
，得
个数
组
的全部剩余类，从每个
成的数组，叫做模的一个完全剩余系。
说明：在个剩余类中各任取一个数作为代表，这样的余系，简称模彼此模完系。
的完系。换句话说，
个数
是模
个数称为模的一个完全剩
称为模的一个完系，是指它们
的最小非负
不同余，例如0,1，2，……，的一个完系，这称作是模
