初等数论中的几个重要定理
萌到你眼炸
637次浏览
2021年01月29日 14:27
最佳经验
本文由作者推荐
议论文的写法-天亮了简谱
初等数论中的几个重要定理
基础知识
定义
（欧拉
(Euler)
函数）
一组数
且对
于
任
意
的
。并定义
数。
这是数论 中的非常重要的一个函数，显然
与
互素的数的个数，比如说
是素数，则有
，而 对于
。
，
就是
1,2
，„，
中
，
若
称为是模
的既约剩余系，
如果对任意的
是
对
模
，
＝
1
，
则
有
且
仅
有
一
个
中和
互质的数的个数，
的
剩
余
，
即
称为 欧拉（
Euler
）函
引理
：
；可用容斥定理来证（证明略）
。
＝
1< br>，则
，我们得设法找出
的个数：
，由于
。
个
相乘，由
＝
1
，从而
个数我们想到
也是与
定理
1
：
（欧拉（
Euler
）定理）设
分析与解答：要证
中与
互
质
的
（
证明：
取模
故
个
互质的
个
数
，
且
两
两
余
数
不
一
样
，
故
）
，而（
的一个既约剩余系
仍与
互质，
且有
）＝
1
，故
，
考虑
，
于是对每个
，
这
种
对
应
关
系
。
，
由于
与
互质，
都能找到唯一的一
是
一
一
的
，
从
而
，
使
得
，
。
，
，故
。证毕。
这是数论证明题中常用的一种方法，使用一组剩余 系，然后乘一个数组组成另外一组剩余系来
解决问题。
定理< br>2
：
（费尔马（
Fermat
）小定理）
对于质数
设
为质数，若
是
的倍数，则
，
及任意整数
有
。若不是
的倍数，则
。
由引理及
欧拉定理得
，由此即得。
定理推论
：设
为质数，
是与
互质的任一整数，则
。
。
定理
3
：
（威尔逊（
W ilson
）定理）
设
为质数，则
分析与解答：受欧拉定理的影响，我们也找
证明：
对于
则好是
，
在
个数，然后来对应乘法。
余
1
，
这是因为
中，
必然有一个数除以
的一个剩余 系去
0
。
，使得
，
，有
，
则
；
，
，
故
对
于
中数
，
从而对
若
。即对于不同的
对应于不同的，即
，
即与它自己配对，
这时
，
或
余
1
。故
。
。
（
可两两配对，
其积除以
余
1
，
然后有
，
使
，
或
除
定义：
设
外，别的数可两两配对，积除以
为整系数多项式
（< br>）
，
我们把含有
的一组同余式
）
称为同余方组程。特别地，< br>，当
程组
.
若整数
同时满足：
，则剩余类
解，写作< br>
均为
的一次整系数多项式时，该同余方程组称为一次同余方
（其中
）称为同余方程组的一个
定理
4
：（中国剩余定理）
设
一次同余方程组
，
是两两互素的正整数，
那 么对于任意整数
必有解，且解可以写为：
，
这里
对模
的逆）
。
，
，
以及
满 足
，
（即
为
中国定理的作用在于它能断言所说的同余式组当模两两互素时一定 有解，而对于解的形式并
不重要。
定理
5
：
（拉格郎日定理）
设
是质数，
是非负整数，多项式
是一个
模
为
次的整系数多项式（即
）
，则同余方程
至多有
个解（在模
有
意义的情况下）
。
定理
6
：若
为
对模
的阶，
为某一正整数，满足
，则
必 为
的倍数。
以上介绍的只是一些系统的知识、
方法，
经常在解决数 论问题中起着突破难点的作用。
另外还有一
些小的技巧则是在解决、
思考问题中起着排 除情况、
辅助分析等作用，
有时也会起到意想不到的作
用，如：
这些定理的例 子。
典例分析
例
1.
设
证明：
因为
，求证：
，
故由
知
。
，从而
，
，
从
而
，
但是
，
；
同
理
，
，
。这里我们只介绍几个较为直接的应用
故
由
欧
拉
定
理
得
：
。
于是，
注明： 现考虑整数
，其中
因而关于
，
数列
的幂
，即
所成的 数列：
；
。
若有正整数
使
，则有
的项 依次同余于
这个数列相继的
项成一段，各段是完全相同的，因而是周期数列。如下例：
例
2
．试求不大于
100
，且使
解：通过逐次计算，可求出
关于
成立的自然数
的和。
的最小非负剩余（即为被
11
除所得的余数）为：
因而通项为
的数列的项的最小非负剩余构成周期为
5
的周期数列：
3
，
9
，
5
，
4
，
1
，
3
，
9
，
5
，
4
，
1
， „„„
类似地，经过计算可得
的数列的项的最小非负剩余构成周期为
10< br>的周期数列：
7
，
5
，
2
，
3< br>，
10
，
4
，
6
，
9
，
8
，
1
，„„„
于是由上两式可知通项为
最小公倍数）的周期数列：
3
，
7
，
0
，
0
，
4
，
0
，
8
，
7
，
5
，
6
，„„„
这就表明，当
时，当且仅当
时，
，即
；
的数列的项的最小非负剩余，构成周期为
10
（即上两式周期的