对于欧拉函数是积性函数的证明

欧拉函数的积性证明

积性函数

积性函数 是指对于函数$ f $，当$ gcd(m, n) = 1 $时，$f(m)f(n) = f(mn)$。

完全积性函数 是指对于函数$f$，$f(m)(n) = f(mn)$。

下面我们将证明欧拉函数是积性函数。

证明

目标等式： $\phi(m)\phi(n) = \phi(mn)$

符号约定

$\phi(n)$：欧拉函数

$X$ ： $m$ 的简化剩余系

$Y$ ： $n$ 的简化剩余系

$Z$ ： $mn$ 的简化剩余系

$x_i$ ：$X$ 的代表元素

$y_i$ ： $Y$ 的代表元素

$z$ ： $Z$ 的代表元素

$(x,y)$ ： $x，y$ 的最大公约数

证明思路

我们构造等式 $x_in+y_jm$ ，我们想要证明 $\{x_in+y_jm\}$ 和 $mn$ 的简化剩余系 $Z$ 之间存在一个双射关系，也就是说 $x_in+y_jm$ 的个数与 $mn$ 的简化剩余系的个数相同。

同时，我们将证明 $x_in+y_jm$ 当 $i，j$ 不同时不在同一剩余类中。这样得到 $x_in+y_im$ 可以表示 $\phi(m)\phi(n)$ 个不同的剩余类。目标等式得证。所以我们将证明：

1. $x_in+y_jm\in Z$ ，即 $gcd(x_in+y_jm,mn)=1$
2. $\forall z,\exist i, j, \mbox{ s.t. } x_in+y_jm \equiv z \pmod{mn}$
3. 对于任意一个有序二元组$(i,j)\neq(k,l)，$ $x_in+y_jm\equiv x_kn+y_lm \pmod{mn} $

$1,2$ 实际上证明了双射关系，$3$ 则证明了不在同一剩余类。

证明过程

对1的证明

$$(x_i,m)=1\Longrightarrow(x_in,m)=1\Longrightarrow(x_in,mn)=1 \tag{1}$$ $$(y_i,n)=1\Longrightarrow(y_im,n)=1\Longrightarrow(y_im,mn)=1 \tag{2}$$

由 $(1)，(2)$ 得 $(x_im+y_jm,mn)=1$

对2的证明

由 $(m,n)=1$ 可得，存在 $p，q$ 使得 $mp+nq=z$。

那么，我们可以得到：

$(z,mn)=1\Rightarrow(mp+nq,mn)=1\Rightarrow(mp+nq,m)=1\Rightarrow(nq,m)=1\Rightarrow(q,m)=1$

由此可得，$q$ 在 $m$ 的简化剩余系中，所以 $\exist x_i,x_i \equiv q \pmod{m}$，可以推得

$$x_in \equiv qn \pmod{mn} \tag{3}$$

同理，我们可以得到：

$$y_jm \equiv pm \pmod{mn} \tag{4}$$

由 $(3),(4)$ 我们可以得到：

$$x_in+y_jm \equiv qn+ pm \equiv z \pmod{mn}$$

对3的证明

应用反证法，我们假设存在这样的有序二元组 $(i,j)$ 和 $(k,l)$ 满足 $(i,j)\neq(k,l)$ 使得 $x_in+y_jm\equiv x_kn+y_lm \pmod{mn} $ ，那么我们有 ：

$x_in+y_jm\equiv x_kn+y_lm \pmod{m} \Rightarrow x_in \equiv x_kn \pmod{m} \Rightarrow x_i \equiv x_k \pmod{m}$ ，而由题设我们可以知道 $\forall i \neq k, x_i \not\equiv x_k \pmod{m}$，所以矛盾。

所以对于任意一个有序二元组$(i,j)\neq(k,l)，$ $x_in+y_jm\equiv x_kn+y_lm \pmod{mn} $ 得证。

综上，证得欧拉函数为积性函数。