欧拉函数

可以使用 中国剩余定理。对于互素的正整数 α，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://tongren.me），接着再看更方便。