Euler関数の乗法性から値の和を計算する

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

[定理] 任意の正の整数 $n$ に対して, $$ \sum_{d\mid n}\varphi(d) = n $$ が成り立つ. ただし, $d$ は $n$ の正の約数全体を動く.

[証明] $n$ の素因数分解を $$ n = \prod_{i=1}^{s}p_{i}^{e_{i}} $$ とすると, $n$ の約数の素因数分解は $$ \prod_{i=1}^{s}p_{i}^{f_{i}},\quad 0\leq f_{i}\leq e_{i} $$ なる形である. これにより, $n$ の正の約数全体と, 素因数の指数の組からなる集合 $$ \{ (f_{1},f_{2},\ldots,f_{s}) \mid 0\leq f_{i}\leq e_{i} \} $$ とが $1$ 対 $1$ に対応する. よって, $$ \sum_{d\mid n}\varphi(d) = \sum_{(f_{1},\ldots,f_{s})}\varphi\left( \prod_{i=1}^{s}p_{i}^{f_{i}} \right). $$ Euler 関数の乗法性より, $$ \sum_{(f_{1},\ldots,f_{s})}\varphi\left( \prod_{i=1}^{s}p_{i}^{f_{i}} \right) = \sum_{(f_{1},\ldots,f_{s})}\prod_{i=1}^{s}\varphi( p_{i}^{f_{i}} ). $$ 右辺を因数分解すると, $$ \sum_{(f_{1},\ldots,f_{s})}\prod_{i=1}^{s}\varphi( p_{i}^{f_{i}} ) = \prod_{i=1}^{s}\sum_{f=0}^{e_{i}}\varphi( p_{i}^{f} ). $$ 各 $i=1$, $2$, $\ldots$, $s$ に対して \begin{align*} \sum_{f=0}^{e_{i}}\varphi( p_{i}^{f} ) &= \varphi(1) + \varphi(p_{i}) + \cdots + \varphi(p_{i}^{e_{i}}) \\ &= 1 + (p_{i} - 1) + \cdots + (p_{i}^{e_{i}} - p_{i}^{e_{i}-1}) \\ &= p_{i}^{e_{i}} \end{align*} であるから, $$ \prod_{i=1}^{s}\sum_{f=1}^{e_{i}}\varphi( p_{i}^{f} ) = \prod_{i=1}^{s}p_{i}^{e_{i}} = n. $$ したがって, 求める等式が得られる. (証明終)

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示