初等数论

这就表明，当

；

时，当且仅当时，，即

又由于数列的周期性，故当时，满足要求的只有三个，即

从而当时，满足要求的的和为：

.

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

例3．求证：对于任意整数，是一个整数。

证明：令可。

由3，5是素数及Fetmat小定理得

，则只需证是15的倍数即

，；

，则

是15的倍数。所以

是整数。

而（3，5）=1，故例4．求证：证明：令所以

含有因式

7|

，即

（为任意整数）。 ，则

；

由Fetmat小定理，知13|

能整除

是整数，求证：

。

，又因为。

可以被30整除。

又13，7，5，3，2两两互素，所以2730=例5．设

是直角三角形的三边长。如果

证明：不妨设是直角三角形的斜边长，则若2

，2

，2

c，则

矛盾！

所以2|若3

.

，3

，又

若 5 所以从而5|

.

.

，5

，5 或0(mod5)与

c，因为

矛盾！

，3

c，因为，矛盾！从而3|

，

.

， ，则

又(2,3,5)=1，所以30|

下面讲述中国剩余定理的应用

例6．证明：对于任意给定的正整数，均有连续个正整数，其中每一个都有大于1的平方因子。

证明：由于素数有无穷多个，故我们可以取个互不相同的素数同余组因为

于是，连续个数

①

显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。

分别被平方数

整除。

，而考虑

注：（1）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续个正整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较容易解决的。

（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数

两两互素，故将①中的

式也有解，同样可以导出证明。

例7．证明：对于任意给定的正整数，均有连续个正整数，其中每一个都不是幂数。 分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。 证明：取个互不相同的素数因为对于

因为

，考虑同余组

转化为

后，相应的同余

显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。

，故

，但由①式可知

，

即在的标准分解中恰好出现一次，故是给定的偶数，

使得

且

是偶数。 ，且

都不是幂数。

例8． 设

证明：存在整数。

使

证明：我们先证明，当为素数幂 若若

且

：

时结论成立。实际上，能够证明，存在

，则条件表明为偶数，此时可取，则

与

；

中有一对满足要求。

是的一个标准分解，上面已经证明，对

一般情形下，设每个同余式同余式现不难验证解于是故

存在整数

使得

且

，而由中国剩余定理，

①有解， ②有解

符合问题中的要求：因，又由①②知

。

。 ，故

，

，

注：此题的论证表现了中国剩余定理最为基本的作用：将一个关于任意正整数的问题，化为为素数幂的问题，而后者往往是比较好处理的。

同余

同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。 基础知识 三个数论函数

对于任何正整数均有定义的函数，称为数论函数。在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数[x]及其性质，除数函数d(n)和欧拉(Euler)函数

和它的计算公式。

1． 高斯(Gauss)取整函数[]

设是实数，不大于的最大整数称为的整数部分，记为[]；

称为的小数

部分，记为｛｝。例如：［0.5］＝0，等等。 由性质1.性质2.性质3.设性质4.

，则

;

的定义可得如下性质：

； ；

；

;

性质5. ；

性质6.对于任意的正整数，都有如下的埃米特恒等式成立：

为了描述性质7，我们给出如下记号：若记为

。例如：我们有

，且

；

，则称为

恰好整除，

等等，其实，由整数唯一分解定理：任

的形式，其中

。

为质

何大于1的整数能唯一地写成（素）数（

）。我们还可以得到：

性质7.若，则

请注意，此式虽然被写成了无限的形式，但实际上对于固定的，必存在正整数，

使得，因而，故，而且对于时，都有。因

此，上式实际上是有限项的和。另外，此式也指出了乘数的指数

的计算方法。

的标准分解式中，素因数

2．除数函数d(n)

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

，

为素数唯一分解定理中的指数。为了

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