注册    登录
今天看啥  ›  专栏  ›  BlueHeart0621

欧拉函数

BlueHeart0621  · 简书  ·  · 2020-03-10 02:55

1. 欧拉函数定义

欧拉函数 {\phi(n)} 表示的是小于等于 n 且和 n 互质的正整数的个数。（易知 {\phi(1) = 1} ）

2. 欧拉函数公式

对于任意整数 n ，若其质因数分解结果为 {n = p_1^{k_1}p_2^{k_1} \cdots p_n^{k_n}} ，则欧拉函数公式为 {\phi(n) = n(1-{1 \over p_1})(1- {1 \over p_2}) \cdots (1-{1 \over p_n})}

3. 欧拉函数性质

（1）欧拉函数为积性函数。（对于数论函数 {f(n)} 不恒等于 0，当 {(m,n) = 1} 时，满足 {f(mn) = f(m)f(n)} ，则称 {f(n)} 为积性函数）
{\phi(mn) = \phi(m)\phi(n), \, (m,n) = 1}

（2）若 {(m,n) = d} ，则
{\phi(mn) = d{\phi(m)\phi(n) \over \phi(d)}}

（3）若 m 、 n 满足 {m|n} ，则
{\phi(mn) = m \cdot \phi(n)}

（4）若 m 、 n 满足 {m|n} ，则
{\phi(m)|\phi(n)}

（5）对于质数 p ，其欧拉函数公式为
{\phi(p) = p-1}

（6）对于质数 p ， {p_k} 的欧拉函数公式为
{\phi(p^k) = (p-1)p^{k-1}}

（7）小于等于 n 且整除 n 的所有正整数的欧拉函数值之和等于 n ，即
{n = \sum_{d|n}\phi(d)}

（8）欧拉定理：若 {(a,m) = 1} ，则 {a^{\phi(m)} \equiv 1 \, (mod \, m)} 。

（9）扩展欧拉定理
{a^x \equiv a^{x \,\, mod \,\, \phi(m)} \, (mod \, m), \,\, (a,m) = 1} 或 {a^x \equiv a^x (mod \, m), \,\, (a,m) \neq 1 \wedge x \lt \phi(m)} 或 {a^x \equiv a^{x \,\, mod \,\, \phi(m) + \phi(m)} (mod \, m), \,\, (a,m) \neq 1 \wedge x \ge \phi(m)}




原文地址：访问原文地址
快照地址： 访问文章快照
推荐文章
求是网  ·  国务院台办发言人就台湾地区领导人“5·20”讲话表态
21 小时前
小鹏汽车  ·  小鹏520 AI DAY直播预告来了！
4 天前
蔚来(微博搜索)  ·  蔚来(微博搜索)-20240518-1
3 天前
人民日报评论  ·  以大开放促进大开发 | 评论员观察
5 天前
高工智能汽车  ·  架构升级！车规MCU打响“升级战”，这家本土厂商杀出重围
1 周前
河北卫视  ·  地球一小时｜有些美好 唯关灯可见
2 年前
Chiphell  ·  [时尚] Waxed Kudu 皮靴十个月旧化对比
2 年前
雪球  ·  投资本身没风险，最大的风险往往是你对自己的高估，以及缺乏对市场的-20200507201752
4 年前
FM93交通之声  ·  44岁浙江职场妈妈给儿子做了8年精致早餐!结果她自己都意外…
5 年前
装修情报  ·  装修前就要完成的手艺活，你还漏了这一件！
6 年前
关于   移动版   ·   Py中国   ·   RSS之家   ·   codingpro   ·   Code   ·   link之家   ·   卧龙AI搜索   ·   藏经阁   ·   小百科
今天看啥 - 微信公众号rss订阅, 微信rss, 稳定的RSS源
© 2024 ~ 沪ICP备11025650号