专栏首页wym欧拉定理——数论定理

欧拉定理——数论定理

在数论中,欧拉定理也叫费马-欧拉定理,是一个关于同余的性质,欧拉定理表明,若n,a为整数,且n,a互质,则

  • 证明:
  • 1~n中与n互质的数按照顺序排布为x1,x2,...xφ(n),显然有φ(n)个
  • 我们考虑这么一些数
  • m1=a*x1,m2=a*x2,m3=a*x3......mφ(n)=a*xφ(n)
  •  1)这些数中的任意两个都不%n同余
  • 设mS≡mR(modn),不妨令mS>mR
  • 有mS-mR=a(xS-xR)=qn, 由于(xS-xR)<n,而a和n互质,左边式子不能整除n,则这个等式不存在
  • 2)这些数除n的余数都与n互质,设余数与n有公因子r,则a*xi=z*n+y*r=r*(.....),a*xi就不与n互质了
  • 这些数除n的余数都在x1,x2,x3,....xφ(n)中,因为这是1~n中与n互质的所有数,且都小于n

由1),2)可知,m1,m2,m3....mφ(n)必须和x1,x2,x3.....xφ(n)同余

也就是a^φ(n)*{x1*x2....*xφ(n)}≡x1*x2*x3...xφ(n)(modn)

也即a^φ(n)≡1(modn)

费马定理: a是不能被质数p整数的正整数  a^(p-1)≡1(modp) 因为φ(p)=p-1.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java开发 按钮

    用户2965768
  • linux下自定义静态函数库

    用户2965768
  • 贪心算法理论概述

      贪心策略是指从问题的初始状态出发,通过若干次贪心选择得出最优值(或较优解)的一种解法

    用户2965768
  • ShadowBrokers 又搞事!每月支付 400 万美元,多获得两份新泄露的文件,你会买吗?

    今年 4 月份,臭名昭著的 ShadowBrokers 入侵 NSA,窃取到 Equation Group 研发的一系列工具,并将这些 exploit 以付费订...

    FB客服
  • 消失20年的病毒在美国死灰复燃,全球致死11万人:有些灾难,本可以避免

    4月初,美国50个州,其中44个州爆发危机,26个州处于高度紧张状态。美国纽约州为此颁布紧急禁令,禁止部分人群进入公共场所。

    华章科技
  • 智慧交通解决方案:借力交通综合执法管理系统

    在建设统一、规范的交通综合执法文书制作系统、网络办案系统,为交通执法部门的案件处理提供标准的处理程序以及为执法单位的公文处理提供极大的方便;集中存放和管理交通行...

    科技快讯网
  • 腾讯云高防服务器 腾讯云BGP高防IP是如何防DDos和cc攻击的?

    腾讯云高防服务器又称为腾讯云BGP高防ip,无论你的业务是否在腾讯云,都可以使用腾讯云提供的DDos及cc防护。如果 业务不在腾讯云,只需把需要防护的设备绑定腾...

    追梦者
  • 腾讯云高防服务器 腾讯云BGP高防IP是如何防DDos和cc攻击的?

    腾讯云高防服务器又称为腾讯云BGP高防ip,无论你的业务是否在腾讯云,都可以使用腾讯云提供的DDos及cc防护。如果 业务不在腾讯云,只需把需要防护的设备绑定腾...

    用户6497543
  • 腾讯云高防服务器 腾讯云BGP高防IP是如何防DDos和cc攻击的?

    腾讯云高防服务器又称为腾讯云BGP高防ip,无论你的业务是否在腾讯云,都可以使用腾讯云提供的DDos及cc防护。如果 业务不在腾讯云,只需把需要防护的设备绑定腾...

    用户6601673
  • 该如何有效的提高C/C++语言编程能力

      其实我以前也有这样的困惑,感觉完了不知道怎么用。而且我也不是学计算机的,也没有从事相关工作,所以大概有十年的时间都没写什么程序。最近因为想做点东西,所以又重...

    用户6754675

扫码关注云+社区

领取腾讯云代金券