tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> >>

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


初等数论中的几个重要定理 基础知识 定义 (欧拉(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,???

于是由上两式可知通项为 最小公倍数)的周期数列:

的数列的项的最小非负剩余,构成周期为10(即上两式周期的 3,7,0,0,4,0,8,7,5,6,???

这就表明,当

时,当且仅当

时,

,即



又由于数列的周期性,故当

时,满足要求的 只有三个,即

从而当

时,满足要求的 的和为:

. 下面我们着重对 Fetmat 小定理及其应用来举例: 例3.求证:对于任意整数 , 是一个整数。

证明:令

,则只需证 , ;

是15的倍数即可。 ,则

由3,5是素数及 Fetmat 小定理得

而(3,5)=1,故 例4.求证: 证明:令 所以 含有因式 7|

,即 ( 为任意整数) 。 ,则

是15的倍数。所以

是整数。



由 Fetmat 小定理,知13|

又13,7,5,3,2两两互素,所以2730= 例5.设 是直角三角形的三边长。如果

能整除 是整数,求证: 。

。 可以被30整除。

证明:不妨设 是直角三角形的斜边长,则 若2 所以2| 若3 ,2 . ,3 ,3 . ,2

c,则

,又因为

矛盾!

c,因为

,则

,又

,矛盾!从而3| 若 5 所以 ,5 ,5 或0(mod5)与

c,因为
矛盾!





从而5|

. .

又(2,3,5)=1,所以30|

下面讲述中国剩余定理的应用 例6.证明:对于任意给定的正整数 ,均有连续 个正整数,其中每一个都有大于1的平方因子。 证明:由于素数有无穷多个,故我们可以取 个互不相同的素数 ① 因为 续 个数 显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。于是,连 分别被平方数 整除。 ,而考虑同余组

注: (1)本题的解法体现了中国剩余定理的一个基本功效,它常常能将“找连续 个正整数具有某 种性质”的问题转化为“找 个两两互素的数具有某种性质”,而后者往往是比较容易解决的。 (2)本题若不直接使用素数,也中以采用下面的变异方法:由费尔马数 互素,故将①中的 转化为 后,相应的同余式也有解,同样可以导出证明。 两两

例7.证明:对于任意给定的正整数 ,均有连续 个正整数,其中每一个都不是幂数。 分析:我们来证明,存在连续 个正整数,其中每一个数都至少有一个素因子,在这个数的标准分 解中仅出现一次,从而这个数不是幂数。 证明:取 个互不相同的素数 因为 对于 因为 ,考虑同余组

显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。 ,故 ,但由①式可知 都不是幂数。 且 是偶数。 ,且 。 使 ,即 在 的

标准分解中恰好出现一次,故 例8. 设 是给定的偶数, 使得

证明:存在整数

证明:我们先证明,当 为素数幂 且 若 若 :

时结论成立。实际上,能够证明,存在

,则条件表明 为偶数,此时可取 ,则 与

; 中有一对满足要求。 是 的一个标准分解,上面已经证明,对每个 存在整

一般情形下,设 数 使得 且

,而由中国剩余定理,

同余式 同余式 现不难验证解 于是 故

①有解 , ②有解 。 符合问题中的要求:因 ,又由①②知 。 ,故 , ,

注:此题的论证表现了中国剩余定理最为基本的作用:将一个关于任意正整数 的问题,化为 为 素数幂的问题,而后者往往是比较好处理的。


推荐相关:

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

初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 定义 意的 对模 个数, , 的剩余,即 且对于任意的 。并定义 称为是模 ,若 的既约剩余系...


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

第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义 1 ≤ j ...


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

第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义 1 ≤ j ...


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

有关初等数论中的几个定理,费马小定理,剩余定理等等。有关初等数论中的几个定理,费马小定理,剩余定理等等。隐藏>> 初等数论中的几个重要定理基础知识 定义(欧拉(...


11数论的几个重要定理

11数论的几个重要定理_高三数学_数学_高中教育_教育专区。11 数论的几个重要定理...初等数论中的几个重要定... 6页 免费 美丽的自然风光图片素材 39页 免费 报...


初等数论(四)-几个著名的数论定理

初等数论(四)--几个著名的数论定理一些常用概念 ? 欧拉函数 ? (n) --介于 1 和 n 之间与 n 互质的自然数个数 ? 缩系---在 ? (n) 个剩余类中各取...


初等数论定理

使 a=bq+r,其中 0≤r...初等数论中的欧拉定理 7页 免费 初等数论中的几个重要定... 8页 1下载券 初等数论中的几个重要定... 暂无评价 10页 1下载...


数论重要定理

一、欧拉定理 的整数, 设 m > 1 的整数, ( a, m ) = 1, 则a ? (...数论之同余定理、个位律 7页 2下载券 初等数论中的几个重要定... 6页 1下...


初等数论中一些命题的多种证法

初等数论中一些命题的多种证法_司法考试_资格考试/...p 证法 2:相关定理补充: (x1 ? x2 ? ... ...非常重视构造技巧的,好的 构造对于问题解决十分重要...


第四讲-几个定理

初等代数选讲---第四讲 第四讲定义(欧拉(Euler)函数) 初等数论中的几个重要定理 一组数 x1 , x2 ,?, xs 称为是模 m 的既约剩余系, 如果对任意的 1...

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