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

初等数论中的几个重要定理初等数论中的几个重要定理 基础知识 定义一组数的，的剩余，即且对于任意的。并定义，若称为是模的既约剩余系，如果对任意是对模1，则有且仅有一个中和互质的数的个数，称为欧拉函数。 这是数论中的非常重要的一个函数，显然中与互素的数的个数，比如说，而对于，。 就是1,2，是素数，则有 引理：；可用容斥定理来证。 定理1：定理）设1，则。 分析与解答：要证我们想到中与互质的互质的，我们得设法找出的个数：个相乘，由，由于个数1，从而也是与个数，且两两余数不一样，故，而1，故。 证明：取模于与个互质，故的一个既约剩余系仍与互质，且有，使得，考虑，由，于是对每，这种对应关系都能找到唯一的一个是一一的，从而，。 ，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：小定理）对于质数及任意整数有。 设为质数，若是的倍数，则，。若不是的倍数，则，由此即得。 由引理及欧拉定理得 定理推论：设为质数，是与互质的任一整数，则。 定理3：定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于则好是，在的一个剩余系去0。 中，必然有一个数除以余1，这是因为 从而对，使得； 若对于，有，则，。即对于不同的对应于不同的，故，即中数可两两配对，其积除以己配对，这时或。 ，余1，然后有，使，或，即与它自， 除外，别的数可两两配对，积除以余1。故。 定义：设为整系数多项式，我们把含有的一组同余式均为的一次整系）称为同余方组程。特别地，当数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：，则剩余类余方程组的一个解，写作称为同 定理4：设，一次同余方程组是两两互素的正整数，那么对于任意整数，必有解，且解可以写为： 这里。 ，以及满足，中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：设是一个模是质数，是非负整数，多项式），则同余方程至多为次的整系数多项式。 有个解为： 因而通项为的数列的项的最小非负剩余构成周期为5的周期数列： 3，9，5，4，1，3，9，5，4，1， 类似地，经过计算可得的数列的项的最小非负剩余构成周期为10的周期数列： 7，5，2，3，10，4，6，9，8，1， 于是由上两式可知通项为式周期的最小公倍数）的周期数列： 的数列的项的最小非负剩余，构成周期为10=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 ，5 ，5 c，因为， 所以或0(mod5)与矛盾！ 从而5|. 又(2,3,5)=1，所以30|. 下面讲述中国剩余定理的应用 例6证明：对于任意给定的正整数，均有连续个正整数，其中每一个都有大于1的平方因子。 证明：由于素数有无穷多个，故我们可以取个互不相同的素数组 ，而考虑同余因为于是，连续个数显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。分别被平方数整除。 注：本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续个正整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较容易解决的。 本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数两两互素，故将中的有解，同样可以导出证明。 转化为后，相应的同余式也例7证明：对于任意给定的正整数，均有连续个正整数，其中每一个都不是幂数。 分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。 证明：取个互不相同的素数，考虑同余组 因为显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。 对于在因为，故，但由式可知 ，即的标准分解中恰好出现一次，故都不是幂数。 例8 设是给定的偶数，且是偶数。 证明：存在整数使得，且。 证明：我们先证明，当为素数幂时结论成立。实际上，能够证明，存在使 且： 若，则条件表明为偶数，此时可取； 若，则与中有一对满足要求。 一般情形下，设个存在整数使得且是的一个标准分解，上面已经证明，对每，而由中国剩余定理， 同余式 有解， 同余式 有解。 现不难验证解符合问题中的要求：因，故 ， 于是，又由知， 故。 注：此题的论证表现了中国剩余定理最为基本的作用：将一个关于任意正整数的问题，化为为素数幂的问题，而后者往往是比较好处理的。