9512.net
甜梦文库
当前位置:首页 >> 数学 >>

趣味数学151:“欧拉函数”节选


选自《数论妙趣——数学女王的盛情款待》 第十二章 互质的数有多少个。 如,求小于 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,6 7,71,共 24 个。所以,小于 72 并且与 72 互质的数有 24 个。 有没有一种比较简便的方法,能解决此类问题呢?有。 我们知道,任意正整数 N 分解为质数幂连乘积的一般表达式为
a a a N ? p1a1 p2 2 p3 3 ? pn n 。

欧拉函数(节选)

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

求小于 N 并且与 N 互质的数有多少个,可以用“欧拉函数” :
a a a ? ( N ) ? p1a ?1 ( p1 ?1) p2 ?1 ( p2 ?1) p3 ?1 ( p3 ?1)? pn ?1 ( pn ?1) 。
1 2 3 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。 作为特例,2=21,Φ (2)=21-1(2-1)=20×1=1×1=1,是一个奇数;而 大于 2 的正整数 N 的欧拉函数Φ (N),从它的表达式可以看出:当 P 为奇数时, (P-1)是偶数;当 P 是偶数时,P 的乘幂是偶数。即Φ (N)恒为偶数。 欧拉函数非常有用,在数论的许多场合,都能见到它的身影。



更多相关文章:
欧拉函数_图文.ppt
欧拉函数_数学_自然科学_专业资料。欧拉函数 Euler's totient function φ函数欧拉商数 Define 定义 ? 在...
欧拉函数.doc
欧拉函数_数学_自然科学_专业资料。欧拉函数 [ Submit Code ] [
欧拉函数积性公式证明.doc
欧拉函数积性公式证明_数学_自然科学_专业资料。欧拉函数积性公式证明 定义:两个
欧拉函数_图文.ppt
欧拉函数_数学_自然科学_专业资料。*欧拉函数主讲人 厉伟键 * 欧拉函数对正整数n,欧拉函数是少于或等 于n的数中与n互质的数的数目。此 函数以其首名研究者...
欧拉函数的一个迭代估计.pdf
欧拉函数的一个迭代估计张祖华平阴县职业教育中心 摘要:欧拉函数的一个迭代估计式被建立。 关键词:欧拉 欧拉函数 估计 济南平阴 250400 欧拉,大数学家,被列为数学...
关于欧拉函数乘积性定理的证明.pdf
关于欧拉函数乘积性定理的证明_数学_自然科学_专业资料。介绍欧拉函数上海机 械学
欧拉函数算法实现及其应用_图文.pdf
% 该函数在很多领域有广 泛的应用 #如 在数论中证明歌德巴赫猜想 #在 离散数学中求循环群的生 成员 # 在计算机网络安全中的 +!- 体制等 % 实现欧拉函数 !...
欧拉函数的角度给出有限循环群生成元的计数公式.doc
欧拉函数的角度给出有限循环群生成元的计数公式_数学_自然科学_专业资料。从...从欧拉函数的角度给出有限循环群生成元的计数公式 摘要:本文从有限循环群的定义...
简化剩余系与欧拉函数.ppt
简化剩余系与欧拉函数_数学_自然科学_专业资料。§3.3 简化剩余系与欧拉函数 一、基本概念 定义1 设R是模m的一个剩余类,若有a?R,使得(a, m) = 1,则称...
数学名家4.txt
数学名家1 5页 免费 数学名家2 6页 免费 【PPT】生活中的趣味数学 30页 免费...几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图