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

欧拉函数

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

相关小说

林晓晓 连载中
林晓晓
多吃一点米
故事设定了基调和背景,接下来的故事将围绕陆霆骁和林晓晓之间的关系发展,以及他们如何共同面对即将到来的挑战和阴谋
2.1万字5个月前
异世界奇异 连载中
异世界奇异
ANN魏盼
顾盼在异世界结实队员,然后在每次任务中提升能力,为了最后的那一个人,她为了他成功了
0.2万字5个月前
请爱我好吗? 连载中
请爱我好吗?
不来朝
原d温柔白切黑sX小狼狗病娇g年龄差有点大g是s养大的(章结有点乱)
2.8万字2个月前
2068年的世界 连载中
2068年的世界
基拉哈斯提
2.3万字1个月前
变成男人去救世 连载中
变成男人去救世
白云衣
兽人、羽人、鲛人…没带脑子,想哪儿是哪儿,大女主,全文女主最大。
7.3万字1周前
荆棘坡 连载中
荆棘坡
阿克曼龙头求打压
兄妹,雷者自避(已签约)
2.6万字3天前