欧拉函数是积性函数证明
令 S(n) 为 1∼n 中与 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.