当前位置：首页 > news >正文

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

news 来源：原创 2025/8/6 2:52:47

文章目录

- - 1. 简介
  - 2. 证明一：唯一分解定理+容斥原理
  - 3. 证明二：中国剩余定理
  - 4. 引理证明
  - 5. 参考

1. 简介

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

如
$\phi(6)=2 \quad (1\ 5)\\ \phi(12) = 4\quad (1\ 5\ 7 \ 11)$

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

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

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

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

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

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

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

$n=\Pi_{i=1}^{m}p_i^{a_i}$

我们令全集
$S_n := \{1,2,\cdots,n\}$
我们可以将 $S_n$ 中 $n$ 的因子根据是是否整除素数 $p_i$ 进行分类
$A_{p_i} := \{x|\ x = kp_i \land x \in S_n, k \in 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\ \land p_2 \mid s \Rightarrow p_1p_2 \mid s$
因此
$|A_{p_1} \cap A_{p_2} \cdots \cap A_{p_m}| = \frac{n}{p_1p_2\cdots p_m}$
计数后的结果
$|\cap_{i=1}^m \overline{A_{p_i}}| =n -\frac{n}{p_1} - \cdots - \frac{n}{p_m} + \\ \frac{n}{p_1p_2} +\frac{n}{p_1p_3}+ \cdots + \frac{n}{p_{m-1}p_m}\\ \cdots +(-1)^m \frac{n}{p_1p_2}$
整理后得到
$\phi(n) =|\cap_{i=1}^m \overline{A_{p_i}}| = n \times \Pi _{i=1}^{m}(1-\frac{1}{p_i})$
到此，我们导出了欧拉函数的定义式；下面直接带进去算就行了。

假设 $a\ b$ 的唯一分解式如下
$\Pi_{i=1}^s p_i^{x_i} \\ b = \Pi_{j=1}^t q_j^{y_j}$
由于 $\gcd(a, b) =1$ , 因此
$\forall i \in \{ 1,2, \cdots,s\}, j \in \{ 1,2, \cdots,t\};\\ p_i \ne q_j$

因此 $ab$ 的唯一分解式可表示为
$\Pi_{i=1}^s p_i^{x_i} \Pi_{j=1}^tq_j^{y_j}$

综上可得
$\begin{align*} \phi(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}) \\ &=\phi(a)\phi(b) \end{align*}$

$Q . E . D$

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

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

设 $\{ 1 \le x \le 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 \bmod a) = \gcd(b, x \bmod 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;$

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

$\exists! \ 1 \le z \le ab, s.t. \\ \begin{equation*} \begin{cases} z \equiv x \quad( \bmod\ a) \\ z \equiv y \quad (\bmod \ b) \end{cases} \end{equation*}$
因此 $\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)$ 的大小一致，又由于

$\phi(n)$ , 因此

$\gcd(a,b) =1 \Rightarrow \phi(ab) =\phi(a)\phi(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. \quad am_1+xn_1=1$
同理
$\exists m_2,n_2 \in Z,\ s.t. \quad bm_2+xn_2=1$
两式相乘
$am_1+xn_1)(bm_2+xn_2) =\\ (m_1m_2) ab +(am_1n_2+bm_2n_1+n_1n_2x) x=1$
因此存在 $m' =m_1m_2,n'=(am_1n_2+bm_2n_1+n_1n_2x)$ 使得

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

证明二：反证法

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

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

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

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

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

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

$Q . E . D$

5. 参考

zhihu-WYXkk-Gauss

文章目录

1. 简介

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

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

4. 引理证明

5. 参考

相关文章：