2解：（1）5a?2?2不同余x(mod5)；

222 （2）5a?6?a?2?2或3(mod5)，但x?0或1(mod5)。 6． 求所有满足8?15?17的正整数三元组(x,y,z)。

xyz第五节 初等数论中的几个重要定理

基础知识

定义（欧拉(Euler)函数）一组数x1,x2,?,xs称为是模m的既约剩余系，如果对任意的

1?j?s，(xj,m)?1且对于任意的a?Z，若(a,m)＝1，则有且仅有一个xj是a对模m的剩余，即a?xj(modm)。并定义?(m)?s?{1,2,?,m}中和m互质的数的个数，?(m)称为欧拉（Euler）函数。

这是数论中的非常重要的一个函数，显然?(1)?1，而对于m?1，?(m)就是1,2，?，

m?1中与m互素的数的个数，比如说p是素数，则有?(p)?p?1。

引理：?(m)?m?P为质数1；可用容斥定理来证（证明略）。 （1－）?PP|m?(m)定理1：（欧拉（Euler）定理）设(a,m)＝1，则a?1(modm)。

证明：取模m的一个既约剩余系b1,b2,?,bs,(s??(m))，考虑ab1,ab2,?,abs，由于a与

m互质，故abj(1?j?s)仍与m互质，且有abi abj(?1?i?j?s)，于是对每个

1?j?s都能找到唯一的一个1??(j)?s，使得abj?b?(j)(modm)，这种对应关系?是

一一的，从而

?(ab)??b?jj?1j?1ss(j)(modm)??bj(modm)，?a(?bj)?(?bj)(modm)。

sj?1j?1j?1sss?(m,?bj)?1，?as?1(modm)，故a?(m)?1(modm)。证毕。

j?1s分析与解答：要证a?(m)?1(modm)，我们得设法找出?(m)个n相乘，由?(m)个数我们

想到1,2,?,m中与m互质的?(m)的个数：a1,a2,?,a?(m)，由于(a,m)＝1，从而

aa1,aa2,?,aa?(m)也是与m互质的?(m)个数，且两两余数不一样，故a1?a2???a?(m)?aa1,aa2,?,aa?(m)?a?(m)a1?a2???a?(m)（modm），而

（a1?a2???a?(m)m）＝1，故a?(m)?1(modm)。

这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。

定理2：（费尔马（Fermat）小定理）对于质数p及任意整数a有ap?a(modp)。

设p为质数，若a是p的倍数，则ap?0?a(modp)。若a不是p的倍数，则(a,p)?1由引理及欧拉定理得?(p)?p?1,a?(p)?1(modp)，?ap?1?1(modp),ap?a(modp)，由此即得。

*定理2推论：设p为质数，a是与p互质的任一整数，则?ap?1?1(modp)。

定理3：（威尔逊（Wilson）定理）设p为质数，则(p?1)!??1(modp)。 分析与解答：受欧拉定理的影响，我们也找p?1个数，然后来对应乘法。

证明：对于(x,p)?1，在x,2x,?,(p?1)x中，必然有一个数除以p余1，这是因为

x,2x,?,(p?1)x则好是p的一个剩余系去0。

从而对?x?{1,2,?p?1},?y?{1,2,?,p?1}，使得xy?1(modp)；

若xy1?xy2(modp)，(x,p)?1，则x(y1?y2)?0(modp)，p|(y1?y2)，故对于y1,y2?{1,2,?,p?1}，有xy1 xy2(modp)。即对于不同的x对应于不同的y，即

1,2,?,p?1中数可两两配对，其积除以p余1，然后有x，使x2?1(modp)，即与它自

2己配对，这时x?1?0(modp)，(x?1)(x?1)?0(modp)，x??1或x?1(modp)，

x?p?1或x?1。

modp)。 除x?1,p?1外，别的数可两两配对，积除以p余1。故(p?1)!?(p?1)?1??1(

定义：设fj(x)为整系数多项式（1?j?k），我们把含有x的一组同余式，当fi(x)均为x的一次整系数fj(x)?0(modmj)（1?j?k）称为同余方组程。特别地，

多项式时，该同余方程组称为一次同余方程组.若整数c同时满足：fj(c)?0(modmj)

1?j?k，则剩余类Mc?{x|x?Z,x?c(modm)}（其中m?[m1,m2,?,mk]）称为同

余方程组的一个解，写作x?c(modm)

定理4：（中国剩余定理）设m1,m2,?,mk是两两互素的正整数，那么对于任意整数

a1,a2,?,ak，一次同余方程组x?aj(modmj)，1?j?k必有解，且解可以写为：

x?M1N1a1?M2N2a2???MkNkak(modm)

这里m?m1m2?mk，Mi?m(1?i?k)，以及Nj满足MjNj?1(modmj)，1?j?kmi（即Nj为Mj对模mj的逆）。

中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。

定理5：（拉格郎日定理）设p是质数，n是非负整数，多项式f(x)?anxn???a1x?a0是一个模p为n次的整系数多项式（即p an），则同余方程f(x)?0(modp)至多有n个解（在模p有意义的情况下）。

定理6：若l为a对模m的阶，s为某一正整数，满足a?1(modm)，则s必为l的倍数。 以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到

s1(mod8)n为奇数时?0(mod9)3整除n时。这里我们2意想不到的作用，如：n2??，n????0(mod4)n为偶数时?0(mod3)3不整除n时只介绍几个较为直接的应用这些定理的例子。

典例分析

例1.设(91,ab)?1，求证：91|(a?b)。

1212,a)?1，从而(7,a)?1,(13,a)?1，但是证明：因为91?7?13，故由(91,ab)?1知(91?(7)?6,?(13)?12，故由欧拉定理得：a12?(a6)2?12?1(mod7)，a12?1(mod13)，

从而a12?1(mod91)；同理，b12?1(mod91)。

12于是，a?b12?1?1?0(mod91)，即91|(a12?b12)。

注明：现考虑整数a的幂a所成的数列：a,a2,?,an,?若有正整数k使ak?1(modm)，则有an?ar(modm)，其中n?kq?r,0?r?k；

因而关于mod(m)，数列a,a2,?,an,?的项依次同余于a,a2,?,ak,a,a2,?,ak,a,?这个数列相继的k项成一段，各段是完全相同的，因而是周期数列。如下例： 例2．试求不大于100，且使11|(3n?7n?4)成立的自然数n的和。

解：通过逐次计算，可求出3关于mod11的最小非负剩余（即为被11除所得的余数）为：

nn3?3(mod11),32?9(mod11),33?5(mod11),34?5?3?4(mod11),35?4?3?1(mod11)

因而通项为3的数列的项的最小非负剩余构成周期为5的周期数列：

3，9，5，4，1，3，9，5，4，1，???

类似地，经过计算可得7的数列的项的最小非负剩余构成周期为10的周期数列：

7，5，2，3，10，4，6，9，8，1，???

于是由上两式可知通项为3?7?4的数列的项的最小非负剩余，构成周期为10（即上两式周期的最小公倍数）的周期数列：

3，7，0，0，4，0，8，7，5，6，???

这就表明，当1?n?10时，当且仅当n?3,4,6时，即11|(3?7?4)； 3?7?4?0(mod11)，又由于数列的周期性，故当10k?1?n?10(k?1)时，满足要求的n只有三个，即

nnnnnnnnn?10k?3,10k?4,10k?6

从而当1?n?100时，满足要求的n的和为：

?(10k?3)?(10k?4)?(10k?6)??30k?13?30?k?10?13?30?45?130?1480.

k?0k?0k?0999下面我们着重对Fetmat小定理及其应用来举例：

15137x?x?x是一个整数。 531515137x，则只需证15f(x)?3x5?5x3?7x是15的倍数即可。证明：令f(x)?x?x?

5315例3．求证：对于任意整数x，

由3，5是素数及Fetmat小定理得x?x(mod5)，x?x(mod3)，则

533x5?5x3?7x?3x?7x?0(mod5)；3x5?5x3?7x?2x?x?0(mod3)

而（3，5）=1，故3x?5x?7x?0(mod15)，即15f(x)是15的倍数。所以f(x)是整数。

53