初等数论

所以因为而

即

是奇数，易知；

，于是

与

中有一个是

，另一个是

，

另一方面，得

所以，以

为边的三角形都是直角三角形，其面积等于

是平方数，

但是，于是构造出了一个面积更小的勾股三角形，矛盾！

初等数论中的几个重要定理

基础知识

定义（欧拉(Euler)函数）一组数意的对模个数，

，的剩余，即

且对于任意的

。并定义

称为是模，若

的既约剩余系，如果对任

是

＝1，则有且仅有一个

中和

互质的数的

称为欧拉（Euler）函数。

，而对于是素数，则有

，

。

就是

这是数论中的非常重要的一个函数，显然1,2，?，

中与

互素的数的个数，比如说

引理：；可用容斥定理来证（证明略）。

＝1，则，我们得设法找出

互质的

的个数：

。

个相乘，由，由于

个＝1，从

定理1：（欧拉（Euler）定理）设 分析与解答：要证数我们想到

中与

而也是与互质的个数，且两两余数不一样，故

（

），而

（

证明：取模由于与对每个

）＝1，故的一个既约剩余系

仍与

。

，考虑

互质，且有

，使得

，，于是，这种对

互质，故

都能找到唯一的一个

应关系是一一的，从而，

。

，

组剩余系来解决问题。

，故。证毕。

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

定理2：（费尔马（Fermat）小定理）对于质数

设

为质数，若是

的倍数，则

及任意整数有

。若不是，

。

的倍数，则

，

由引理及欧拉定理得

由此即得。 定理

推论：设

为质数，是与

互质的任一整数，则为质数，则

。 。

定理3：（威尔逊（Wilson）定理）设

分析与解答：受欧拉定理的影响，我们也找 证明：对于为

从而对 若

，

，则

，在则好是

个数，然后来对应乘法。 中，必然有一个数除以

余1，这是因

的一个剩余系去0。

，使得

，

；

，

故对于即

，有 。即对于不同的对应于不同的

余1，然后有，使，

，

，

中数可两两配对，其积除以，即与

或

它自己配对，这时

，

除

或

。

外，别的数可两两配对，积除以

。

余1。故

定义：设为整系数多项式（（

），我们把含有的一组同余式均为的一次整同时满足：

）称为同余方组程。特别地，，当

系数多项式时，该同余方程组称为一次同余方程组.若整数

，则剩余类

同余方程组的一个解，写作 定理4：（中国剩余定理）设数

，一次同余方程组

（其中

）称为

是两两互素的正整数，那么对于任意整，

必有解，且解可以写为：

这里

（即

为

，对模

的逆）。

，以及满足，

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

定理5：（拉格郎日定理）设

是一个模

余方程

是质数，

是非负整数，多项式

），则同

为次的整系数多项式（即

有意义的情况下）。

至多有个解（在模

定理6：若为对模的阶，为某一正整数，满足，则必为的

倍数。

以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到意想不到的作用，如：

，

。这里我们只介绍几个较为直接的应用这些定理的例子。 典例分析 例1.设证明：因为

，求证：，故由

，故由欧拉定理得：

从而于是，

注明：现考虑整数

，则有

因而关于

，数列

的幂；同理，

，即

所成的数列：

，其中

的项依次同余于

。

。

知。

，从而

，

，但是

，

若有正整数；

使

这个数列相继的项成一段，各段是完全相同的，因而是周期数列。如下例： 例2．试求不大于100，且使解：通过逐次计算，可求出为：

因而通项为

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

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

类似地，经过计算可得

的数列的项的最小非负剩余构成周期为10的周期数列：

关于

成立的自然数的和。

的最小非负剩余（即为被11除所得的余数）

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

于是由上两式可知通项为

的数列的项的最小非负剩余，构成周期为10（即上

两式周期的最小公倍数）的周期数列：

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