オイラーのファイ関数のイメージ

まず，$1$ から $n$ の中で $p_1$ と互いに素なものの割合は，$\dfrac{p_1-1}{p_1}$ 。

生き残った $n\left(1-\dfrac{1}{p_1}\right)$ 個の中で $p_2$ と互いに素なものの割合は，$\dfrac{p_2-1}{p_2}\cdots(1)$

さらに生き残った $n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)$ 個の中で $p_3$ と互いに素なものの割合は，$\dfrac{p_3-1}{p_3}$

これを繰り返すとオイラーのファイ関数の公式を得る。

$A=\{1,2,\cdots,n\}$ とする。 $a\in A$ と $n$ の約数 $d$ について，

$a$ と $n$ との最大公約数が $d$

$\iff$

$\dfrac{a}{d}$ が整数かつ $\dfrac{a}{d}$ と $\dfrac{n}{d}$ は互いに素

$\iff$

$\dfrac{a}{d}$ が $1,2,\cdots,\dfrac{n}{d}$ のいずれか，かつ $\dfrac{a}{d}$ と $\dfrac{n}{d}$ は互いに素

一番最後の条件を満たす $a$ の個数は，$\phi\left(\dfrac{n}{d}\right)$ である。

よって，$A$ の要素を $n$ との最大公約数 $d$ でグループ分けすることにより，

$n=\displaystyle\sum_{d\mid n}\phi\left(\dfrac{n}{d}\right)$

が分かる。 $d$ が $n$ の約数 $\iff \dfrac{n}{d}$ が $n$ の約数であることに注意すると目標の式を得る。