欧拉函数 10的欧拉函数

欧拉函数:

对于一个正整数n,小于n且和n互质的正整数的个数,记做:φ(n),其中φ(1)被定义为1,但是并没有任何实质的意义。

特殊性质:当n为奇数时,φ(2n)=φ(n)。

完全余数集合:
定义小于n且和n互质的数构成的集合为Zn,称呼这个集合为n的完全余数集合。

显然,对于素数p,φ(p)= p - 1.

对于两个素数p、q,他们的乘积n = pq 满足φ(n)=(p-1)(q-1)

证明:对于质数p,q,满足φ(n) =(p-1)(q-1)
考虑n的完全余数集Zn = { 1,2,....,pq -1}
而不和n互质的集合由下面三个集合的并构成:
1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个
2) 能够被————q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个
3) {0}
很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) =(p-1)(q-1)

欧拉定理:
对于互质的整数a和n,有aφ(n) ≡ 1 mod n

{

注:

同余符号:  

两个整数a,b,若它们除以整数m所得的余数相等,则称a,b对于模m同余

  记作 a ≡ b (mod m)

  读作a同余于b模m,或读作a与b关于模m同余。

  比如 26 ≡ 14 (mod 12)

}


证明:
首先证明下面这个命题:
对于集合Zn={x1,x2,...,xφ(n)},考虑集合
欧拉函数 10的欧拉函数
S = {ax1 mod n,ax2mod n,...,axφ(n)mod n}
则S = Zn
1) 由于a,n互质,xi也与n互质,则axi也一定于p互质,因此
任意xi,axi mod n 必然是Zn的一个元素
2) 对于Zn中两个元素xi和xj,如果xi ≠ xj
则axi mod n ≠ axi mod n,这个由a、p互质和消去律可以得出。
所以,很明显,S=Zn

既然这样,那么
(ax1 × ax2×...×axφ(n))mod n
= (ax1 mod n × ax2mod n × ... × axφ(n)mod n)mod n
= (x1 × x2 × ... × xφ(n))mod n
考虑上面等式左边和右边
左边等于(aφ(n) × (x1 × x2 × ... × xφ(n))mod n) mod n
右边等于x1 × x2 × ... × xφ(n))mod n
而x1 × x2 × ... × xφ(n))mod n和p互质
根据消去律,可以从等式两边约去,就得到:
aφ(n)≡ 1 mod n

费马定理:
a是不能被质数p整除的正整数,则有 ap -1 ≡ 1 modp

证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
同样有推论:对于不能被质数p整除的正整数a,有ap ≡ a mod p

欧拉函数公式:

( 1 ) pk的欧拉函数

对于给定的一个素数 p , φ(p) = p -1。则对于正整数 n = pk

 φ(n) = pk - pk -1

证明:
小于 pk 的正整数个数为 pk - 1个,其中
和 pk 不互质的正整数有{p * 1,p * 2,...,p * (pk - 1-1)} 共计 pk - 1 - 1
所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1

( 2 ) p * q的欧拉函数

假设 p, q是两个互质的正整数,则 p * q 的欧拉函数为

φ(p * q) = φ(p) * φ(q) , gcd(p, q) = 1。

证明:
令 n = p * q , gcd(p,q) = 1
根据中国余数定理,有
Zn 和 Zp × Zq 之间存在一一映射
(我的想法是: a ∈ Zp , b ∈ Zq ⇔ b * p + a * q ∈ Zn 。)
所以 n 的完全余数集合的元素个数等于集合 Zp × Zq 的元素个数。
而后者的元素个数为 φ(p) * φ(q) ,所以有
φ(p * q) = φ(p) * φ(q) 。

( 3 )任意正整数的欧拉函数

任意一个整数 n 都可以表示为其素因子的乘积为:

 I
n = ∏ piki (I 为 n 的素因子的个数)
i=1
(注:∏是希腊字母,即π的大写形式,在数学中表示求积运算或直积运算,形式上类似于Σ,有时也用来代表圆周率值)

根据前面两个结论,很容易得出它的欧拉函数为:
I I
Φ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)
i=1 i=1
对于任意 n > 2,2 | Φ(n) ,因为必存在 pi -1 是偶数。

  

爱华网本文地址 » http://www.aihuau.com/a/25101016/310494.html

更多阅读

代理超人v4.10的使用方法 t racks v4.10 破解版

代理 代理ip“代理超人”是一个简单易用的代理搜索工具,可以保证我们随时有有效的代理可用。  “代理超人”是绿色软件,只需将压缩包解压后就可以使用了。软件运行后主界面如图1。标题栏显示了软件的版本和我电脑的IP地址。 图1

维生素辅酶CoQ-10的作用治疗帕金森氏综合症 辅酶coq10

摘编1辅酶Q10辅酶Q10是一种脂溶性抗氧化剂,辅酶Q10是人类生命不可缺少的重要元素之一,能激活人体细胞和细胞能量的营养,具有提高人体免疫力、增强抗氧化、延缓衰老和增强人体活力等功能,医学上广泛用于心血管系统疾病,国内外广泛将其

教学反思(10篇) 10的认识教学反思

《郑和远航》教学反思一、课前的思考是否落实?课前备课时希望自己的课堂能给予学生充分展示自己学习成果的机会,还希望初步形成第二课时精读课文时“预习反馈”式教学的粗略模式。我认为《郑和远航》这课的教学,将自己课前的两方面考虑

如何让宝宝理解大于10的单数和双数? 单数和双数教案

当儿子在做数学题目中不太理解:特别大于10的单数和双数,这让萍儿费心。我只好求助百度,搜索一下,这一长篇,我全粘到博客上来,再捡些简单的语句,等儿子放学回来,我再与他一起好好学习,天天向上~~~~~~~加强动手操作提高教学效率——兼谈苏

声明:《欧拉函数 10的欧拉函数》为网友無知女分享!如侵犯到您的合法权益请联系我们删除