欧拉函数公式及其证明.doc
欧拉函数 :
欧拉函数是数论中很重要的一个函数，欧拉函数是指:对于一个正整数 n ，小于 n 且和 n 互质的正整数(包括 1)的个数，记作 φ(n) 。
完全余数集合:
定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。 显然 |Zn| ,φ(n) 。
有关性质:
对于素数 p ，φ(p) = p -1 。
对于两个不同素数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。 这是因为 Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ， 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ,φ(p) * φ(q) 。
欧拉定理 :
φ(n)对于互质的正整数 a 和 n ，有 a ? 1 mod n 。
证明:
( 1 ) 令 Zn = {x, x, ..., x} ， S = {a * x mod n, a * x mod n, ... , a * 12φ(n)12x mod n} ， φ(n)
则 Zn = S 。
? 因为 a 与 n 互质， x (1 ? i ? φ(n)) 与 n 互质， 所以 a * x 与 n 互质，所以 a * x iiimod n ? Zn 。
? 若 i ? j ， 那么 x ? x，且由 a, n互质可得 a * x mod n ? a * x mod n (消去ijij律)。
φ(n) ( 2 ) a* x* x *... * x mod n 1 2φ(n)
? (a * x) * (a * x) * ... * (a * x) mod n 12φ(n)
? (a * x mod n) * (a * xmod n) * ... * (a * x mod n) mod n 12 φ(n)
? x* x* ... * xmod n 1 2 φ(n) φ(n) 对比等式的左右两端，因为 x (1 ? i ? φ(n)) 与 n 互质，所以 a ? 1 i
mod n (消去律)。
注:
消去律:如果 gcd(c,p) = 1 ，则 ac ? bc mod p ? a ? b mod p 。
费马定理 :
p - 1若正整数 a 与素数 p 互质，则有 a ? 1 mod p 。 证明这个定理非常简单，由于 φ(p) = p -1，代入欧拉定理即可证明。 ******************************************************
***********************
补充:欧拉函数公式
k( 1 ) p 的欧拉函数
k对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = p ，
kk -1φ(n) = p - p
证明:
kk 小于 p 的正整数个数为 p - 1个，其中
kk - 1k - 1 和 p 不互质的正整数有{p * 1,p * 2,...,p * (p-1)} 共计 p - 1 个
kk - 1kk - 1 所以 φ(n) = p - 1 - (p - 1) = p - p 。
( 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
k n = ? p (I 为 n 的素因子的个数) ii
i=1
根据前面两个结论，很容易得出它的欧拉函数为:
I I
k-1 Φ(n) = ? p(p-1) = n? (1 - 1 / pi) iii
i=1 i=1
对于任意 n > 2，2 | Φ(n) ,因为必存在 p-1 是偶数。 i
本文档为【欧拉函数公式及其证明.doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483