スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Euler関数の値の和

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

正の整数 $n$ に対して, $1$ から $n$ までの整数のうち $n$ と互いに素なものの個数を $\varphi(n)$ で表す. こうして定まる関数 $\varphi(n)$ を Euler 関数という.

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

[証明] 正の整数 $n$ に対し, $n$ 以下の正の整数全体からなる集合を $I_{n}$ とおく. さらに, $n$ とその正の約数 $d$ に対して, $$ \Phi(n, d) = \{ x\in I_{n} \mid \gcd(x, n)=d \} $$ とおく. $\lvert\Phi(n, 1)\rvert = \varphi(n)$ であることに注意しておく. 任意の $x\in I_{n}$ に対して $\gcd(x, n)$ は $n$ の約数であるから, $$ I_{n} = \bigcup_{d\mid n}\Phi(n, d)\quad (\mbox{集合の直和}). $$ よって, $$ n = \lvert I_{n}\rvert = \sum_{d\mid n}\lvert \Phi(n, d)\rvert. $$ 一方, $n$ の各々の約数 $d$ に対して, 写像 $$ f: \Phi(n, d)\longrightarrow \Phi\left(\frac{n}{d}, 1\right),\quad x\longmapsto \frac{x}{d} $$ が定まる. 実際, 任意の整数 $x$ に対して, \begin{align*} x\in \Phi(n, d) &\Longrightarrow \mbox{$x\in I_{n}$ かつ $\gcd(x, n)=d$} \\ &\Longrightarrow \mbox{$x/d\in I_{n/d}$ かつ $\gcd(x/d, n/d) = 1$} \\ &\Longrightarrow x/d\in \Phi(n/d, 1). \end{align*} 任意の $x$, $y\in \Phi(n, d)$ に対して, $$ f(x)=f(y) \Longrightarrow \frac{x}{d}=\frac{y}{d} \Longrightarrow x=y $$ であるから, $f$ は単射である. また, 任意の $x'\in \Phi(n/d, 1)$ に対して, \begin{align*} x'\in \Phi(n/d, 1) &\Longrightarrow \mbox{$x'\in I_{n/d}$ かつ $\gcd(x', n/d)=1$} \\ &\Longrightarrow \mbox{$dx'\in I_{n}$ かつ $\gcd(dx', n) = d$} \\ &\Longrightarrow dx'\in \Phi(n, d). \end{align*} これと $f(dx')=x'$ より, $f$ が全射であることもいえる. よって, $f$ は全単射であり, $$ \lvert \Phi(n, d)\rvert = \left\lvert \Phi\left(\frac{n}{d}, 1\right)\right\rvert = \varphi\left(\frac{n}{d}\right). $$ ゆえに, $$ \sum_{d\mid n}\lvert \Phi(n, d)\rvert = \sum_{d\mid n}\varphi\left(\frac{n}{d}\right). $$ さらに, $$ \left\{ \frac{n}{d} \biggm| \mbox{$d$ は $n$ の約数} \right\} = \{ d \mid \mbox{$d$ は $n$ の約数}\} $$ であるから, $$ \sum_{d\mid n}\varphi\left(\frac{n}{d}\right) = \sum_{d\mid n}\varphi(d). $$ したがって, 求める等式が得られる. (証明終)

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。