文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 初等数论中的几个重要定理

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

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
初等数论中的几个重要定理
基础知识
定义（欧拉(Euler函数）一组数
且对于任意的
。并定义
数。
这是数论中的非常重要的一个函数，显然与
互素的数的个数，比如说
是素数，则有
，而对于
。
，
就是1,2，„，
中
，若
称为是模
的既约剩余系，如果对任意的
是
对模
，
＝1，则有且仅有一个中和
互质的数的个数，
的剩余，即
称为欧拉（Euler）函
引理：；可用容斥定理来证（证明略）。
＝1，则，我们得设法找出
的个数：
，由于
。个相乘，由＝1，从而
个数我们想到
也是与
定理1：（欧拉（Euler）定理）设分析与解答：要证
中与互质的
（
证明：取模故个
互质的
个数，且两两余数不一样，故
），而（的一个既约剩余系仍与
互质，且有

）＝1，故
，考虑，于是对每个
，这种对应关系
。
，由于与
互质，
都能找到唯一的一是一一的，从而
，使得
，。
，，故。证毕。
这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
定理2：（费尔马（Fermat）小定理）对于质数
设
为质数，若是
的倍数，则
，
及任意整数有
。若不是
的倍数，则
。
由引理及
欧拉定理得，由此即得。

定理推论：设为质数，是与互质的任一整数，则
。
。
定理3：（威尔逊（Wilson）定理）设为质数，则分析与解答：受欧拉定理的影响，我们也找证明：对于则好是
，在
个数，然后来对应乘法。
余1，这是因为
中，必然有一个数除以
的一个剩余系去0。
，使得
，
，有

，则
；，
，故对于
中数
，
从而对若
。即对于不同的对应于不同的，即
，即与它自己配对，这时
，
或余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，„„„
于是由上两式可知通项为最小公倍数）的周期数列：
3，7，0，0，4，0，8，7，5，6，„„„
这就表明，当
时，当且仅当
时，
，即
；
的数列的项的最小非负剩余，构成周期为10（即上两式周期的

又由于数列的周期性，故当时，满足要求的只有三个，即

从而当时，满足要求的的和为：
.
下面我们着重对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．设
是给定的偶数，
使得
证明：存在整数
证明：我们先证明，当为素数幂若若
且
：
时结论成立。实际上，能够证明，存在
，则条件表明为偶数，此时可取，则
与
；
中有一对满足要求。
是的一个标准分解，上面已经证明，对每个
存在整
一般情形下，设数
使得
且
，而由中国剩余定理，

同余式同余式现不难验证解于是故
①有解，②有解。
符合问题中的要求：因，又由①②知
。
，故
，
，
注：此题的论证表现了中国剩余定理最为基本的作用：将一个关于任意正整数的问题，化为为素数幂的问题，而后者往往是比较好处理的。

本文来源：https://www.2haoxitong.net/k/doc/87ae9e35ee06eff9aef8076e.html

《初等数论中的几个重要定理.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

法律文秘应届生个人简历范文 2019学习井冈山精神心得体会600字范文15篇 高一班主任工作计划模板2021(最新版) 部分暨南大学金融系导师资料() 新学期学习计划500字3篇(完整版) 幼儿教师师德师风演讲稿15篇 幼儿园数学活动游戏化的意义与实施方法 大月份引产及注意事项 禾苗造句 树枝在林中互相碰触着,绿叶在狂风里 仿写 描写思念亲人的诗句_1499
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号