tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

初等数论中的几个重要定理 高中数学竞赛


初等数论中的几个重要定理
基础知识

定义(欧拉(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)函数)一组数 x1 , x 2 ,L ,...


初等数论中的几个重要定理(竞赛必备)

初等数论中的几个重要定理(竞赛必备)_学科竞赛_高中教育_教育专区。初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 的, 的剩余,即 且对于...


个人精心整理!高中数学联赛竞赛平面几何四大定理~及考纲

个人精心整理!高中数学联赛竞赛平面几何四大定理~及考纲_学科竞赛_高中教育_教育专区...简单的初等数论问题,除初中大纲中所包括的内容外,还应包括无穷递降法,同余,欧...


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

第五节初等数论中的几个重要定理_学科竞赛_高中教育_教育专区。第五节基础知识 初等数论中的几个重要定理 定义(欧拉 (Euler)函数)一组数 x1 , x2 ,?, xs ...


全国高中数学联赛竞赛大纲(修订稿)及全部定理内容

3、 几个全国高中数学联赛竞赛大纲及全部定理内容一、平面几何 1、 数学竞赛...7、 简单的初等数论问题,除初中大纲中所包括的内容外,还应包括无穷递降法,...


全国高中数学联赛一试 范围

全国高中数学联赛一试 范围_学科竞赛_高中教育_教育...几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、...简单的初等数论问题,除初中大纲中斯包括的内容外,还...


全国高中数学联赛试题新规则和考试范围

──高中数学竞赛大纲(修订稿)在“普及的基础上不...几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、...3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余系...


全国高中数学联赛竞赛大纲

不断提高”的方针指导下,全国数学竞赛活动方兴未艾...几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、...3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余系...


全国高中数学联赛新规则

全国高中数学联赛新规则_学科竞赛_高中教育_教育专区...几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、...简单的初等数论问题,除初中大纲中所包括的内容外,还...


高中数学竞赛讲义(免费)

高中数学竞赛讲义(免费)_高三数学_数学_高中教育_教育...几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、...初等数论 同余,欧几里得除法,裴蜀定理,完全剩余类,...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com