欧拉函数的积性证明

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

欧拉函数的积性证明

积性函数

积性函数 是指对于函数$ 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的证明

由 $(1),(2)$ 得

对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}$,可以推得

同理,我们可以得到:

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

对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} $ 得证。

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