初等数论--欧拉函数积性的证明

1. 简介

欧拉函数$\varphi (n)$表示在小于等于$n$的正整数中与$n$互质的个数。

如
$$\begin{gathered} \varphi (6)=2(15) \\ \varphi (12)=4(15711) \end{gathered}$$

欧拉函数是一个积性函数；

所谓积性函数，指的是满足下面的条件的函数

$$\forall a,b\in N_{+},s.t.\gcd (a,b)=1\Rightarrow \varphi (ab)=\varphi (a)\varphi (b)$$

本文提供两种比较初等方式证明欧拉函数的积性性质，内容源于知乎。

• 算术基本定理+容斥原理
• 中国剩余定理

2. 证明一：唯一分解定理+容斥原理

根据算术基本定理，我们有任意一个大于$1$的正整数可以唯一表示为下面的形式

$$n={\Pi }_{i=1}^m{p}_i^{a_i}$$

我们令全集
S n : = { 1 , 2 , ⋯ , n } S_n := \{1,2,\cdots,n\} Sn​:={1,2,⋯,n}
我们可以将$S_n$中$n$的因子根据是是否整除素数$p_i$进行分类
A p i : = { x ∣ x = k p i ∧ x ∈ S n , k ∈ N ∗ } A_{p_i} := \{x|\ x = kp_i \land x \in S_n, k \in N^* \} Api​​:={x∣ x=kpi​∧x∈Sn​,k∈N∗}
因此我们可以将所有与$n$互质的数的集合表示为
$${\cap }_{i=1}^m\overline{A_{p_i}}$$
应用容斥原理得到
$${\cap }_{i=1}^m\overline{A_{p_i}}=S_n-A_{p_1}-\cdots +(-1{)}^m|A_{p_1}\cap A_{p_2}\cap \cdots A_{p_m}|$$
显然有
$$p_1\mid s\wedge p_2\mid s\Rightarrow p_1{p}_2\mid s$$
因此
$$|A_{p_1}\cap A_{p_2}\cdots \cap A_{p_m}|=\frac{n}{p_1{p}_2\cdots p_m}$$
计数后的结果
$$\begin{gathered} |{\cap }_{i=1}^m\overline{A_{p_i}}|=n-\frac{n}{p_1}-\cdots -\frac{n}{p_m}+ \\ \frac{n}{p_1{p}_2}+\frac{n}{p_1{p}_3}+\cdots +\frac{n}{p_{m-1}{p}_m} \\ \cdots +(-1{)}^m\frac{n}{p_1{p}_2} \end{gathered}$$
整理后得到
$$\varphi (n)=|{\cap }_{i=1}^m\overline{A_{p_i}}|=n\times {\Pi }_{i=1}^m(1-\frac{1}{p_i})$$
到此，我们导出了欧拉函数的定义式；下面直接带进去算就行了。

假设$ab$的唯一分解式如下
$$\begin{gathered} a={\Pi }_{i=1}^s{p}_i^{x_i} \\ b={\Pi }_{j=1}^t{q}_j^{y_j} \end{gathered}$$
由于$\gcd (a,b)=1$, 因此
∀ i ∈ { 1 , 2 , ⋯ , s } , j ∈ { 1 , 2 , ⋯ , t } ; p i ≠ q j \forall i \in \{ 1,2, \cdots,s\}, j \in \{ 1,2, \cdots,t\};\\ p_i \ne q_j ∀i∈{1,2,⋯,s},j∈{1,2,⋯,t};pi​=qj​

因此$ab$的唯一分解式可表示为
$$ab={\Pi }_{i=1}^s{p}_i^{x_i}{\Pi }_{j=1}^t{q}_j^{y_j}$$

综上可得
$$\begin{array}{rl}\varphi (ab)& =ab{\Pi }_{i=1}^s(1-\frac{1}{p_i}){\Pi }_{j=1}^t(1-\frac{1}{q_j})\\ & =a{\Pi }_{i=1}^s(1-\frac{1}{p_i})b{\Pi }_{j=1}^t(1-\frac{1}{q_j})\\ & =\varphi (a)\varphi (b)\end{array}$$

$Q.E.D$

3. 证明二：中国剩余定理

先引入一个引理 ，证明放在最后面；现在直接用就完了。
$$\gcd (a,x)=\gcd (b,x)=1\Rightarrow \gcd (ab,x)=1$$

设 S ( n ) = { 1 ≤ x ≤ n ∣ gcd ⁡ ( x , n ) = 1 } S(n) = \{ 1 \le x \le n | \gcd(x,n)=1\} S(n)={1≤x≤n∣gcd(x,n)=1},

$S(n)$表示所有与$n$互质的数的集合。

容易得到
$$\forall 1\le x\le ab,\gcd (ab,x)=1\Rightarrow \gcd (a,x)=\gcd (b,x)=1$$

因此
$$\gcd (a,x\mathrm{mod}a)=\gcd (b,x\mathrm{mod}b)=1$$

从而有$S(ab)$到$\{(x,y)|x\in S(a),y\in S(b)\}$的映射。

$$\forall 1\le x\le a,1\le y\le b,\gcd (a,x)=\gcd (b,y)=1;$$

根据中国剩余定理我们可以得到

$$\begin{gathered} \exists !1\le z\le ab,s.t. \\ \begin{array}{c}\{\begin{array}{l}z\equiv x(\mathrm{mod}a)\\ z\equiv y(\mathrm{mod}b)\end{array}\end{array} \end{gathered}$$
因此$\gcd (a,z)=\gcd (b,z)=1$, 根据引理可得

$\gcd (ab,z)=1$。

因此有从$\{(x,y)|x\in S(a),y\in S(b)\}$到$S(ab)$的映射。

综上，$\{(x,y)|x\in S(a),y\in S(b)\}$与$S(ab)$的大小一致，又由于

$|S(n)|=\varphi (n)$, 因此

$\gcd (a,b)=1\Rightarrow \varphi (ab)=\varphi (a)\varphi (b)$。

$Q.E.D$

4. 引理证明

$$\gcd (a,x)=\gcd (b,x)=1\Rightarrow \gcd (ab,x)=1$$
证明一： 裴蜀系数

由于$a,x$互质，那么根据裴蜀定理
$$\exists m_1,n_1\in Z,s.t.a{m}_1+x{n}_1=1$$
同理
$$\exists m_2,n_2\in Z,s.t.b{m}_2+x{n}_2=1$$
两式相乘
$$\begin{gathered} (a{m}_1+x{n}_1)(b{m}_2+x{n}_2)= \\ (m_1{m}_2)ab+(a{m}_1{n}_2+b{m}_2{n}_1+n_1{n}_{2}x)x=1 \end{gathered}$$
因此存在$m^{\prime }=m_1{m}_2,n^{\prime }=(a{m}_1{n}_2+b{m}_2{n}_1+n_1{n}_{2}x)$使得

$m^{\prime }ab+n^{\prime }x=1$; 因此$\gcd (ab,x)=1$。

证明二： 反证法

假设$\gcd (ab,x)=d>1$,

$d>1$，那么必有质数$p>1,p\mid d$ , $p\mid ab,p\mid x$。

因此要么$p\mid a$, 要么$p\mid b$。

进而$p\mid \gcd (a,x)$或者$p\mid \gcd (b,x)$,

而这与$\gcd (a,x)=\gcd (b,x)=1$矛盾，所以假设不成立，

$\gcd (ab,x)=1$。

$Q.E.D$

5. 参考

zhihu-WYXkk-Gauss