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

欧拉函数

可以使用 中国剩余定理。对于互素的正整数 α,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),接着再看更方便。

相关小说

三人行之一:魔法列车的低语 连载中
三人行之一:魔法列车的低语
璃月非李月
魔幻小说作者某天突然的脑洞,有点发疯,自认为能到个小学水平#求评论!不拒绝吐槽但别过分了灵湖小学五年三班迎来了一个新班主任!但这位班主任的行......
4.3万字5个月前
穿成电竞文里的菜鸡小炮灰 连载中
穿成电竞文里的菜鸡小炮灰
哒布吉呀
#年度MVP选手林宿雨穿书了#(双男主)(文中三观不代表作者三观,真的真的真的!)1林宿雨在带领自家俱乐部取得中国赛区的冠军,还没有享受冠军......
9.4万字4个月前
君忆仙落凡尘 连载中
君忆仙落凡尘
三寸旧城七寸执怜
青丘狐族是上古时期九尾狐神族遗留下的血脉因地势缘由,而迁移致高处,因防有凡人意外闯入而设了结界,也为了保护族人,所以定下族规,以防不知情的族......
23.2万字3个月前
天皇下凡历劫记 连载中
天皇下凡历劫记
醉花挑灯
慕晚棠,为上天众仙女皇,下凡历劫,之前记忆本该没有,12岁却恢复了。。。还遇到众仙中只有她能补的天裂,又会发生什么事呢语录“天黄?天是蓝的呀......
1.7万字2个月前
荆棘本无意 连载中
荆棘本无意
是你喵总
这是荆棘家离开后的故事,莱洛拉受伤被两位老人家救了,却意外害死了这两位老人家。后来,她化名为温溪并认识了阿鹤,结伴与羽逾等人一起去寻找莱洛拉......
2.1万字2个月前
回屿悸 连载中
回屿悸
Aa诀祈
【原创作品】(月更)☂避雷:星际,双洁,年上,EO恋,体型差(有私设).♪成年:16岁.-不喜左上角,自行退出,谢谢-——·灵魂一旦被爱,血......
2.5万字2个月前