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

欧拉函数

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

相关小说

美:天选之人 连载中
美:天选之人
操控者
不许转载抄袭,模仿@操控者(模仿J.K罗琳的哈利波特)。角色已拟人前面的正在修改中,正文持续更新中
0.9万字6个月前
落魄小宗竟全是大佬 连载中
落魄小宗竟全是大佬
栖休安
白漠渴望得道长生于是她来到来了一个小宗门(排雷:女主傻白甜,文中有多对楠楠副cp,全员be)
7.9万字6个月前
浮生异界 连载中
浮生异界
132***790_8440181711
女主拥有无上力量被异界的邪恶组织觊觎及追杀,神界的男主历劫下凡与女主相识相知相爱,不成想女主正是男主的生死劫,最后双双殒命
0.5万字5个月前
星空下的守望者 连载中
星空下的守望者
橙子树_75469
科技的发展使人类成功走向宇宙,星际时代就此拉开帷幕。当人类的星际移民进行的如火如荼时,来自宇宙深处的神秘敌人却悄然降临……一个从边缘星球走出......
8.6万字4个月前
重来一次会如何 连载中
重来一次会如何
鹤佳m
我是个普通在普通不过的女子,因为含恨死去,上天重新给了我开挂一样的人生。
6.0万字2个月前
墨色轩:以命换天机 连载中
墨色轩:以命换天机
狸晟
深夜的旧城区街道空无一人,我因妹妹失踪多日绝望徘徊,当时钟敲响十下,街角突然浮现一座挂着紫色灯笼的阴森小楼,雕花木门无声开启,穿紫裙黑袍的女......
1.4万字2个月前