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)恒为偶数。 欧拉函数非常有用,在数论的许多场合,都能见到它的身影。



更多相关文章:
欧拉函数积性公式证明
欧拉函数积性公式证明_数学_自然科学_专业资料。欧拉函数积性公式证明 定义:两个整数相除 N/m 一定可以表示为 N=m·u+r,在初等数 论中称 m 为模,r 为...
自适应法的欧拉函数
自适应法的欧拉函数_数学_自然科学_专业资料。中南大学matlab程序设计实践全部答案(很多自己搜)标题是第一题题目(只供参考)第一题对简单的一阶方程的初值问题: y...
更多相关标签:

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

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