１からｎまでの数のうち、ｎと互いに素なものの個数を数えたものを
オイラー関数というのでした。
このオイラー関数の和について、
実はびっくり仰天の事実が成り立ちます。
オイラー関数の和を観察
オイラー関数とは、１からｎまでの数のうち、ｎと互いに素なものの個数を数えるものです。
例えば$\phi(6)$を考えると、
１，２，３，４，５，６のうち
６と互いに素であるのは１，５なので、
$\phi(6)=2$です。
ところで、６の約数は、
１，２，３，６です。
$\phi(1)=1$
$\phi(2)=1$
$\phi(3)=2$
$\phi(6)=2$
です。
よって、
$\phi(1)+\phi(2)+\phi(3)+\phi(6)=1+1+2+2=6$
です。
要するに、
$\phi(1)+\phi(2)+\phi(3)+\phi(6)=6$
です。
ヤバくないですか？
①自然数ｎを取ってきて、
②それの約数を並べて、
③オイラー関数の和を取ると
④ｎ自身になる
ヤバすぎるでしょ！！
今回はこれを証明します。
オイラー関数の和の性質の証明
（定理）
$n$を自然数とし、$n$の約数を$d_1(=1), d_2, d_3, \cdots, d_k(=n)$とする。
このとき、
$\phi(d_1)+\phi(d_2)+\cdots + \phi(n)=n$
が成り立つ。
さて、証明をしていきますが、いつものごとく何から手を付ければよいのやら見当もつきません。
難しい問題に遭遇した時は、
何が難しい原因なのか分析することが大切です。
今回の場合は、
$n$の約数$d_1(=1), d_2, d_3, \cdots, d_k(=n)$たちです。
具体的に$n=6$の場合を考えます。
１，２，３，４，５，６のうち、
６の約数であるものが１，２，３，６であることはすぐに分かります。
しかし、これを文字で表そうと思うと途端に難しくなるのです。
１，２，３，…, ｎのうち、
ｎの約数はどれか？
…ちょっとわかんないなぁ。
ここです。これが今回の証明が難しい原因です。
そこで、この問題を解決するために分数を使います。
具体例を見ると分かりやすいので、６の場合を考えましょう。
１，２，３，４，５，６の中から、
機械的な操作でうまく１，２，３，６だけ取り出したいわけです。
１，２，３，４，５，６を６で割りましょう。
$\dfrac{1}{6}, \dfrac{2}{6}, \dfrac{3}{6}, \dfrac{4}{6}, \dfrac{5}{6}, \dfrac{6}{6}$
約分すると、
$\dfrac{1}{6}, \dfrac{1}{3}, \dfrac{1}{2}, \dfrac{2}{3}, \dfrac{5}{6}, \dfrac{1}{1}$
どうです？
分母に１，２，３，６が上手く取り出せています！
しかも、分母に注目すると面白い発見があります。
分母が１である分数は１個です。
分母が２である分数は１個です。
分母が３である分数は２個で、
分母が６である分数は２個です。
ここで、
$\phi(1)+\phi(2)+\phi(3)+\phi(6)=1+1+2+2=6$
でした。
例えば３に着目すると、
（分母が３である分数の個数）$=\phi(3)$
が成立しています。
ヤバくないですか？
この発想を上手く使って証明を進めていきましょう！
（証明）
$n$の約数を$d_i$ $i=1, 2, \cdots, k$とおく。
$1, 2, 3, \cdots, d_i$のうち、$d_i$と互いに素なものを集めた集合を$A_{d_i}$とする。
$A_{d_i}$には$\phi(d_i)$個の要素があることになる。
ここで、
$\dfrac{1}{n}, \dfrac{2}{n}, \dfrac{3}{n}, \cdots, \dfrac{n-1}{n}, \dfrac{n}{n}$
を考える。
これらの分数が既約分数になるまで約分したとき、
分母となる数は必ず$n$の約数でなければならないので、
$d_1$から$d_k$までのいずれかである。
ここで、約分したときの分母が$d_i$であるものを考える。
分数は既約分数になるまで約分されているので、
分母が$d_i$となる分数の分子は$d_i$と互いに素でなければならない$\cdots ①$
逆に、ある自然数$a$ $1≦a≦d_i$
が$d_i$と互いに素であるならば、
$\dfrac{a}{d_i}=\dfrac{a×\dfrac{n}{d_i}}{d_i×\dfrac{n}{d_i}}=\dfrac{a×\dfrac{n}{d_i}}{n}$
となる。
$1$から$d_i$までの数で、$d_i$と互いに素なものの数は$\phi(d_i)$である。
ここで、分子に着目する。
$a×\dfrac{n}{d_i}=n×\dfrac{a}{d_i}$
であり、$0<\dfrac{a}{d_i}≦1$であるので、全体を$n$倍すると、
$0<n×\dfrac{a}{d_i}≦n$である。
ゆえに、
$\dfrac{a}{d_i}=\dfrac{a×\dfrac{n}{d_i}}{n}$
は
$\dfrac{1}{n}, \dfrac{2}{n}, \dfrac{3}{n}, \cdots, \dfrac{n-1}{n}, \dfrac{n}{n}$
のいずれかである$\cdots ②$
$\dfrac{1}{n}, \dfrac{2}{n}, \dfrac{3}{n}, \cdots, \dfrac{n-1}{n}, \dfrac{n}{n}$のうち
分母が$d_i$となる分数の個数を$B_{d_i}$とする。すると、
①と②より、$B_{d_i}=\phi(d_i)$が成立する。
したがって、
$B_{d_1}+B_{d_2}+\cdots B_{d_k}=\phi(d_1)+\phi(d_2)+\cdots +\phi(d_k)$
となり、
$n=\phi(d_1)+\phi(d_2)+\cdots + \phi(n)$
が成り立つ。
（証明終了）
まとめ
いかがでしたか？
今回のポイントをまとめておきます
・オイラー関数ヤバい
以上
ではまた次回の記事でお会いしましょう！
コメント