スポンサーサイト

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

Euler関数の積公式の直接的な証明

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

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

[定理] 任意の正の整数 $n$ に対して, $$ \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right) $$ が成り立つ. ただし, $p$ は $n$ の素因数全体を動く.

[証明] $p_{1}$, $p_{2}$, $\ldots$, $p_{s}$ を $n$ の異なる素因数とする. 示すべき等式の右辺の積を展開すると, \begin{align*} n\prod_{p \mid n}\left(1-\frac{1}{p}\right) &= n\prod_{i=1}^{s}\left(1-\frac{1}{p_{i}}\right) \\ &= n\left( 1 - \sum_{i=1}^{s}\frac{1}{p_{i}} + \sum_{i<j}\frac{1}{p_{i}p_{j}} - \sum_{i<j<k}\frac{1}{p_{i}p_{j}p_{k}} + \cdots \right) \\ &= n - \sum_{i=1}^{s}\frac{n}{p_{i}} + \sum_{i<j}\frac{n}{p_{i}p_{j}} - \sum_{i<j<k}\frac{n}{p_{i}p_{j}p_{k}} + \cdots. \end{align*} 各 $i=1$, $2$, $\ldots$, $s$ に対して, $\displaystyle \frac{n}{p_{i}}$ は $1$ から $n$ までの整数のうち $p_{i}$ で割れるものの個数であるから, \begin{align*} \sum_{i=1}^{s}\frac{n}{p_{i}} &= \sum_{i=1}^{s}\#\{ m \mid \mbox{$1\leq m\leq n$ かつ $m$ は $p_{i}$ で割れる}\} \\ &= \sum_{m=1}^{n}\#\{ i \mid \mbox{$1\leq i\leq s$ かつ $m$ は $p_{i}$ で割れる}\} \\ &= \sum_{m=1}^{n}\sum_{i \atop p_{i}\mid m} 1 . \end{align*} 各 $i$, $j$ ($i<j$) に対して, $\displaystyle \frac{n}{p_{i}p_{j}}$ は $1$ から $n$ までの整数のうち $p_{i}p_{j}$ で割れるものの個数であるから, \begin{align*} \sum_{i<j}\frac{n}{p_{i}p_{j}} &= \sum_{i<j}\#\{ m \mid \mbox{$1\leq m\leq n$ かつ $m$ は $p_{i}p_{j}$ で割れる}\} \\ &= \sum_{m=1}^{n}\#\{ (i, j) \mid \mbox{$1\leq i< j\leq s$ かつ $m$ は $p_{i}p_{j}$ で割れる}\} \\ &= \sum_{m=1}^{n}\sum_{i<j \atop p_{i}p_{j}\mid m}1. \end{align*} 残りの項についても同様である. ゆえに, \begin{align*} & n - \sum_{i}\frac{n}{p_{i}} + \sum_{i<j}\frac{n}{p_{i}p_{j}} - \sum_{i<j<k}\frac{n}{p_{i}p_{j}p_{k}} + \cdots \\ & \quad = \sum_{m=1}^{n} 1 - \sum_{m=1}^{n}\sum_{i \atop p_{i}\mid m} 1 + \sum_{m=1}^{n}\sum_{i<j \atop p_{i}p_{j}\mid m}1 - \sum_{m=1}^{n}\sum_{i<j<k \atop p_{i}p_{j}p_{k}\mid m}1 + \cdots \\ & \quad = \sum_{m=1}^{n}\left( 1 - \sum_{i \atop p_{i}\mid m} 1 + \sum_{i<j \atop p_{i}p_{j}\mid m}1 - \sum_{i<j<k \atop p_{i}p_{j}p_{k}\mid m}1 + \cdots\right). \end{align*} $n$ の素因数 $p_{1}$, $p_{2}$, $\ldots$, $p_{s}$ の中で整数 $m$ を割るものの個数を $l(m)$ で表す. 上式の最後の辺における丸括弧の中は, $l(m)=0$ ならば $1$ に等しい. $l(m)>0$ ならば, 二項定理より, \begin{align*} & 1 - \sum_{i \atop p_{i}\mid m} 1 + \sum_{i<j \atop p_{i}p_{j}\mid m}1 - \sum_{i<j<k \atop p_{i}p_{j}p_{k}\mid m}1 + \cdots \\ & \quad = 1 - \binom{l(m)}{1} + \binom{l(m)}{2} - \binom{l(m)}{3} + \cdots \\ & \quad = (1-1)^{l(m)} = 0. \end{align*} さらに, $l(m)=0$ は $\gcd(m, n)=1$ と同値である. ゆえに, \begin{align*} & \sum_{m=1}^{n}\left( 1 - \sum_{i \atop p_{i}\mid m} 1 + \sum_{i<j \atop p_{i}p_{j}\mid m}1 - \sum_{i<j<k \atop p_{i}p_{j}p_{k}\mid m}1 + \cdots\right) \\ & \quad = \sum_{1\leq m\leq n \atop l(m)=0} 1 = \sum_{1\leq m\leq n \atop \gcd(m, n) = 1} 1 = \varphi(n). \end{align*} したがって, 求める等式が得られる. (証明終)

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

プロフィール

よしいず

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

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

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

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

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

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