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

欧拉函数及其证明_欧拉函数证明题请思考以下问题:  任意给定正整数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)
blank

相关推荐

  • webmin的repo

    webmin的repo

  • java类加载的过程 父_类加载机制原理

    java类加载的过程 父_类加载机制原理JVM和类当我们调用Java命令运行某个Java程序时,该命令将会启动一条Java虚拟机进程,不管该Java程序有多么复杂,该程序启动了多少个线程,它们都处于该Java虚拟机进程里。同一个JVM的所有线程、所有变量都处于同一个进程里,它们都使用该JVM进程的内存区。当系统出现以下几种情况时,JVM进程将被终止:程序运行到最后正常接收; 程序运行到使用Sys…

  • SQL语句面试题目_sql基础知识面试题

    SQL语句面试题目_sql基础知识面试题我自己编辑总结的sql面试题目大全,也是每条都验证过的第一类:sql面试题(学生表_课程表_成绩表_教师表)表结构,节选自:http://www.cnblogs.com/qixuejia/p/3637735.html题目一,节选,自:https://wenku.baidu.com/view/cda288f1b90d6c85ed3ac671.html题目二,节选,自:http://ww…

  • python hashlib模块安装_python hashlib 模块

    python hashlib模块安装_python hashlib 模块hashlib模块用于加密相关的操作,代替了md5模块和sha模块,主要提供SHA1,SHA224,SHA256,SHA384,SHA512,MD5算法。在python3中已经废弃了md5和sha模块什么是摘要算法呢?摘要算法又称哈希算法、散列算法。它通过一个函数,把任意长度的数据转换为一个长度固定的数据串(通常用16进制的字符串表示)。摘要算法就是通过摘要函数f()对任意长度的数据data计算出…

  • 服务器的基础知识_篮球小知识科普

    服务器的基础知识_篮球小知识科普“服务器”-互联网之魂服务器被誉为互联网之魂。我第一次见到服务器是在学校图书馆,是一种机架式服务器。第二次见到服务器是在公司机房,本期文章是对服务器进行大盘点和梳理,会介绍我拆装服务器过程,从中的学习感悟。一、服务器1.1服务器与PC机大部分程序员见到的服务器也就是云服务器,知名的那几家公司:阿里云、腾讯云…都是著名的云服务器提供厂商。在学校写个网站啥的,学生就可以优惠买买买。不过今天我们介绍的是服务器而非云服务器。在学校的时候,老师会说:“你们用的电脑也是服务器”。是的,那么现在我们来讨论,P

  • 2021版idea激活码99年_在线激活

    (2021版idea激活码99年)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~K…

发表回复

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

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