オイラーのφ関数とメビウス関数の関係オイラーのφ関数の積表示の別証明

本記事の内容
本記事で言いたいこと
オイラーの $\varphi$ 関数とメビウス関数の軽い復習
1. オイラーの $\varphi$ 関数
2. メビウス関数
オイラーの $\varphi$ 関数とメビウス関数の関係
1. 主張の明示 (再掲)とその証明
オイラーの $\varphi$ 関数の積表示の別証明
皆様のコメントをください！
結

本記事の内容

本記事は、オイラーの $\varphi$ 関数とメビウス関数の関係として代表的なものについて解説します。

本記事を読むに当たり、オイラーの $\varphi$ 関数及びメビウス関数について知っている必要があるため、以下の記事も合わせてご覧ください。

↓オイラーの $\varphi$ 関数の記事

↓メビウス関数の記事

本記事で言いたいこと

本記事で言いたいことは

定理1.

$\varphi:\mathbb{N}\longrightarrow \mathbb{N}$ をオイラーの

$\varphi$ 関数、

$\mu:\mathbb{N}\longrightarrow \left\{ -1,0,1\right\}$ をメビウス関数とする。このとき、

$\varphi(n)=\sum_{d\mid n}\mu\left(\frac{n}{d} \right)d=\sum_{d\mid n}\mu(d)\frac{n}{d}$ である。

の証明及び

定理2.

$n\in\mathbb{N}$ を

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\quad$ (

$i=1,2,\cdots,k$ に対して

$p_i\in\mathbb{N}$ は素数、

$a_i\in\mathbb{N}$ )

と素因数分解したとする。このとき、

$\varphi:\mathbb{N}\longrightarrow\mathbb{N}$ をオイラーの

$\varphi$ 関数とするならば

$\varphi(n)=n\left( 1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2} \right)\cdots\left( 1-\frac{1}{p_k}\right)$ である。

の別証明です。

定理2.のメビウス関数を使わない証明については【代数学の基礎シリーズ】初等整数論編その16を御覧ください。

オイラーの $\varphi$ 関数とメビウス関数の軽い復習

「もう知ってるよ」という方はオイラーの $\varphi$ 関数とメビウス関数の関係まで飛んでください。

オイラーの $\varphi$ 関数

$n$ 以下の自然数に対し、 $n$ と互いに素な整数の個数を対応させる関数 $\varphi:\mathbb{N}\longrightarrow \mathbb{N}$ をオイラーの $\varphi$ 関数と呼ぶのでした。

オイラーの $\varphi$ 関数

関数

$\varphi:\mathbb{N}\longrightarrow \mathbb{N}$ を、

$n\in\mathbb{N}$ に対して

$\varphi(n)=$

$n$ 以下の自然数のうち、

$n$ と互いに素な自然数の個数

で定める。この関数

$\varphi$ をオイラーの $\varphi$ 関数、または単にオイラー関数という。

書き方は色々ありますが、例えば以下のように書くことができます。

$\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}$

メビウス関数

$n\in\mathbb{N}$ に対して、 $n=1$ であれば $1$ を対応させます。
すなわち $\mu(1)=1$ と定めます。

$n\neq1$ であるとき、 $n$ を素因数分解して
$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$
と書いたとしましょう。
ただし、 $p_1<p_2<\cdots<p_k$ は素数で、 $a_1\in\mathbb{N}$ です。

このとき、任意の $1\leq i\leq k$ なる $i\in\mathbb{N}$ に対して $a_i=1$ であるときは $(-1)^k$ を対応させます。
すなわち、この場合は $\mu(n)=(-1)^k$ と定めます。

それ以外の場合は $0$ を対応させます。

要するに、 $n\in\mathbb{N}$ に対して

$n=1$ ならば $\mu(n)=1$
$n$ が相異なる $k$ 個の素数の積で表せるならば $\mu(n)=(-1)^k$
$n$ が平方数を因数に持つならば $\mu(n)=0$

ということです。
これをまとめて書けば

メビウス関数

関数

$\mu\mu:\mathbb{N}\longrightarrow\left\{ -1,0,1\right\}$ を、

$n\in\mathbb{N}$ に対して

$\mu(n)= \begin{cases} 1&(n=1)\\ (-1)^k&(k=p_1p_2\cdots p_k)\\ 0&({\rm otherwise}) \end{cases}$ で定める。ただし、

$p_1<p_2<\cdots<p_k$ は素数とする。この関数

$\mu$ をメビウス関数(M

$\ddot{{\rm o}}$ bius関数)という。

です。

オイラーの $\varphi$ 関数とメビウス関数の関係

では、本題その1です。

主張の明示 (再掲)とその証明

定理1.

$\varphi:\mathbb{N}\longrightarrow \mathbb{N}$ をオイラーの

$\varphi$ 関数、

$\mu:\mathbb{N}\longrightarrow \left\{ -1,0,1\right\}$ をメビウス関数とする。このとき、

$\varphi(n)=\sum_{d\mid n}\mu\left(\frac{n}{d} \right)d=\sum_{d\mid n}\mu(d)\frac{n}{d}$ である。

定理1.の証明

まず、オイラーの $\varphi$ 関数は乗法的関数(以下参照)です。

乗法的関数、完全乗法的関数

関数

$f$ が正の整数全体の集合上で定められた関数であるとする。

乗法的関数

$f(1)=1$

$m,n\in\mathbb{N}$

$\gcd(m,n)=1$

$f(nm)=f(n)f(m)$

$f$

乗法的関数

完全乗法的関数

$f$

$m,n\in\mathbb{N}$

$f(nm)=f(n)f(m)$

$f$

完全乗法的関数

実際、次が成り立つからです。

定理2.(オイラーの $\varphi$ 関数の乗法性)

$\varphi:\mathbb{N}\longrightarrow\mathbb{N}$ をオイラーの

$\varphi$ 関数とする。

$a,b\in\mathbb{N}$ に対して

$\gcd(a,b)=1\ \Longrightarrow\ \varphi(ab)=\varphi(a)\cdot\varphi(b)$

定理2.(オイラーの $\varphi$ 関数の乗法性)の証明は【代数学の基礎シリーズ】初等整数論編その17を御覧ください。

定理2.から、オイラーの $\varphi$ 関数は乗法的関数ですので、メビウスの反転公式を使うことができます。

定理3.(メビウスの反転公式)※再掲※

$f(n)$ を乗法的関数(※後述)とする。

$\displaystyle F(n)=\sum_{d\mid n}f(d)$ で定めれば、

$f(n)=\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)$ である。

定理3.(メビウスの反転公式)の証明は【代数学の基礎シリーズ】初等整数論編その20をご覧ください。

すなわち、メビウスの反転公式における $f$ としてオイラーの $\varphi$ 関数 $\varphi$ を取る事ができます。
故に
$\varphi(n)=\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)\tag{1}$
です。
ただし、
$F(n)=\sum_{d\mid n}\varphi(d)\tag{2}$
です。

(2)を(1)に代入することで
$\begin{eqnarray} \varphi(n)&=&\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)\\ &=&\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}\varphi(k)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)\sum_{k\mid d}\varphi(k)\tag{3} \end{eqnarray}$
が成り立ちます。

注目すべきは(3)式の

$\displaystyle\sum_{k\mid \frac{n}{d}}\varphi(k)$
$\displaystyle\sum_{k\mid d}\varphi(k)$

です。

(2.について)

これについては、以下を使えば一瞬です。

定理4.

$\varphi$ をオイラーの

$\varphi$ 関数とする。このとき、

$\sum_{\substack{d\in\mathbb{N}\\d\mid n}}\varphi(d)=n$ である。

定理4.の証明は【代数学の基礎シリーズ】初等整数論編その16を御覧ください。

定理4.から
$\sum_{k\mid d}\varphi(k)=d$
となります。
したがって、
$\varphi(n)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)d$
が成り立ちます。

(1.について)

これについては、2.を $\displaystyle k=\frac{n}{d}$ と変数変換すれば
$\sum_{d\mid n}\mu\left( \frac{n}{d}\right)d=\sum_{k\mid n}\mu(k)\frac{n}{k}$
となるので、 $k$ を新たに $d$ と書き直すことで
$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$
となります。

したがって、証明完了です。

定理1.の証明終わり

オイラーの $\varphi$ 関数の積表示の別証明

本題その2です。

定理2.(※再掲※)

$n\in\mathbb{N}$ を

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\quad$ (

$i=1,2,\cdots,k$ に対して

$p_i\in\mathbb{N}$ は素数、

$a_i\in\mathbb{N}$ )

と素因数分解したとする。このとき、

$\varphi:\mathbb{N}\longrightarrow\mathbb{N}$ をオイラーの

$\varphi$ 関数とするならば

$\varphi(n)=n\left( 1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2} \right)\cdots\left( 1-\frac{1}{p_k}\right)$ である。

以前行った証明(【代数学の基礎シリーズ】初等整数論編その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を御覧ください。

今回証明した定理1.を使えば、定理2.の証明を定理0.を使わないという意味で簡略化できます。

定理2.の別証明

$n\in\mathbb{N}$ を
$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$
と素因数分解したとしましょう。
定理1.から、
$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$
ですので、 $\mu(d)=0$ になる $d\in\mathbb{N}$ を除けば、以下が成り立ちます。
※見た目はイカツイかもしれませんが、 $d$ が素因数のとき、 $d$ が2つの素因数の積のとき、 $d$ が3つの素因数の積のとき $\cdots$ と順々に考えているだけです。

$\begin{eqnarray} \varphi(n)&=&\left(\mu(1)n+\mu(p_1)\frac{n}{p_1}+\cdots+\mu(p_k)\frac{n}{p_k}\right)\\ &&+\left(\mu(p_1p_2)\frac{n}{p_1p_2}+\mu(p_1p_3)\frac{n}{p_1p_3}+\cdots+\frac{n}{p_1p_k}\right.\\ &&+\mu(p_2p_3)\frac{n}{p_2p_3}+\mu(p_2p_4)\frac{n}{p_2p_4}+\cdots+\mu(p_2p_k)\frac{n}{p_2p_k}\\ &&+\left.\cdots\cdots+\mu(p_{k-1}p_k)\frac{n}{p_{k-1}p_k}\right)\\ &&+\left(\mu(p_1p_2p_3)\frac{n}{p_1p_2p_3}+\mu(p_1p_2p_4)\frac{n}{p_1p_2p_4}\right.\\ &&+\cdots+\mu(p_1p_2p_k)\frac{n}{p_1p_2p_k}\\ &&+\mu(p_1p_3p_4)\frac{n}{p_1p_3p_4}+\mu(p_1p_3p_5)\frac{n}{p_1p_3p_5}\\ &&+\left.\cdots+\mu(p_{k-2}p_{k-1}p_k)\frac{n}{p_{k-2}p_{k-1}p_k}\right)\\ &&+\cdots\cdots\\ &&\cdots+\mu(p_1p_2\cdots p_k)\frac{n}{p_1p_2\cdots p_k}\\ &=&\left(n-\frac{n}{p_1}-\frac{n}{p_2}-\cdots-\frac{n}{p_k}\right)\\ &&+\left(\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+\cdots+\frac{n}{p_1p_k}\right.\\ &&+\frac{n}{p_2p_3}+\frac{n}{p_2p_4}+\cdots+\frac{n}{p_2p_k}\\ &&+\left.\cdots\cdots+\frac{n}{p_{k-1}p_k}\right)\\ &&+\left(-\frac{n}{p_1p_2p_3}-\frac{n}{p_1p_2p_4}-\cdots-\frac{n}{p_1p_2p_k}\right.\\ &&\left.-\frac{n}{p_1p_3p_4}-\frac{n}{p_1p_3p_5}-\cdots\cdots-\frac{n}{p_{k-2}p_{k-1}p_k}\right)\\ &&+\cdots\cdots\\ &&\cdots+(-1)^k\frac{n}{p_1p_2\cdots p_k}\\ \end{eqnarray}$

あとは、これを因数分解するだけです(後で別のやり方も紹介します)。
最後の式に注目すると、まず、 $n$ をくくり出せることが分かります。
$\begin{eqnarray} \varphi(n)&=&n\left\{\left(1-\frac{n}{p_1}-\frac{1}{p_2}-\cdots-\frac{1}{p_k}\right)\right.\\ &&+\left(\frac{1}{p_1p_2}+\frac{1}{p_1p_3}+\cdots+\frac{1}{p_1p_k}\right.\\ &&+\frac{1}{p_2p_3}+\frac{1}{p_2p_4}+\cdots+\frac{1}{p_2p_k}\\ &&+\left.\cdots\cdots+\frac{1}{p_{k-1}p_k}\right)\\ &&+\left(-\frac{1}{p_1p_2p_3}-\frac{1}{p_1p_2p_4}-\cdots-\frac{1}{p_1p_2p_k}\right.\\ &&\left.-\frac{1}{p_1p_3p_4}-\frac{1}{p_1p_3p_5}-\cdots\cdots-\frac{1}{p_{k-2}p_{k-1}p_k}\right)\\ &&+\cdots\cdots\\ &&\left.\cdots+(-1)^k\frac{1}{p_1p_2\cdots p_k}\right\}\tag{4}\\ \end{eqnarray}$

さて、この式に注目すると、 $p_1$ から $p_k$ までの $1\leq i\leq k$ 個の組合せすべてを網羅していることが分かります。
しかも、各項の係数は $(-1)^i$ です。
これに気がつければ
$\varphi(n)=n\left( 1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2} \right)\cdots\left( 1-\frac{1}{p_k}\right)\tag{5}$
と因数分解できることが分かります。

別の考え方として、ある種「逆」の考え方もアリです。
目標としては(4)式を示すことですから、「(5)式を因数分解すると(4)式になるのだろうなあ」という予想の元、(4)式を実際に展開して(5)式と一致することを確かめてもOKです。

以上のことから、定理0.を使わずに(4)式が成り立つことが証明できます。

定理2.の別証明終わり

皆様のコメントをください！

このブログを読んでいただいている方は本質的には「数学に興味がある方」だと思いますが、大学生の方が多いのではないかと思います。
それ以外には、社会人の方も見ていただいているようです。

大学生(または大学院)の方へ
そろそろ前期の折り返し地点ですが、もう新学期、新生活には慣れましたか？
「この科目面白えなあ！」と思う科目を是非コメントで教えてください！
社会人の方へ
筆者も本年度から社会人ですが、6月はボーナスの時期ですね。
何かボーナスで買うものは決まっていますか？
是非コメントで教えてください！

結

今回は、オイラーの $\varphi$ 関数とメビウス関数の関係を、メビウスの反転公式から証明しました。
また、メビウスの反転公式を使えば、オイラーの $\varphi$ 関数の乗法性を使わずとも $\varphi$ 関数の積表示を証明することができることも示しました。

メビウス関数はゼータ関数とも深く関連し、数論の分野においては誠に重要な関数です。

次回はメビウス関数とゼータ関数の関係を証明します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！

コメントをする

Warning: Undefined variable $req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 32

Warning: Undefined variable $commenter in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Trying to access array offset on value of type null in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Undefined variable $aria_req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

本記事の内容

本記事で言いたいこと

オイラーのφ\varphi関数とメビウス関数の軽い復習

オイラーのφ\varphi関数

メビウス関数

オイラーのφ\varphi関数とメビウス関数の関係

主張の明示 (再掲)とその証明

定理1.の証明

定理1.の証明終わり

オイラーのφ\varphi関数の積表示の別証明

定理2.の別証明

定理2.の別証明終わり

皆様のコメントをください！

結

コメントをする

オイラーの $\varphi$ 関数とメビウス関数の軽い復習

オイラーの $\varphi$ 関数

オイラーの $\varphi$ 関数とメビウス関数の関係

オイラーの $\varphi$ 関数の積表示の別証明