定義

オイラーのファイ関数 $\phi(n)$ とは、自然数 $n$ に対して、 $1 \sim n-1$ の中で $n$ と互いに素なものの個数として定義される。例えば

$\begin{eqnarray} \phi(4) &=& 2\ (1, 2) \\ \phi(5) &=& 4\ (1, 2, 3, 4) \\ \phi(6) &=& 2\ (1, 5) \\ \phi(7) &=& 6\ (1, 2, 3, 4, 5, 6) \\ \end{eqnarray}$

定理: 素数に関するファイ関数

明らかに素数 $p$ の場合は $1 \sim p-1$ の全てと互いに素なので

$\begin{eqnarray} \phi(p) = p-1 \end{eqnarray}$

定理: 素因数分解とファイ関数の関係性

$n$ が $n = p_{1}^{r_{1}} \times p_{2}^{r_{2}} \times \cdots p_{m}^{r_{m}}$ と素因数分解されるとすると

$\begin{eqnarray} \phi(n) = n\prod_{i=1}^{m}\left(1-\frac{1}{p_{i}}\right) \end{eqnarray}$

となる。感覚的なイメージとしては

$\begin{eqnarray} \phi(n) &=& (1 \sim n のうちp_{1}, p_{2}, \cdots p_{m}のいずれの倍数でもない数の個数) \\ &=& n \times (p_{1}の倍数でない確率) \times (p_{2}の倍数でない確率) \times \cdots (p_{m}の倍数でない確率) \\ &=& n \prod_{i=1}^{m} (p_{i}の倍数でない確率) \\ &=& n\prod_{i=1}^{m} (1-p_{i}の倍数である確率) \\ &=& n\prod_{i=1}^{m} \left(1-\frac{1}{p_{i}}\right) \\ \end{eqnarray}$

として理解できる。

定理: 掛け算に関する性質

$n$ と $m$ が互いに素である場合、

$\begin{eqnarray} \phi(nm) = \phi(n) \times \phi(m) \end{eqnarray}$

となる。証明としては $n$ と $m$ の素因数分解

$\begin{eqnarray} n &=& p_{1}^{r_{1}} \times p_{2}^{r_{2}} \times \cdots p_{m}^{r_{m}} \\ m &=& q_{1}^{s_{1}} \times q_{2}^{s_{2}} \times \cdots q_{k}^{s_{k}} \end{eqnarray}$

に共通の素因数はないはずなので、 $nm$ の素因数分解は

$\begin{eqnarray} nm = p_{1}^{r_{1}} \times p_{2}^{r_{2}} \times \cdots p_{m}^{r_{m}} \times q_{1}^{s_{1}} \times q_{2}^{s_{2}} \times \cdots q_{k}^{s_{k}} \end{eqnarray}$

となるはずである。したがって

$\begin{eqnarray} \phi(nm) &=& nm\prod_{i=1}^{m}\left(1-\frac{1}{p_{i}}\right) \prod_{i=1}^{k} \left( 1-\frac{1}{q_{i}}\right) \\ &=& n\prod_{i=1}^{m}\left(1-\frac{1}{p_{i}}\right) \times m \prod_{i=1}^{k} \left( 1-\frac{1}{q_{i}}\right) \\ &=& \phi(n) \times \phi(m) \end{eqnarray}$