歐拉計數函數

筆記／歐拉計數函數

本文簡介歐拉計數函數（Euler’s to­tient func­tion）。

歐拉計數函數

對非負整數 $n \comma$定義 $[n] = \{0 \cm 1, \ldots \cm n \varminus 1\} \period$

對任意正整數 $n \comma$我們定義 $\phi(n)$ 為 $[n] = \{0 \cm 1, \ldots \cm n \varminus 1\}$ 中與 $n$ 互質的整數個數。此時函數 $\phi \colon \{1 \cm 2, \ldots\} \to \ZZ$ 即為歐拉計數函數（Euler’s to­tient func­tion）。

定理 1　設 $n_0 \jcomma n_1$ 為兩個互質的正整數。若 $m$ 為正整數，則 $m$ 與 $n_0n_1$ 互質的充要條件為 $m$ 與 $n_0$ 互質且 $m$ 與 $n_1$ 互質。

證明　首先假設 $m$ 與 $n_0n_1$ 互質。若存在 $i \in \{0, 1\}$ 使得 $m$ 與 $n_i$ 不互質，則我們能找到 $m$ 與 $n_i$ 的一個公因數 $d$ 滿足 $d \geq 2 \semicolon$此時 $d$ 也整除 $n_0n_1 \comma$故 $m$ 與 $n_0n_1$ 不互質，矛盾。

接著假設 $m$ 與各個 $n_i$ 皆互質，其中 $i \in \{0, 1\} \period$若 $m$ 與 $n_0n_1$ 不互質，則我們能找到 $m$ 與 $n_0n_1$ 的一個公因數 $d$ 滿足 $d \geq 2 \semicolon$此時由於 $m$ 與 $n_0$ 互質，由歐幾里得引理（見貝祖引理與歐幾里得引理）可知 $d$ 會整除 $n_1 \comma$即 $m$ 與 $n_1$ 不互質，矛盾。

定理 2　設 $n_0 \jcomma n_1$ 為兩個互質的正整數，則 $\phi(n_0n_1) = \phi(n_0) \phi(n_1) \period$

證明　由貝祖引理（見貝祖引理與歐幾里得引理），我們可以找到正整數 $r_0 \jcomma r_1$ 使得 $n_0r_0 + n_1r_1 = 1 \period$

設 $f \colon [n_0] \times [n_1] \to [n_0n_1]$ 為滿足 \[\begin{split}f(a_0, a_1) = (a_0n_1r_1 + a_1n_0r_0) \bmod (n_0n_1)\end{split}\] 的函數。對任意 $a_0 \in [n_0]$ 與 $a_1 \in [n_1] \comma$我們有 \[\begin{split}f(a_0, a_1) \bmod n_0 = a_0 \comma \\ f(a_0, a_1) \bmod n_1 = a_1 \comma\end{split}\]故 $f$ 是對射（bi­jec­tion）。也就是說，對任意 $m \in [n_0n_1] \comma$均存在唯一一組 $(a_0, a_1) \in [n_0] \times [n_1]$ 使得 $f(a_0, a_1) = m \period$

由定理 1 可知，一正整數 $m$ 與 $n_0n_1$ 互質若且唯若 $m$ 與 $n_0 \jcomma n_1$ 均互質，其等價於：

由於滿足以上條件的 \[\begin{split}(a_0, a_1) \in [n_0] \times [n_1]\end{split}\] 共有 $\phi(n_0) \cdot \phi(n_1)$ 個，故總共有 $\phi(n_0) \cdot \phi(n_1)$ 個 $m \in [n_0n_1]$ 與 $n_0n_1$ 互質。因而 \[\begin{split}\phi(n_0n_1) = \phi(n_0) \cdot \phi(n_1) \comma\end{split}\]定理得證。

定理 3　設 $p$ 為質數，$a$ 為正整數，則 $\phi(p^a) = p^a - p^{a-1} \period$

證明　對任意 $m \in [p^a] \comma$$m$ 與 $p^a$ 不互質的充要條件為 $p$ 整除 $m \period$由於 $[p^a]$ 中共有 $p^{a-1}$ 個 $p$ 的倍數，故 $\phi(p^a) = p^a - p^{a-1} \period$

定理 4　設 $n$ 為正整數，且 \[\begin{split}n = \prod_{i=0}^{r-1} p_i^{a_i} \comma\end{split}\]其中 $r \geq 0 \comma$且 $p_0 \cm p_1, \ldots \cm p_{r-1}$ 為相異質數，$a_0 \cm a_1, \ldots \cm a_{r-1}$ 為正整數。則我們有 \[\begin{split}\phi(n) = \prod_{i=0}^{r-1} \Bigl(p_i^{a_i} \varminus p_i^{a_i-1}\Bigr) \period\end{split}\]

證明　我們對 $r$ 使用數學歸納法。我們有 $\phi(1) = 1 \comma$故定理在 $r = 0$ 時成立。

接著假設 $r$ 為非負整數，且對任意相異質數 $p_0 \cm p_1, \ldots \cm p_{r-1}$ 與任意正整數 $a_0 \cm a_1, \ldots \cm a_{r-1}$ 均有 \[\begin{split}\phi\Biggl(\prod_{i=0}^{r-1}p_i^{a_i}\Biggr) = \prod_{i=0}^{r-1} \Bigl(p_i^{a_i} \varminus p_i^{a_i-1}\Bigr) \period\end{split}\]

此時對任意任意相異質數 $p_0 \cm p_1, \ldots \cm p_r$ 與任意正整數 $a_0 \cm a_1, \ldots \cm a_r \comma$由定理 2 與定理 3 可得 \[\begin{split}&\mkern5mu\phi\Biggl(\prod_{i=0}^rp_i^{a_i}\Biggr) \\ &= \phi\Biggl(\Biggl(\prod_{i=0}^{r-1}p_i^{a_i}\mkern-2mu\Biggr)p_r^{a_r}\Biggr) \\ &= \phi\Biggl(\prod_{i=0}^{r-1}p_i^{a_i}\Biggr)\phi(p_r^{a_r}) \\ &= \Biggl(\prod_{i=0}^{r-1} \Bigl(p_i^{a_i} \varminus p_i^{a_i-1}\Bigr)\Biggr)\Bigl(p_r^{a_r} \varminus p_r^{a_r-1}\Bigr) \\ &= \prod_{i=0}^{r} \Bigl(p_i^{a_i} \varminus p_i^{a_i-1}\Bigr) \comma\end{split}\]

因而定理得證。

參考資料

  1. David M. Burton. Elementary number theory. McGraw-Hill, seventh edition, 2010.