数学联邦政治世界观
超小超大

欧拉函数

可以使用 中国剩余定理。对于互素的正整数 α,b ,可以直接验证环同态 f:Z/αbZ → Z/αZ × Z/bZ

f(x mod αb):=(x mod α,x mod b)

的逆映射是g(y mod α,z mod b):=ybn+zαm mod αb,这里 m,n 是整数使得 αm+bn=1 ( Bezout等式保证α,b 互素时,这样 m,n 一定存在),因此 f 是环同构,于是我们有Z/αbZ≅Z/αZ × Z/bZ。特别地,它们的乘法群也同构 Z/αbZ)× ≅ (Z/αZ)× × (Z/bZ)× 。考虑等式两边集合的基数,我们就有 ф(αb)=ф(α)ф(b) 。

另一种方法是使用算术函数的 Dirichlet卷积。对于正整数 n ,考虑集合 {1,. . .,n} 的拆分Ad={x∈{1,2,. . .,n}:gcd(x,n)=d},d│n。从定义可知, Ad 有 ф(n/d) 个元素。比较基数我们有

n=∑ф(n/d)

d|n

这说明id=1 * ф ,这里 id(x):=x 是恒等函数, 1(x):=1 是恒为 1 的函数, * 表示 Dirichlet卷积

(f * g)(n):=∑f(d)g(n/d)

d|n

常数函数1 的Dirichlet卷积逆是 Mobius函数 μ ,因此我们有 ф=μ * id 。由于 μ 和 id 都是积性以及两个积性函数的Dirichlet卷积还是积性,我们断定 ф 也是积性。

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

kpl:假如一诺有个姐姐 连载中
kpl:假如一诺有个姐姐
欧蕊拉
假如一诺有个姐姐会是什么样呢
0.8万字6个月前
异世界奇异 连载中
异世界奇异
ANN魏盼
顾盼在异世界结实队员,然后在每次任务中提升能力,为了最后的那一个人,她为了他成功了
0.2万字5个月前
我与神明之间的无数种可能 连载中
我与神明之间的无数种可能
须臾本愚
【双向暗恋+一见钟情】都说神明普度天下,潞鸢却不赞同。初入九重天,潞鸢带着灭族之痛,一腔怒火,此生只为手刃仇人与神明。再入九重天,他带着身后......
10.8万字3个月前
all恶 连载中
all恶
丁猫奇遇记
请自行观看全员恶人,作者更新有点慢
0.9万字3个月前
情神……西玫溅妍 连载中
情神……西玫溅妍
慕羽儿mye
在第四维度的灵界上,玫瑰之王西玖溅妍与鹰国之王鹰.维洛依斯之间的超虐言情救赎,最终双双成神的故事!
1.1万字3个月前
三铜钱 连载中
三铜钱
阿月不想吃肉
1314与1058的相遇像是被安排好的,这发生的一切好像都像是安排好的,这到底是为什么?是谁做的这一切
0.2万字1个月前