性质2.x?1?[x]?x?[x]?1； 性质3.设a?Z，则[a?x]?a?[x]； 性质4.[x?y]?[x]?[y];{x?y}?{x}?{y};

x?Z??[x]性质5.[?x]?? ；

x?Z?[x]?1?性质6.对于任意的正整数n，都有如下的埃米特恒等式成立： [x]?[x?]?[x?]???[x?1n2nn?1]?[nx]； n??1为了描述性质7，我们给出如下记号：若b?|a，且b a，则称为b恰好整除a，记为

?,53||2000等等，其实，由整数唯一分解定理：任何大于1b?||a。例如：我们有24||2000的整数a能唯一地写成a?p11p22?pkk,i?1,2,,?,k的形式，其中pi为质（素）数（pi?pj(i?j)）。我们还可以得到：pii||a,i?1,2,?,k。 性质7.若p?|n!，则??[]?[aaaanpnn]?[]? 23pp 请注意，此式虽然被写成了无限的形式，但实际上对于固定的n，必存在正整数k，使得p?n，因而0?p?1，故[kknnm?k]?0，而且对于时，都有[]?0。因此，

pkpm上式实际上是有限项的和。另外，此式也指出了乘数n!的标准分解式中，素因数p的指数?的计算方法。

2．除数函数d(n)

正整数n的正因数的个数称为除数函数，记为d(n)。这里给出d(n)的计算公式：

d(n)＝(?1?1)(?2?1)?(?k?1)，?1,?2,?,?k?1为素数唯一分解定理中的指数。为了叙述

地更加明确，我们组出素数唯一分解定理。

算术基本定理（素数唯一分解定理）：任何一大于1的整数均可以分解为素数的乘积，若不考虑素数乘积的先后顺序，则分解式是唯一的。

例如：24?2?2?2?3。当一个整数分解成素数的乘积时，其中有些素数可以重复出现。例如在上面的分解式中，2出现了三次。把分解式中相同的素数的积写成幂的形式，我们就可以把大于1的正整数a写成a?p11p22?pkk,i?1,2,,?,k （1）

此式称为a的标准分解式。这样，算术基本定理也可以描述为大于1的整数的标准分解式是唯一的（不考虑乘积的先后顺序）。

推论1.若a的标准分解式是（1）式，则d是a的正因数的充要条件是：

aaa d?p11p22?pkk,0??i?ai,i?1,2,,?,k （2）

应说明（2）不能称为是d的标准分解式，，其原因是其中的某些?i可能取零值（d也有可能不含有某个素因数pi，因而?i?0）

推论2.设a?bc，且(b,c)?1，若a是整数的k次方，则b,c也是整数的k次方。特别地，若a是整数的平方，则b,c也是整数的平方。

3. 欧拉(Euler)函数?(n)

设n正整数0,1，??n?1中与n互素的个数，称之为n的欧拉函数，并记为?(n)。若n的标准分解式是n?p11p22?pkk,i?1,2,,?,k，则?(n)的计算公式是：

a?1a?1?(n)?p1a?1p2?pk(p1?1)(p2?1)?(pk?1),i?1,2,,?,k

12k???aaa例如：?(2000)??(2453)?2453(2?1)(5?1)?800；

)??(3?23?29)?(3?1)(23?1)(29?1)?1432. ?(2001以下我们讲述同余的概念：

同余的概念是高斯（Gauss）在1800年左右给出的。设m是正整数，若用m去除整数a,b，所得的余数相同，则称为a与b关于模m同余，记作a?b(modm)，否则，称为a与b关于模m不同余。

定义1.（同余）设m?0，若m|(a?b)，则称a和b对模m同余，记作a?b(modm)；

15)，若不然，则称a和b对模m不同余，记作a b(modm)。例如：34?4(mod1000??1(mod7)等等。

当0?b?m时，a?b(modm)，则称b是a对模m的最小非负剩余。

由带余除法可知，a和b对模m同余的充要条件是a与b被m除得的余数相同。对于固定的模m，模m的同余式与通常的等式有许多类似的性质：

性质1. a?b(modm)的充要条件是a?b?mt,t?Z也即m|(a?b)。 性质2.同余关系满足以下规律： （1）（反身性）a?a(modm)；

（2）（对称性）若a?b(modm)，则b?a(modm)；

（3）（传递性）若a?b(modm)，b?c(modm)，则a?c(modm)；

（4）（同余式相加）若a?b(modm)，c?d(modm)，则a?c?b?d(modm)； （5）（同余式相乘）若a?b(modm)，c?d(modm)，则ac?bd(modm)；

反复利用（4）（5），可以对多个两个的（模相同的）同余式建立加、减和乘法的运算公式。特别地，由（5）易推出：若a?b(modm)，k,c为整数且k?0，则akc?bkc(modm)；但是同余式的消去律一般并不成立，即从ac?bc(modm)未必能推出a?b(modm)，可是我们却有以下结果：

（6）若ac?bc(modm)，则a?b??mod??m??，由此可以推出，若(c,m)?1,，则有(m,c)??a?b(modm)，即在c与m互素时，可以在原同余式两边约去c而不改变模（这一点再一

次说明了互素的重要性）。

现在提及几个与模相关的简单而有用的性质： （7）若a?b(modm)，d｜m，则a?b(modd)； （8）若a?b(modm)，d?0，则da?db(moddm)；

（9）若a?b(modmi)(i?1,2,?,k)，则a?b(mod[m1,m2,?,mn])，特别地，若m1,m2,?,mn两两互素时，则有a?b(modm1m2?mn)； 性质3.若ai?bi(modm),i?1,2,?,k，则

?a??b(modm)；?a??biiii?1i?1i?1i?1kkkki；

性质4.设f(x)是系数全为整数的多项式，若a?b(modm)，则f(a)?f(b)(modm)。 这一性质在计算时特别有用：在计算大数字的式子时，可以改变成与它同余的小的数字，使计算大大地简化。如例3。

定义2.设(a,m)?1，d0是使a?1(modm)成立的最小正整，则称d0为a对模m的阶。 在取定某数m后，按照同余关系把彼此同余的整数归为一类，这些数称为模m的剩余类。一个类的任何一个数，都称为该类所有数的剩余。显然，同类的余数相同，不同类的余数不相同，这样我们就把全体整数按照模m划分为了m个剩余类：

dKr?{qm?r|q?Z,0?余数r?m?1}。在上述的m个剩余类中，每一类任意取一个剩

余，可以得到m个数a0,a1,?,am?1，称为模m的一个完全剩余系。例如关系模7，下面的每一组数都是一个完全剩余系：

0，1，2，3，4，5，6； -7，8，16，3，-10，40，20； -3，-2，-1，0，1，2，3。

显然，一组整数成为模m的完全剩余系只需要满足两个条件（1）有m个数；（2）各数关于模m两两不同余。最常用的完全剩余系是最小非负完全剩余系及绝对值最小完全剩余系。模m的最小非负完全剩余系是：0，1，2，???,m?1;即除数为m时，余数可能取到的数的全部值。

当m为奇数时，绝对值最小的完全剩余系是：?m?1m?1,?,?1,0,1,?,； 22当m为偶数时，绝对值最小的完全剩余系有两个：

mm?1,?,?1,0,1,?,； 22mm?,?,?1,0,1,?,?1。 22?以上只是我们个人对同余及剩余类的理解，为了方便大家研究，我们把有关材料上的具体概

念给出，希望大家好好地研究：

定义3.（同余类）设Mr?{x|x?Z,x?r(modm)},r?0,1,?,m?1，每一个这样的类为模m的同余类。

说明：整数集合可以按模m来分类，确切地说，若a和b模m同余，则a和b属同一类，否则不属于同一类，每一个这样的类为模m的一个同余类。由带余除法，任一整数必恰与0,1,……，m?1中的一个模m同余，而0,1,……，m?1这m个数彼此模m不同余，因此模m共有m个不同的同余类，即Mr?{x|x?Z,x?r(modm)},r?0,1,?,m?1。 例如，模2的同余类共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式2k和2k?1（k为任意整数）。

定义4。（剩余类）设m是正整数，把全体整按对模m的余数分成m类，相应的m个集合记为：K0,K1,?,Km?1，其中Kr?{qm?r|q?Z,0?余数r?m?1}，称为模m的一个剩余类。以下是几条常用性质： （1）Z?0?i?m?1?Ki且Ki?Kj??(i?j)；

（2）每一个整数仅在K0,K1,?,Km?1的一个里；

（3）对于任意a,b?Z，则a,b?Kr的充要条件是a?b(modm)。

定义5.（完全剩余系）一组数y1,y2,?,ys称为模m的完全剩余系，如果对任意a有且仅有一个yj是a对模m的剩余，即a?yj(modm)。换一种说法更好理解：