注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周靖国的博客

春蚕到死丝方尽 愿将余生蚕化春蚕

 
 
 

日志

 
 

欧拉函数  

2013-08-18 10:36:04|  分类: 趣味数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

(选自《数论妙趣——数学女王的盛情款待》第十二章 欧拉函数)

有时,会遇到这样的问题:对于一个给定的正整数N,求小于N并且与N互质的数有多少个。

如,求小于72并且与72互质的数有多少个?

把72分解因式,72=23×32。与72互质的数,就不应含有质因数2或3。于是,小于72并且不含质因数2或3的数有:

1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,共24个。所以,小于72并且与72互质的数有24个。

有没有一种比较简便的方法,能解决此类问题呢?有。

我们知道,任意正整数N,分解为质数幂连乘积的一般表达式为

欧拉函数 - 老骥 - 周靖国的博客

求小于N并且与N互质的数有多少个,可以用“欧拉函数”:

欧拉函数 - 老骥 - 周靖国的博客

以上面的题目“求小于72并且与72互质的数有多少个”为例

           72=23×32

    Φ(72)=Φ(23×32)=22(2-1)×31(3-1)=4×1×3×2=24。

再如,求小于120并且与120互质的数有多少个?

            120=23×3×5。

 Φ(120)=Φ(23×3×5)=22(2-1)×30(3-1)×50(5-1)=4×1×1×2×1×4=32。

再如,求小于60840并且与60840互质的数有多少个?

          60840=23×32×5×132

   Φ(60840)=Φ(23×32×5×132)=22(2-1)×31(3-1)×50(5-1)×131(13-1)=4×1×3×2×1×4×13×12=14976。

  欧拉函数的用途不限于此,在数论的许多场合,都能见到它的身影。  

  评论这张
 
阅读(143)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017