Euler関数が乗法的であることの証明

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

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

$n$ を正の整数とするとき, $n$ を法とする $1$ つの剰余類に属する整数は, すべて $n$ と互いに素であるか, すべてそうでないかのどちらかである. $n$ を法とする剰余類の中で $n$ と互いに素な整数のみを含むものを, $n$ を法とする既約類という. $n$ を法とする既約類は $\varphi(n)$ 個ある. $n$ を法とする完全剰余系をなす $n$ 個の整数の中から既約類を代表する $\varphi(n)$ 個だけをとったものを, $n$ を法とする既約剰余系という.

[定理] Euler 関数は乗法的である. すなわち, 任意の正の整数 $m$, $n$ に対して, $$ \gcd(m, n) = 1 \Longrightarrow \varphi(mn) = \varphi(m)\varphi(n) $$ が成り立つ.

[証明] $A=\{a_{1}$, $a_{2}$, $\ldots$, $a_{s}\}$ ($s=\varphi(m)$) を $m$ を法とする既約剰余系の集合, $B=\{b_{1}$, $b_{2}$, $\ldots$, $b_{t}\}$ ($t=\varphi(m)$) を $n$ を法とする既約剰余系の集合とする. $\gcd(m, n)=1$ を仮定したとき, 直積集合 $A\times B$ と $mn$ を法とする既約剰余系の集合 $C$ との間に $1$ 対 $1$ 対応が存在することを証明すればよい. そうすれば, $$ \varphi(m)\varphi(n) = \lvert A\rvert \lvert B\rvert = \lvert A\times B\rvert = \lvert C\rvert = \varphi(mn) $$ となる.

$\gcd(m, n)=1$ と仮定する. そのとき, 各組 $(a_{i}, b_{j})\in A\times B$ に対して, 連立合同式 $$ x \equiv a_{i}\pmod{m},\quad x \equiv b_{j}\pmod{n} $$ の解 $x\equiv c_{ij}\pmod{mn}$ が一意的に存在する. しかも, $$ \gcd(c_{ij}, m)=\gcd(c_{ij}, n)=1 \Longrightarrow \gcd(c_{ij}, mn) = 1 $$ であるから, $c_{ij}\in C$ となる. これにより, 写像 $$ f: A\times B\longrightarrow C,\quad (a_{i}, b_{j})\longmapsto c_{ij} $$ が定まる.

任意の $c\in C$ に対して, $$ \gcd(c, mn) = 1 \Longrightarrow \gcd(c, m) = \gcd(c, n) = 1 $$ であるから, ある $a\in A$, $b\in B$ が存在して, $$ c \equiv a\pmod{m},\quad c \equiv b\pmod{n}. $$ すなわち, $f(a, b) = c$. よって, $f$ は全射である.

任意の $a$, $a'\in A$, $b$, $b'\in B$ に対して, $c' = f(a, b) = f(a', b')$ とすれば, \begin{alignat*}{4} c' &\equiv a && \pmod{m},&&\quad c' \equiv b &&\pmod{n}, \\ c' &\equiv a' && \pmod{m},&&\quad c' \equiv b' &&\pmod{n} \end{alignat*} であるから, $$ a\equiv a'\pmod{m},\quad b\equiv b'\pmod{n}. $$ $A$, $B$ は既約剰余系の集合だから, $a=a'$ かつ $b=b'$. よって, $f$ は単射である. (証明終)

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

プロフィール

よしいず

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

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

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

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

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

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