跳转至

欧拉函数（数论）

欧拉函数 \(\varphi(n)\) 也称为欧拉总计函数（Euler's totient function），是小于等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。

将正整数 \(n\) 分解为若干个互不相同的质因数 \(p_i\) 的乘积

\[ n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \]

则

\[ \varphi(n) = n \prod_{i=1}^{r} \left (1 - \frac{1}{p_i} \right ) \]

欧拉函数是 积性函数。

证明

这个公式可以用容斥原理证明，也可以像下面一样从特殊情况开始不断一般化来得到。

情况 1

当 \(n=1\) 时

\[ \varphi(1)=1 \]

情况 2

当 \(n\) 为质数时，\(n\) 和小于它的每个数都互质，所以

\[ \varphi(n)=n-1 \]

情况 3

当 \(n=p^k\) 且 \(p\) 为质数时，小于等于 \(p^k\) 的数中 \(p\) 的整数倍有

\[ 1 \times p, \ 2 \times p, \ 3 \times p, \dots, \ p^{k-1} \times p \]

\(p^k\) 和它们以外的数互质，所以

\[ \varphi \left (p^k \right)=p^k - p^{k-1} \]

情况 4

当 \(n=pq\) 且 \(p,q\) 互质时，设 \(0<N<pq\) 且 \(N\) 与 \(pq\) 互质，那么 \(\varphi(pq)\) 就等于 \(N\) 的个数。\(N\) 可以写成

\[ N=k_1p+a_1=k_2q+a_2 \]

其中 \(0<a_1 < p\) 且 \(0<a_2 < q\)，因此 \(N\) 满足线性 同余 方程组

\[ \left\{\begin{matrix} N \equiv a_1 \pmod{p} \\ N \equiv a_2 \pmod{q} \end{matrix}\right. \]

由 中国剩余定理，通解为

\[ N=kpq + a_1 t_1 q + a_2 t_2 p, k \in \mathbb{Z} \]

其中 \(t_1,t_2\) 是固定的整数。当给定 \(a_1,a_2\) 时，上式是周期为 \(pq\) 的序列，只存在唯一的 \(k\) 使得 \(0<N<pq\)，所以 \(N\) 与二元组 \((a_1,a_2)\) 一一对应，那么使得 \(N\) 与 \(pq\) 互质的 \((a_1,a_2)\) 的个数就是 \(N\) 的个数。

\(N\) 与 \(pq\) 互质当且仅当 \(N\) 与 \(p,q\) 分别互质。根据 欧几里得算法

\[ \gcd(N,p)=\gcd(p,N \bmod p)=\gcd(p, a_1) \]

所以 \(N,p\) 互质当且仅当 \(p,a_1\) 互质，满足条件的 \(a_1\) 有 \(\varphi(p)\) 个。同理，使得 \(N,q\) 互质的 \(a_2\) 有 \(\varphi(q)\) 个。由乘法原理，同时满足两个条件的二元组 \((a_1,a_2)\) 有 \(\varphi(p)\varphi(q)\) 个，所以

\[ \varphi(pq)=\varphi(p)\varphi(q) \]

一般情况

由 算术基本定理，正整数 \(n\) 可分解为质因数乘积

\[ n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \]

则

\[ \begin{align} \varphi(n) &= \varphi \left ( \prod_{i=1}^{r}p_i^{k_i} \right ) \\ &= \prod_{i=1}^{r} \varphi \left (p_i^{k_i} \right) \\ &= \prod_{i=1}^{r} \left ( p_i^{k_i} - p_i^{k_i-1} \right ) \\ &= \prod_{i=1}^{r} p_i^{k_i}\left (1 - \frac{1}{p_i} \right ) \\ &= n \prod_{i=1}^{r} \left (1 - \frac{1}{p_i} \right ) \end{align} \]

相关文章