欧拉函数及其证明_欧拉函数证明题

欧拉函数及其证明_欧拉函数证明题请思考以下问题:  任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以φ(n)=4。φ(n)的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。第一种情况如果n=1,则φ(1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

请思考以下问题:

  任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

φ(n) 的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。

第一种情况

如果n=1,则 φ(1) = 1 。因为1与任何数(包括自身)都构成互质关系。

第二种情况

如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于等于1的整数),则

2015-08-04/55c0573f4a25a

比如 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4。

这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有p^(k-1)个,即1×p、2×p、3×p、…、p^(k-1)×p,把它们去除,剩下的就是与n互质的数。

上面的式子还可以写成下面的形式:

2015-08-04/55c0578076585

可以看出,上面的第二种情况是 k=1 时的特例。

第四种情况

如果n可以分解成两个互质的整数之积,

  n = p1 × p2

  φ(n) = φ(p1p2) = φ(p1)φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

这一条的证明要用到“中国剩余定理”,这里就不展开了,只简单说一下思路:如果a与p1互质(a<p1),b与p2互质(b<p2),c与p1p2互质(c<p1p2),则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能,b的值有φ(p2)种可能,则数对 (a,b) 有φ(p1)φ(p2)种可能,而c的值有φ(p1p2)种可能,所以φ(p1p2)就等于φ(p1)φ(p2)。

第五种情况

因为任意一个大于1的正整数,都可以写成一系列质数的积。
2015-08-04/55c057f99f735

根据第4条的结论,得到
2015-08-04/55c05835ca6e2

再根据第3条的结论,得到

2015-08-04/55c05871f2594

也就等于

2015-08-04/55c058b16129e

这就是欧拉函数的通用计算公式。比如,1323的欧拉函数,计算过程如下:

2015-08-04/55c059446c936

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172052.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • How to use SOAP API call SF

    How to use SOAP API call SF(1)DownloadWSDLfilesSetup→API→APIWSDLpage→GenerateEnterpriseWSDLThiswilltakeseveralminutestocreateapage.right-clickthepageandsaveaswsdl.jsp.xmlfileonyourlocallaptop.(2)DownloadSOAPUIOpenSourcefromDownl…

  • PostgreSQL与MySQL的区别收集(转)

    PostgreSQL与MySQL的区别收集(转)

  • Java 创建文件软链接

    Java 创建文件软链接为什么要使用软链接:对文件进行移动复制粘贴,如果对文件实体进行操作的话,因为文件大小的原因会导致操作时长会很慢,而且占据内存。那么,如果使用文件的快捷方式去做文件操作会很快捷还省空间,这个快捷方式就是软链接。创建软链接的代码:Files.createSymbolicLink(FileSystems.getDefault().getPath(file.getAbsolutePath()),…

  • 海思Hi3798处理器参数,Hi3798芯片详细信息介绍

    海思Hi3798处理器参数,Hi3798芯片详细信息介绍Hi3798CV200集成4核64位高性能CortexA53处理器、内置NEON加速引擎,强大的CPU处理能力可以满足各种差异化的业务需求。在码流兼容性、在线视频播放的流畅性、图像质量以及整机性能方面保持业界最好的用户体验。支持4K2KP60@10bit超高清视频解码和显示,支持H.265/HEVC、H.264/AVC、AVS+、MVC、MPEG2、MPEG4、VC-1、VP6、VP…

  • java补码运算_java中的补码运算

    java补码运算_java中的补码运算publicclassTest2_8{/*补码运算*在计算机中,数值一率采用补码来运算,如:5-3实例上是5+(-3);*正数与负数的关系:取反再加1**/publicstaticvoidmain(Stringargs[]){intfive=5;intthree=-3;//从输出结果来看负数是用补码来存储的//输出5和-3的二进制码,最高位(最左边那位)为0表示正数,为1…

  • 动态规划背包问题

    动态规划背包问题一、0-1背包1.      有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。(1&lt;=n&lt;=100,1&lt;=wi,vi&lt;=100,1&lt;=W&lt;=10000)样例输入:4231234225 42133457910样例输出…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号