初等数论中的几个重要定理(竞赛必备)

1、初等数论中的几个重要定理 根底知识定义欧拉(Euler)函数一组数称为是模的既约剩余系，如果对任意的，且对于任意的，假设1，那么有且仅有一个是对模的剩余，即。并定义中和互质的数的个数，称为欧拉Euler函数。这是数论中的非常重要的一个函数，显然，而对于，就是1,2，中与互素的数的个数，比方说是素数，那么有。引理：；可用容斥定理来证证明略。定理1：欧拉Euler定理设1，那么。分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于1，从而也是与互质的个数，且两两余数不一样，故，而1，故。 证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯

2、一的一个，使得，这种对应关系是一一的，从而，。，故。证毕。这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。定理2：费尔马Fermat小定理对于质数及任意整数有。设为质数，假设是的倍数，那么。假设不是的倍数，那么由引理及欧拉定理得，由此即得。定理推论：设为质数，是与互质的任一整数，那么。定理3：威尔逊Wilson定理设为质数，那么。分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。证明：对于，在中，必然有一个数除以余1，这是因为那么好是的一个剩余系去0。从而对，使得；假设，那么，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以

3、余1，然后有，使，即与它自己配对，这时，或，或。除外，别的数可两两配对，积除以余1。故。定义：设为整系数多项式，我们把含有的一组同余式称为同余方组程。特别地，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.假设整数同时满足：，那么剩余类其中称为同余方程组的一个解，写作定理4：中国剩余定理设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为：这里，以及满足，即为对模的逆。中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。定理5：拉格郎日定理设是质数，是非负整数，多项式是一个模为次的整系数多项式即 ，那么同余方程至

4、多有个解在模有意义的情况下。定理6：假设为对模的阶，为某一正整数，满足，那么必为的倍数。以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧那么是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到意想不到的作用，如：，。这里我们只介绍几个较为直接的应用这些定理的例子。典例分析例1.设，求证：。证明：因为，故由知，从而，但是，故由欧拉定理得：，从而；同理，。于是，即。注明：现考虑整数的幂所成的数列：假设有正整数使，那么有，其中；因而关于，数列的项依次同余于这个数列相继的项成一段，各段是完全相同的，因而是周期数列。如下例：例2试求不大于100，

5、且使成立的自然数的和。解：通过逐次计算，可求出关于的最小非负剩余即为被11除所得的余数为：因而通项为的数列的项的最小非负剩余构成周期为5的周期数列：3，9，5，4，1，3，9，5，4，1，类似地，经过计算可得的数列的项的最小非负剩余构成周期为10的周期数列：7，5，2，3，10，4，6，9，8，1，于是由上两式可知通项为的数列的项的最小非负剩余，构成周期为10即上两式周期的最小公倍数的周期数列：3，7，0，0，4，0，8，7，5，6，这就说明，当时，当且仅当时，即；又由于数列的周期性，故当时，满足要求的只有三个，即从而当时，满足要求的的和为：.下面我们着重对Fetmat小定理及其应用来举例：例

6、3求证：对于任意整数，是一个整数。证明：令，那么只需证是15的倍数即可。由3，5是素数及Fetmat小定理得，那么；而3，5=1，故，即是15的倍数。所以是整数。例4求证：为任意整数。证明：令，那么；所以含有因式由Fetmat小定理，知13|7|又13，7，5，3，2两两互素，所以2730=能整除。例5设是直角三角形的三边长。如果是整数，求证：可以被30整除。证明：不妨设是直角三角形的斜边长，那么。假设2  ，2  ，2  c，那么，又因为矛盾！所以2|.假设3  ，3  ，3  c，因为，那么，又，矛盾！从而3|.假设 5 

7、0;，5  ，5  c，因为，所以或0(mod5)与矛盾！从而5|.又(2,3,5)=1，所以30|.下面讲述中国剩余定理的应用例6证明：对于任意给定的正整数，均有连续个正整数，其中每一个都有大于1的平方因子。证明：由于素数有无穷多个，故我们可以取个互不相同的素数，而考虑同余组     因为显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续个数分别被平方数整除。注：1此题的解法表达了中国剩余定理的一个根本成效，它常常能将“找连续个正整数具有某种性质的问题转化为“找个两两互素的数具有某种性质，而后者往往是比拟容易解决

8、的。   2此题假设不直接使用素数，也中以采用下面的变异方法：由费尔马数两两互素，故将中的转化为后，相应的同余式也有解，同样可以导出证明。例7证明：对于任意给定的正整数，均有连续个正整数，其中每一个都不是幂数。分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。证明：取个互不相同的素数，考虑同余组因为显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。对于因为，故，但由式可知 ，即在的标准分解中恰好出现一次，故都不是幂数。例8 设是给定的偶数，且是偶数。证明：存在整数使得，且。证明：我们先证明，当为素数幂时结论成立。实际上，能够证明，存在使 且：假设，那么条件说明为偶数，此时可取；假设，那么与中有一对满足要求。一般情形下，设是的一个标准分解，上面已经证明，对每个存在整数使得且，而由中国剩余定理，同余式