本記事の内容
本記事は、オイラーのφ関数”だけ”の性質である「オイラーの\(\varphi\)関数に対して、ある整数の約数での和は元の整数と一致する」を証明する記事です。
本記事を読むに当たり、オイラーの\(\varphi\)関数について知っている必要があるため、以下の記事も合わせてご覧下さい。
前回、前々回の軽い復習 (読み飛ばしてOK)
そもそも、オイラーの\(\varphi\)関数とは何だったか？ということも含め、前回説明したことについて軽く復習します。
オイラー関数とは何か？
\(n\)以下の自然数に対し、\(n\)と互いに素な整数の個数を対応させる関数\(\varphi:\mathbb{N}\longrightarrow \mathbb{N}\)をオイラーの\(\varphi\)関数と呼ぶのです。
オイラーの\(\varphi\)関数
関数\(\varphi:\mathbb{N}\longrightarrow \mathbb{N}\)を、\(n\in\mathbb{N}\)に対して書き方は色々ありますが、例えば以下のように書くことができます。
\begin{eqnarray}
\varphi(n)&=&\left|\left\{ x\in\mathbb{N}\middle|x\leq n,\ \gcd(x,n)=1\right\}\right|\tag{1}\\
&=&\sum_{\substack{x\in\mathbb{N}\\ x\leq n\\ \gcd(x,n)=1}}1\tag{2}
\end{eqnarray}
オイラーの\(\varphi\)関数の性質
定理1.
\(\varphi:\mathbb{N}\longrightarrow\mathbb{N}\)をオイラーの\(\varphi\)関数、\(p\in\mathbb{N}\)を素数とする。このとき $$ \varphi(p)=p-1 $$ である。すなわち、\(p\)以下の自然数で、\(p\)と互いに素な自然数は\(p-1\)個存在する。定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その16を御覧ください。
定理２.
\(\varphi:\mathbb{N}\longrightarrow\mathbb{N}\)をオイラーの\(\varphi\)関数、\(p\in\mathbb{N}\)を素数、\(e\in\mathbb{N}\)とする。このとき $$ \varphi(p^e)=p^e-p^{e-1} $$ である。すなわち、\(p^e\)以下の自然数で、\(p^e\)と互いに素な自然数は\(p^e-p^{e-1}\)個存在する。定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その16を参照して下さい。
定理3.
\(n\in\mathbb{N}\)を定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その16を参照して下さい。
定理0.
\(\varphi:\mathbb{N}\longrightarrow\mathbb{N}\)をオイラーの\(\varphi\)関数とする。\(a,b\in\mathbb{N}\)に対して $$ \gcd(a,b)=1\ \Longrightarrow\ \varphi(ab)=\varphi(a)\cdot\varphi(b) $$定理0.の証明は【代数学の基礎シリーズ】初等整数論編 その17を御覧ください。
本記事で言いたいこと
一言で述べれば
定理4.
\(\varphi\)をオイラーの\(\varphi\)関数とする。このとき、 $$ \sum_{\substack{d\in\mathbb{N}\\d\mid n}}\varphi(d)=n $$ である。の証明です。
本題に入る前に (使う事実を予め証明する)
定理4.
\(a,b\in\mathbb{N}\)とする。また、 $$ a^\prime=\frac{a}{\gcd(a,b)},\quad b=\frac{b}{\gcd(a,b)} $$ とすれば、\(\gcd(a^\prime,b^\prime)=1\)、すなわち $$ \gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)} \right)=1 $$ である。定理4.の証明
\(d=\gcd(a,b)\)とします。
以下の事実を使います。
定理5.
2つ以上の整数の公約数は最大公約数の約数である。定理5.の証明は【代数学の基礎シリーズ】初等整数論編 その3を御覧ください。
定理5.から、\(a\)と\(b\)の任意の公約数\(e\)は\(d\)の約数です。
故に、\(\displaystyle \frac{a}{\gcd(a,b)}\)と\(\displaystyle\frac{b}{\gcd(a,b)}\)に公約数は存在しません(最大公約数で割ることで約数の全てを割っていることになるから)。
したがって、成り立ちます。
定理4.の証明終わり
オイラーの\(\varphi\)関数に対して、ある整数の約数での和は元の整数と一致することの証明
では、本題に入りましょう。
主張を再掲しておきます。
定理5.
\(\varphi\)をオイラーの\(\varphi\)関数とする。このとき、 $$ \sum_{\substack{d\in\mathbb{N}\\d\mid n}}\varphi(d)=n $$ である。この\(\displaystyle\sum_{d\mid n}\)という記法については【代数学の基礎シリーズ】初等整数論編 その16を御覧ください。
定理5.の証明
\(n\in\mathbb{N}\)の任意の約数を\(d\in\mathbb{N}\)とするとき、\(n\)個の正の整数\(1,2,\cdots,n\)の中に\(\gcd(x,n)=d\)であるような\(x\in\mathbb{N}\)は何個存在するだろうか？ということを考えます。
\(\gcd(x,n)=d\)を満たすような\(x\in\mathbb{N}\)は
$$
(\exists x^\prime,\ n^\prime\in\mathbb{N})\ {\rm s.t.}\ x=dx^\prime,\ n=dn^\prime
$$
と書くことができます。
そして、定理4.から\(\gcd(x^\prime,n^\prime)=1\)が成り立ちます。
したがって、\(\gcd(x,n)=d\)となるような\(x\in\mathbb{N}\)の個数は\(\gcd(x^\prime,n^\prime)=1\)なる\(x^\prime\in\mathbb{N}\)の個数と一致します。
すなわち、\(\displaystyle\varphi(n^\prime)=\varphi\left( \frac{n}{d}\right)\)と一致します。
故に、\(n\)個の自然数\(x=1,2,\cdots,\)をそれぞれに対応する\(\gcd(x,n)=d\)で分類すると、
- \(d=1\)のとき
\(\gcd(x,n)=d=1\)であるような\(x\)の個数は\(\displaystyle\varphi\left( \frac{n}{d}\right)=\varphi\left(\frac{n}{1} \right)=\varphi(n)\)個 - \(d=d_1\)のとき
\(\gcd(x,n)=d=d_1\)であるような\(x\)の個数は\(\displaystyle\varphi\left( \frac{n}{d_1}\right)\)個 - \(d=d_2\)のとき
\(d=d_1\)のとき
\(\gcd(x,n)=d=d_1\)であるような\(x\)の個数は\(\displaystyle\varphi\left( \frac{n}{d_1}\right)\)個 - \(d=n\)のとき
\(\gcd(x,n)=d=n\)であるような\(x\)の個数は\(\displaystyle\varphi\left( \frac{n}{d}\right)=\varphi\left(\frac{n}{n} \right)=\varphi(1)\)個
すなわち、\(d\)を順々に増やしていくと、最後には\(\varphi(1)=1\)個になります。
これらの個数の総和は\(n\)でなければならないから
$$
\varphi(n)+\varphi\left( \frac{n}{d_1}\right)+\varphi\left( \frac{n}{d_2}\right)+\cdots+\varphi(1)=n
$$
が成り立ちます。
\(\displaystyle n,\frac{n}{d_1},\frac{n}{d_2},\cdots,1\)は、\(n\)の全ての約数\(1,d_1,d_2,\cdots,n\)の余約数、すなわち\(1\)と\(n\)を除いて約数でないものですから、全体としては\(n\)の全ての約数です。
したがって、
$$
\sum_{\substack{d\in\mathbb{N}\\ d\mid n}}\varphi(d)=n
$$
となるわけです。
定理5.の証明終わり
確かめてみる
\(n=15\)のとき、定理5.を確かめてみましょう。
\(d\mid n\)なる\(d\in\mathbb{N}\)は、\(n=15\)ですので、
$$
d=1,3,5,15
$$
です。
一方で、
\begin{eqnarray}
\varphi(1)&=&1,\ \varphi(3)=2,\ \varphi(5)=4,\ \varphi(15)=8
\end{eqnarray}
です。
和を取れば、\(1+2+4+8=15=n\)となっています。
たしかに成り立っています。
ちょっと先取り (オイラーの\(\varphi\)関数は特殊な関数)
詳しくは次回以降で解説しますが、今回解説した定理5.はオイラーの\(\varphi\)関数ならではの性質です。
つまり、オイラーの\(\varphi\)関数以外で、定理5.のような性質を持つ数論的関数は存在しないのです。
言い換えれば、任意の\(n\in\mathbb{N}\)に対して
$$
\sum_{\substack{d\in\mathbb{N}\\d\mid n}}\psi(d)=n
$$
であるときは、\(\psi=\phi\)と断言することができるのです。
皆様のコメントを下さい！
数学に限らず、なにか作業をしていると、煮詰まったり疲れたりしますよね。
そんなとき、どう息抜きをしていますか？
是非コメントで教えてください！
結
今回は、オイラーの\(\varphi\)関数特有の性質である「オイラーの\(\varphi\)関数に対して、ある整数の約数での和は元の整数と一致する」を証明しました。
証明方法はシンプルで、平たく言えば単に数え上げるという方法です。
今回解説した性質はオイラーの\(\varphi\)関数特有のもので、今回解説した性質を満たすような数論的関数はオイラーの\(\varphi\)関数のみです。
次回以降は、「メビウス関数」について解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
初等整数論について、以下の書籍をオススメします！
コメントをする