欧拉函数是积性函数证明

S(n)1n 中与 n 互质的数组成的集合。

分别任取 S(a),S(b) 中的元素 a0,b0.( gcd

考虑线性同余方程组 \begin{cases} x\equiv a_0\pmod {a}\\ x\equiv b_0\pmod {b} \end{cases} ,

则有唯一解 x\equiv c_0\pmod {ab}.

\gcd(c_0,a)=\gcd(c_0\bmod a.a)=\gcd(a_0,a)=1. 同理可得,\gcd(c_0,b)=1.

\gcd(c_0,ab)=1,c_0\in S(ab).

此为 S(a)\times S(b)S(ab) 的一个单射。

任取 S(ab) 中的元素 c_0,令 a_0=c_0\bmod a,b_0=c_0\bmod b.

由于 \gcd(ab,c_0)=1,故 a_0\in S(a),b_0\in S(b).

此为 S(ab)S(a)\times S(b) 的一个单射。

S(a)\times S(b)S(ab) 存在一个双射。

因此 |S(ab)|=|S(a)||S(b)|,即 \varphi(ab)=\varphi(a)\varphi(b)

Q.E.D.