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

まず，$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}$

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

$n=p^k$ の場合，$\phi(n)$ は $n$ 以下の正の整数で $p$ の倍数でないものの数なので $\phi(n)=p^k\left(1-\dfrac{1}{p}\right)$ となる。

$m,n$ が互いに素なとき，$\phi(mn)=\phi(m)\phi(n)$ であることを示す。

$mn$ 以下の正の整数を $m$ で割ったあまりごとで $m$ 個の集合にわける。余りが $r$ である集合を $A_r=\{r,m+r,2m+r,\dots,(n-1)m+r\}$ とおく。$A_r$ ごとに「$mn$ と互いに素」なものの数を数える。

• $r$ と $m$ が互いに素でない場合。$r$ と $m$ の最大公約数を $d$ とおくと，$A_r$ に属する整数はすべて $d$ の倍数なので $mn$ と互いに素なものはない。
• $r$ と $m$ が互いに素な場合。$mn$ と互いに素なものの個数は $\phi(n)$ 個（なぜなら $A_r$ の要素はすべて $m$ と互いに素であり，さらに $A_r$ の要素を $n$ で割った余りはすべて異なり（→補足）$0$ から $n-1$ を尽くすので $\phi(n)$ 個が $n$ と互いに素）。

後者のようなグループは $\phi(m)$ 個あるので，結局 $\phi(mn)=\phi(m)\phi(n)$

$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ と素因数分解されるとき，乗法性を繰り返し使うと

$\phi(n)=\phi(p_1^{e_1})\phi(p_2^{e_2})\cdots\phi(p_k^{e_k})$

ここで右辺の各項に第一段階の結果を使うと，求めたい公式を得る。

$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$ の約数であることに注意すると目標の式を得る。

$1$ 以上 $n$ 以下で $n$ と互いに素な整数を $\{m_1,m_2,\dots,m_{\phi(n)}\}$ とおく。

$n$ で割った余りで見ると， $\{am_1,am_2,\dots,am_{\phi(n)}\}$ という集合は $\{m_1,m_2,\dots,m_{\phi(n)}\}$ と一致する（→補足）。よって，すべて掛け算すると

$a^{\phi(n)}m_1m_2\cdots m_{\phi(n)}\equiv m_1m_2\cdots m_{\phi(n)} \pmod{n}$

ここで，各 $m_i$ は $n$ と互いに素なので，合同式の両辺を $m_1m_2\cdots m_{\phi(n)}$ で割って

$a^{\phi(n)}\equiv 1\pmod{n}$