元祖ワシ的日記

wikipediaより

オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）は各正の整数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。慣例的に φ(n) と表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。

計算方法概略

簡単にするためまず$n$の素因数分解を$p_1 p_2 p_3 \cdots p_n$とし因子に平方数を含まないとします。 (つまり素数 $p_1, p_2, p_3, \cdots$の羃は1)

$1$から$n$のうち$p_1$の倍数の数が $n / p_1$個あり、 $p_2$の倍数が $n / p_2$あり……ということでこれらの数を$n$から引きます。しかし、これでは $p_1 p_2$など2つの素数の積の数を2回引いてしまうのでそれらを足します。しかし、これでは $p_1 p_2 p_3$のような3つの素数の積になってる数を足しすぎてしまうのでそれらをまた引きます……と考えていけば……

\begin{eqnarray} \phi(n) = n &-& (n / p_1 + n / p_2 + \cdots + n / p_n)\\ &+& (n / p_1p_2 + n / p_1p_3 + \cdots + n / p_{n-1}p_n)\\ &-& (n / p_1p_2p_3 + n / p_1p_2p_4 + \cdots + n / p_{n-2}p_{n-1}p_n)\\ &+& \cdots \end{eqnarray} この式の分母の素数の積は$n$の全ての約数を渡ることは明かです。$n$の約数$d$を素因数分解したとき、それが偶数個なら$n/d$を足し、奇数個なら$n/d$を引いていくという流れになります。なお、上記の式は以下のように書けます。 \begin{eqnarray} \phi(n) = n(1 - 1/p_1)(1 - 1/p_2)(1 - 1/p_3)\cdots(1 - 1/p_n) \end{eqnarray}

例

\begin{eqnarray} \phi(30) &= 30 - (30 / 2 + 30 / 3 + 30 / 5) + (30 / 6) + (30 / 10) + (30 / 15) - 30 / 30 = 8 \end{eqnarray}

平方数を含む場合ですが例えば $12$のときを考えれば$2$の倍数を除去したときに12の因数である$4$の倍数は既に除去されています。つまり、平方因子をもつ約数は考慮しなくてもよいのです。（つまり、素因数が何種類あるか？が重要）これはそのまま一般に拡張出来ます。実際上記の式は $n$の素因数分解を$p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$と分解される場合でも成立します。

$n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$の素因数をそれぞれの項に配分していけば

\begin{eqnarray} \phi(n) &=& p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}(1 - 1/p_1)(1 - 1/p_2)(1 - 1/p_3)\cdots(1 - 1/p_n)\\ &=&(p_1^{e_1} - p_1^{e_1-1}) (p_2^{e_2} - p_2^{e_2-1})\cdots (p_n^{e_n} - p_n^{e_n-1}) \end{eqnarray}

なお、上記の式はメビウス関数を使えば \begin{eqnarray} \phi(n) = \sum_{d|n}\mu({d}){\frac{n}{d}} \end{eqnarray} とも表わすことができます。メビウス関数$\mu({n})$は

• $n$が平方因数を含む場合は$\mu({n})=0$
• $n$が因数を偶数個含む場合は$\mu({n})=1$
• $n$が因数を奇数個含む場合は$\mu({n})=-1$

という関数です。

ここからメビウスの反転公式を使って

\begin{eqnarray} \sum_{d|n}\phi(d) = n \end{eqnarray} とか即座に得られるのがまた味わい深いですの。

以上Mathjaxのリハビリでした