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