当前位置:首页 >> 学科竞赛 >>

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


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

基础知识

定义(欧拉(Euler)函数)一组数 的 , 的剩余,即 且对于任意的 。并定义 ,若

称为是模

的既约剩余系,如果对任意 是 对模

=1,则有且仅有一个 中和

互质的数的个数,

称为欧拉(E

uler)函数。

这是数论中的非常重要的一个函数, 显然 中与 互素的数的个数,比如说

, 而对于

, 。

就是 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)函数)一组数 的, 的剩余,即 且对于...
初等数论中的几个重要定理 高中数学竞赛
初等数论中的几个重要定理 高中数学竞赛_学科竞赛_高中教育_教育专区。初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 的, 的剩余,即 且对于任...
第五节初等数论中的几个重要定理
第五节初等数论中的几个重要定理_学科竞赛_高中教育_教育专区。第五节基础知识 初等数论中的几个重要定理 定义(欧拉 (Euler)函数)一组数 x1 , x2 ,?, xs ...
初等数论中的几个重要定理
初​等​数​论​中​的​几​个​重​要​定​理初等数论中的几个重要定理 基础知识 定义 (欧拉(Euler)函数) 一组数 且对于任意的 。并...
第五节初等数论中的几个重要定理
高中数学竞赛 初等数论系列讲义高中数学竞赛 初等数论系列讲义隐藏>> 第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L ,...
初等数论中的几个重要定理
初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 定义 意的 对模 个数, , 的剩余,即 且对于任意的 。并定义 称为是模 ,若 的既约剩余系...
初等数论中的几个重要定理
初等数论中的几个重要定理初等数论中的几个重要定理隐藏>> 初等数论中的几个重要定理 基础知识 (欧拉(Euler)函数) 一组数 定义 且对 于任意的 ,若 中和 称为...
第五节初等数论中的几个重要定理
竞赛数学数论专题 8页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 第五节初等数论中的几个重要定理 数论数论隐藏...
初等数论中的几个重要定理
有关初等数论中的几个定理,费马小定理,剩余定理等等。有关初等数论中的几个定理,费马小定理,剩余定理等等。隐藏>> 初等数论中的几个重要定理基础知识 定义(欧拉(...
中学数学竞赛中常用的几个重要定理
中学数学竞赛中常用的几个重要定理_数学_初中教育_教育专区。赛瓦定理、托勒密定理、斯特沃尔特定理、欧拉定理、梅内劳斯定理数学竞赛中几个重要定理 1、 梅涅劳斯定理...
更多相关标签:
初等数论四大定理 | 初等数论 之孙子定理 | 数学竞赛初等数论 | 高中数学竞赛初等数论 | 初等数论 | 初等数论第三版答案 | 初等数论 潘承洞 | 初等数论 pdf |