酒烧吢头性质：（1）个整数构成模的一个完全剩余系，则与
两两对模不同余；
的完全剩余系。
（2）若同时跑遍模
第五节 初等数论中的几个重要定理
基础知识
定义（欧拉(Euler)函数）一组数
，
的剩余，即
且对于任意的
。并定义
称为是模，若
的既约剩余系，如果对任意的
是对模
＝1，则有且仅有一个
中和
互质的数的个数，
称为欧拉（Euler）函数。
这是数论中的非常重要的一个函数，显然中与引理：
互素的数的个数，比如说
，而对于
，。
就是1,2，?，
是素数，则有
；可用容斥定理来证（证明略）。
定理1：（欧拉（Euler）定理）设证明：取模互质，故
的一个既约剩余系
仍与
＝1，则
，考虑
互质，且有
，使得
。
，由于与，于是对每个，这种对应关系
是
都能找到唯一的一个
一一的，从而，。
，，故。证毕。
分析与解答：要证想到
中与
互质的也是与
，我们得设法找出的个数：互质的
个相乘，由，由于
个数我们＝1，从而
个数，且两两余数不一样，故
（
），而
（）＝1，故。
这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
定理2：（费尔马（Fermat）小定理）对于质数
设
为质数，若是
的倍数，则
，
互质的任一整数，则为质数，则
及任意整数有
。若不是
。
的倍数，则
，由此即得。 。 。
由引理及欧拉定理得定理
推论：设
为质数，是与
定理3：（威尔逊（Wilson）定理）设
分析与解答：受欧拉定理的影响，我们也找证明：对于
，在则好是
从而对 若对于
，，有
，则
个数，然后来对应乘法。 中，必然有一个数除以
余1，这是因为
的一个剩余系去0。
，使得
，
。即对于不同的
余1，然后有，使
，
或
对应于不同的
；
，故，即
中数可两两配对，其积除以
己配对，这时
或
除定义：设
。
，
，即与它自
，
外，别的数可两两配对，积除以为整系数多项式（（
余1。故
），我们把含有
。
的一组同余式
）称为同余方组程。特别地，，当均为的一次整系数
）称为同
多项式时，该同余方程组称为一次同余方程组.若整数同时满足：
，则剩余类
余方程组的一个解，写作定理4：（中国剩余定理）设
（其中
是两两互素的正整数，那么对于任意整数
，一次同余方程组，必有解，且解可以写为：
这里，，以及满足，
（即为对模的逆）。
中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。
定理5：（拉格郎日定理）设是一个模解（在模
是质数，是非负整数，多项式
），则同余方程
至多有
个
为次的整系数多项式（即有意义的情况下）。
定理6：若为对模的阶，为某一正整数，满足，则必为的倍数。
以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到意想不到的作用，如：
，
。这里我们
只介绍几个较为直接的应用这些定理的例子。
下面我们着重对Fetmat小定理及其应用来举例： 例3．求证：对于任意整数，证明：令
由3，5是素数及Fetmat小定理得
；
而（3，5）=1，故例4．求证：证明：令所以
含有因式
7|
能整除
，即
（为任意整数）。 ，则
。
；
是15的倍数。所以
，则只需证
，
是一个整数。
是15的倍数即可。 ，则
是整数。
由Fetmat小定理，知13|
又13，7，5，3，2两两互素，所以2730=
例5．设是直角三角形的三边长。如果是整数，求证：
。 ，又因为
可以被30整除。
证明：不妨设是直角三角形的斜边长，则若2 ，2 ，2 c，则所以2|若3 . ，3 ，3 c，因为
.
，矛盾！
矛盾！
，则，又
，矛盾！从而3|
若 5 ，5 ，5 c，因为所以从而5|
.
或0(mod5)与
，
又(2,3,5)=1，所以30|. 下面讲述中国剩余定理的应用
例6．证明：对于任意给定的正整数，均有连续个正整数，其中每一个都有大于1的平方因子。
证明：由于素数有无穷多个，故我们可以取个互不相同的素数组因为
于是，连续个数
①
显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。
分别被平方数
整除。
，而考虑同余
注：（1）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续个正整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较容易解决的。
（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数
两两互素，故将①中的
转化为
后，相应的同余式也
有解，同样可以导出证明。
例7．证明：对于任意给定的正整数，均有连续个正整数，其中每一个都不是幂数。 分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。 证明：取个互不相同的素数因为对于
因为
，考虑同余组
显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。
，故
，但由①式可知
，即
在
的标准分解中恰好出现一次，故
例8． 设
是给定的偶数，
使得
且
是偶数。 ，且
都不是幂数。
证明：存在整数。
使
证明：我们先证明，当为素数幂 若若
且
：
时结论成立。实际上，能够证明，存在
，则条件表明为偶数，此时可取，则
与
；
中有一对满足要求。
是的一个标准分解，上面已经证明，对每
一般情形下，设个
存在整数
使得
且
，而由中国剩余定理，
①有解， ②有解
。 ，
，
同余式同余式现不难验证解于是故
符合问题中的要求：因，又由①②知
。
，故
注：此题的论证表现了中国剩余定理最为基本的作用：将一个关于任意正整数的问题，化为为素数幂的问题，而后者往往是比较好处理的。
第六节 不定方程
所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些（如要求是有理数、整数或正整数等等）的方程或方程组。不定方程也称为丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。不定方程的重要性在数学竞赛中也得到了充分的体现，每年世界各地的数学竞赛吉，不定方程都占有一席之地；另外它也是培养学生思维能力的好材料，数学竞赛中的不定方程问题，不仅要求学生对初等数论的一般理论、方法有一定的了解，而且更需要讲究思想、方法与技巧，创造性的解决问题。在本节我们来看一看不定方程的基础性的题目。
基础知识
1．不定方程问题的常见类型： （1）求不定方程的解；
