初等数论中的几个重要定理(竞赛必备)
温柔似野鬼°
634次浏览
2021年01月26日 06:19
最佳经验
本文由作者推荐
春夜宴桃李园序-
初等数论中的几个重要定理
(
竞
赛必备
)
初等数论中的几个重要定理
基础知识
定义（欧拉
(Euler)
函数）一组数
为是模
的既约剩余系，如果对任意的
且对于任意的
，若
有一个
是
对模的剩余，即
中和
互质的数的个数，
拉（
Euler
）函数。
这是数论中的非常重要的一个函数，显然
，
而对于
，
就是1,2
，
…，
中与
互
。
素的数的个数，比如 说
是素数，则有
称
，
＝
1
，则有且仅
。并定义称为欧
引理：
明略）。
；
可用容斥定理来证
（证
定理
1
：（ 欧拉（
Euler
）定理）设
则
。
＝
1
，
分析与解答：要证
找出互质的
个
相乘，
由
的个数：
也是与
互质的
不一 样，故
（
），而（
，我们得设法
中与
＝
1
，从而< br>，由于
个数我们想到
个数，且两两余数
）＝
1
，故
。
证明：取模
的一个既约剩余系
，考虑故
是对每个
得
，由于
与
互质，
，于
，使
仍与
互质，且有
都能找到唯一的一个
，这种对应关系
是一一的，从而
，
。
，
，故
。证毕。
这是数论证明题中常用的一种方法，
使用 一组
剩余系，
然后乘一个数组组成另外一组剩余系来
解决问题。
定理
2
：（费尔马（
Fermat
）小定理） 对于
质数
及任意整数
有
。
。
设
为质数， 若
是
的倍数，则
若
不是
的倍数，则
，
由引理及欧拉 定理得
，由此即得。
定理
推论：设
为质数，
是与
互质的任
一整数，则
。
定理< br>3
：（威尔逊（
Wilson
）定理）设
为
质数，则
。
分析与解答：
受欧拉定理的影响，
我们也找
个数，然后来对应乘法。
证明：对于
一个剩余系去
0
。
从而对
；
，使得
，在
中，必然有< br>则好是
的
一个数除以
余
1
，
这是因为
若
，故对于
，
，则
，有
，
。
中数可
，
。
即对于不同的
对应于不 同的
，
即
两两配对，
其积除以
余
1
，
然后 有
，
使
即与它自己配对，这时
，
除
1
。故
定义：设
或
，
，
或
外，
别的数可两两 配对，
积除以
余
。
为整系数多项式（
（
），我们 把
）称为同
含有
的一组同余式
余方组程。特别地，，当
若整数
同时满足：
，则剩余类
均为
的一次整系数
（其中多项式时，该同余方程组称为一次同余方程组
.
）称为同余方程组的一个解，写作
定理
4
：
（中国剩余定理）设
互素的正整数，
那 么对于任意整数
是两两
，
一次
同余方程组
为：
，
必有解，
且解可以写
这里
，，
，以及
满足
（即
为
对模
的逆）。
中国定理的作用在于它能断言所说的同余式
组当模两两互素时一定有解，
而对于解的形式并不重要。
定理
5
：（拉格郎日定理）设
是质数，
是
非负整数，多项式
次的整系数多项式（即
下）。
定理
6
：
若
为
对模
的阶，< br>为某一正整数，
满足
，则
必为
的倍数。
是一个模
为
），则同余方程
至多有
个解（在模
有意义的情况
以上介绍的只是一些系统的知识、
方法，
经常在
解决数论问题中起着突破难点 的作用。
另外还有
一些小的技巧则是在解决、
思考问题中起着排除
情况、辅助分析等作用，
有时也会起到意想不到
的作用，
如：
例子。
典例分析
例
1.
设
证明：因为
，但是
，
。
于是，
，即
。
，求证：
，故由
。
知
，
从而
，从而
；
同理，
，
。这
里我 们只介绍几个较为直接的应用这些定理的
，故由欧拉定理得：
注明：现考虑整数
的幂< br>所成的数列：
若有正整数
使
；
，则有
，其中