费马小定理欧拉 欧拉函数和费马小定理

2018-12-18 - 费马小定理

大家对费马小定理都非常熟悉,它是说如果p为素数,则对于任意的正整数a都有p整除a^p-a。到了1736年,欧拉给出了费马小定理的严格证明。而到了1760年,欧拉又给出了费马小定理的重要推广。他首先考虑了小于给定正整数n且与n互素的正整数个数,高斯为此专门引入了一个记号Φ(n),称之为欧拉函数。

费马小定理欧拉

使用这个新的函数,欧拉证明了如果a和n互素,则n整除a^Φ(n)-1。注意到当n为素数p时,每个小于p的正整数都和p互素,即Φ(n)=p-1,此时欧拉推广的定理变成了对每个与p互素的a,均有p整除a^(p-1)-1当然也整除a^p-a。如果a和p不互素,即p整除a,显然有p整除a^p-a。其实这就是费马小定理。

费马小定理欧拉

令人惊奇的是,欧拉这个定理的证明非常简单,相比之下他的发现和提出要难的多。接下来我们来看看他的证明过程。

首先假设a和n互素,并且在1,2,3,…,n中和n互素的数为R1,R2,R3,…,Rk,则欧拉函数Φ(n)=k。接着欧拉又考虑k个数aR1,aR2,aR3,…,aRk除以n后所得的余数。一方面a和n互素,Ri也分别和n互素,所以他们的余数也和n互素。

费马小定理欧拉

另一方面,如果aRi和aRj除以n所得的余数相同,则n必整除他们之差,即n整除Ri-Rj,而这是不可能的。所以aR1,aR2,aR3,…,aRk除以n所得的余数不仅和n互素且两两不同。因此余数就是R1,R2,R3,…,Rk的某一个排列。所以n整除下面乘积之差:

又因为R1R2R3…Rk也和n互素,因此n整除a^k-1。至此就证明了欧拉对于费马小定理的扩展。返回搜狐,查看更多

费马小定理欧拉
相关阅读
  • 镱同位素怎么生成 小儿皮肤血管瘤的同位素治疗

    镱同位素怎么生成 小儿皮肤血管瘤的同位素治疗

    2019-07-26

    一位朋友的小孩出生后发现左侧额部有一绿豆大的红痣,三个月来逐渐长大,他不知是什么病,问我应该如何治疗,治疗后会不会留下疤痕?上述皮肤红痣在医学上称为血管瘤,是皮肤上新生血管形成的良性肿瘤,是一种婴幼儿常见的皮肤疾病。皮肤血管瘤的治疗方法很多,各有优缺点,用何种方法,也要按血管瘤的种类、发生部位和发展情况而定。

  • 工科男跳秦淮八艳 窗帘改礼服工科男走秀 好看的礼服品牌有哪些?

    工科男跳秦淮八艳 窗帘改礼服工科男走秀 好看的礼服品牌有哪些?

    2018-10-09

    穿着礼服走秀或者出席大型活动的时候,那是女人的专属,但是你见男的穿礼服走秀吗?近日,窗帘改礼服工科男走秀视频在网上走红,江苏常州大二男生周同学,自制礼服在寝室走秀,不仅礼服挺时尚,走起秀还真有名模气场,连室友也忍不住加入。周同学说,他学的工程专业,走秀看看就会了。画面简直就是太辣了,说起来礼服,你知道好看的礼服的品牌有哪些吗?我们一起来看看。

  • 费马小定理群论 群论证明费马小定理

    费马小定理群论 群论证明费马小定理

    2018-12-18

    摘要:本文论述了集合中的阶的应用,交换群中的阶与费马小定理之间的联系给我的启发性思考。关键词:群;阶;等价类;简化剩余系数学是一道永无止境的阶梯,引领人不断往上爬,越到上面看到的问题就越清晰。“阶”这个概念我是在高中奥数竞赛书上看到的,“集合的阶”指的是集合的元素个数,举个例子:n个元素构成的集合。

  • 费马小定理求逆元模板 除法取模逆元费马小定理

    费马小定理求逆元模板 除法取模逆元费马小定理

    2018-12-18

    对于正整数和,如果有,那么把这个同余方程中的最小正整数解叫做模的逆元。逆元一般用扩展欧几里得算法来求得,如果为素数,那么还可以根据费马小定理得到逆元为。(都要求a和m互质)推导过程如下(逆元详解)(点我)nbsp;假如p是质数,且gcd(a,p)1,那么a(p1)1(modp)这个为费马小定理。