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

欧拉函数

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

相关小说

长夜的消散 连载中
长夜的消散
泪落朽木
白色的风筝也要独属于它的夜晚
0.2万字5个月前
我在无序副本里弑神 连载中
我在无序副本里弑神
秋南栀
「出逃者」浅羽x「神牌」林沨林沨在求死时意外进入副本系统,为了与系统达成交易,获得【起死回生】复活妹妹,林沨选择留在系统成为玩家在过副本途中......
6.5万字5个月前
明暗交响 连载中
明暗交响
屿枫夜
她,曾经是大陆的魔女,人们说她残害亲眷,阴险狠毒,为楚家之耻。最后,她死于那个没有血缘关系的“哥哥”之手。后来,她重生,伪装,复仇。假扮学生......
12.9万字5个月前
春风酌酒 连载中
春风酌酒
不想更新的一天
我以春风酌酒,愿故友永宁。(禁止任何形式的抄袭,以及投喂AI等一系列的侵权操作。)
6.9万字4个月前
异世界转生重生 连载中
异世界转生重生
黑土还不阴
怎么说呢,男主角转生变成少女
1.6万字4个月前
无限重置 连载中
无限重置
补密码的课,写密码的作业
只是我写的无脑爽文,双男主林嘉言x牧赫一
3.9万字2周前