φ(ab)=φ(a)φ(b)の証明(オイラーのφ関数の乗法性)

本記事の内容
前回の軽い復習
1. オイラー関数とは何か？
2. オイラーの$\varphi$関数の性質
この記事で言いたいこと
オイラーの$\varphi$関数の性質(乗法性)
計算で確かめてみる
皆様のコメントを下さい！
結

本記事の内容

本記事は、オイラーの$\varphi$関数の重要な性質$\varphi(ab)=\varphi(a)\varphi(b)$を証明する記事です。

本記事を読むに当たり、オイラーの$\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}

オイラーの$\varphi$関数の性質

定理1.

$\varphi:\mathbb{N}\longrightarrow\mathbb{N}$をオイラーの$\varphi$関数、$p\in\mathbb{N}$を素数とする。このとき $$ \varphi(p)=p-1 $$ である。すなわち、$p$以下の自然数で、$p$と互いに素な自然数は$p-1$個存在する。

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

定理２.

$\varphi:\mathbb{N}\longrightarrow\mathbb{N}$をオイラーの$\varphi$関数、$p\in\mathbb{N}$を素数、$e\in\mathbb{N}$とする。このとき $$ \varphi(p^e)=p^e-p^{e-1} $$ である。すなわち、$p^e$以下の自然数で、$p^e$と互いに素な自然数は$p^e-p^{e-1}$個存在する。

定理2.の証明は【代数学の基礎シリーズ】初等整数論編その16を参照して下さい。

定理3.

$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) $$ である。

定理3.の証明は【代数学の基礎シリーズ】初等整数論編その16を参照して下さい。

この記事で言いたいこと

一言で述べれば

定理3.の証明で使ったオイラーの$\varphi$関数の乗法性(後述)の証明

です。

オイラーの$\varphi$関数の性質(乗法性)

本記事では2種類の証明を解説します。

と、その前に（既約類と既約の代表の一組）

ここでは、以下の証明で使う言葉を定めます。

$n$を法とするときの数の類の中で$n$と互いに素である数のみを含むものを$n$を法としての既約類と呼ぶことにします。
すると、$n$を法としての既約類の個数が、すなわち$\varphi(n)$なのです。

既約類

$n\in\mathbb{Z}$を法とするときの整数の剰余類の中で、$n$と互いに素である整数のみを含むような剰余類を$n$を法としての既約類と呼ぶ。

さて、$n$を法としての各剰余類を代表する$n$個の整数の一組の中から、既約類を代表する$\varphi(n)$個だけをとって、その$\varphi(n)$個の剰余類を既約代表の一組と呼ぶことにします。

既約の代表の一組

$n$を法としての各剰余類を代表する$n$個の整数のうち、既約類の代表であるような$\varphi(n)$個の整数から成る組を、$n$を法としての既約代表の一組と呼ぶ。

主張の明示

では、主張を明示します。

定理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) $$

今回は、この定理の2種類の証明を解説します。

証明その１（ちょっと難しい）

定理0.の証明(パターン1)

仮定から$a,b\in\mathbb{Z}$は$\gcd(a,b)=1$ですから、任意の$k\in\mathbb{Z}$は
$$
ay+bx=k\quad(x,y\in\mathbb{Z})
$$
という形で書くことができます。

なぜなら、次が成り立っているからです。

定理4.

一次の不定方程式 $$ ax+by+cz=k\quad (a,b,c,k\in\mathbb{Z}) $$ が整数解を持つための必要十分条件は、$k$が$d=\gcd(a,b,c)$で割り切れることである(変数の数は任意)。

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

今、$ab$を法として考えたとき、$x$を$a$の倍数だけ増減したとしても、または$y$を$b$の倍数だけ増減しても、$ay+bx$は$ab$の倍数だけ増減します。
実際、$r,s\in\mathbb{Z}$としたとき、
\begin{eqnarray}
&&ay+bx-\left\{ay+b\left( x+ra\right) \right\}=ay+bx-ay-bx-ab\cdot r=abr\\
&&ay+bx-\left\{a\left( y+sb\right)+bx \right\}=ay+bx-ay-ab\cdot s+bx=abs\\
\end{eqnarray}
となるため、
$$
ay+bx\equiv ay+b\left( x+ra\right)\ ({\rm mod}\ ab),\quad ay+bx\equiv a\left( y+sb\right)+bx\ ({\rm mod}\ ab)
$$
であるからです。

したがって、$ay+bx$なるに置いては、$x$には$a$を法としての各剰余類の代表の一組であるような$a$個の値を与え、また$y$には$b$を法としての代表の一組である$b$個の値を与えるときに、この式$ay+bx$から出てくる$ab$個の値は、$ab$うぃお法としての各類の代表の一組でなければなりません。

このようにして、$ay+bx$から得られる$ab$個の値の中から、法$ab$と互いに素でないものを取り除けば、$ab$を法としての既約代表の一組を得るのです。

ただ、$\gcd(x,a)\neq1$だった場合、$\gcd(x,a)\mid ay+bx$であり、また$\gcd(y,b)\neq1$である場合もどうようですから、$ay+bx$において$x$が$a$と互いに素でないものと$y$が$b$と互いに素でないものは取り除かなければなりません。
故に$\gcd(x,a)=1$、$\gcd(y,b)=1$とすれば、

$\gcd(ay+bx,a)=\gcd(bx,a)=1$かつ$\gcd(ay+bx,b)=1$

であるから、$\gcd(ay+bx,ab)=1$となります。

したがって、$ay+bx$において、$x$には$a$を法としての既約代表の一組の値($\varphi(a)$個)、また$y$には$b$を法としての既約代表としての一組($\varphi(b)$個)を与えるときに、$ay+bx$が取る$\varphi(a)\varphi(b)$個の値は、$ab$を法としての既約代表の一組ということになります。

故に、
$$
\varphi(ab)=\varphi(a)\varphi(b)
$$
です。

定理0.の証明終わり

主観ですが、この証明はちょっと難しい(分からなかったからどうだと言う話ではなくて)と感じました。
ただ、剰余の話を理解する上では良い頭の体操になると思いましたので載せました。

一方で、もっと正直な証明もありますので、それも紹介します。

証明その2（正直）

では、行きましょう。

定理0.の証明(パターン2)

$1,2,\cdots,mn$を$m$で割った余りで$m$個の集合に分ける、ということを考えます。

$mn$以下であり$m$で割った余りが$0\leq r\leq m-1$であるような整数の集合$X_r$は以下のように書けます。
\begin{eqnarray}
X_r&=&\left\{ 0\times m+r,\ 1\times m+r,\ 2\times m+r,\cdots,(n-2)\times m+r,\ (n-1)\times m+r\right\}\\
&=&\left\{ r,\ m+r,\ 2m+r,\cdots,(n-2)m+r,\ (n-1)m+r\right\}
\end{eqnarray}
この$X_r$を用いることで
\begin{eqnarray}
\left\{ 1,2,\cdots,mn\right\}=\coprod_{r=1}^{m-1}X_r
\end{eqnarray}
と書くことができます。
ただし、$\displaystyle\coprod$は共通部分が空集合であるような和集合を表す記号です。

この各$X_r\ (0\leq r\leq m-1)$の中から、$mn$と互いに素であるような整数を数え上げます。
それが$\varphi(m)\varphi(n)$個であれば証明完了です。

まず、$r=0$の場合を考えます。
このとき、
$$
X_0=\left\{ 0,\ m,\ 2m,\cdots,(n-2)m,\ (n-1)m\right\}
$$
です。
すなわち、$X_0$の要素は全て$m$の倍数です。
したがって、$X_0$の要素の中に$mn$と互いに素な自然数は存在しません。

次に、$r\neq0$の場合、すなわち$0<r<m-1$の場合を考えます。

$\gcd(r,m)=d\neq1$である場合(つまり、$r$と$m$が互いに素でない場合)
このとき、$d$は$r$と$m$の最大公約数ですので、
$$
r=k_1d,\quad m=k_2d\quad (k_1,k_2\in\mathbb{N})
$$
と書くことができます。
すると$X_r$は
\begin{eqnarray}
X_r&=&\left\{ k_1d,\ k_2d+k_1d,\ 2k_2d+k_1d,\cdots,(n-2)k_2d+k_1d,\ (n-1)k_2d+k_1d\right\}\\
&=&\left\{ k_1d,\ d(k_2+k_1),\ d(2k_2+k_1),\cdots,d\left[(n-1)k_2+k_1\right]\right\}
\end{eqnarray}
となります。
故に、$X_r$の要素はすべて$d$の倍数です。
一方で、今回の場合は$mn=d\cdot k_2n$ですから、$mn$も$d$の倍数です。
$d\neq1$だったため、$\gcd(r,m)\neq1$のときは、$X_r$の要素に$mn$と互いに素であるような整数は存在しません。
$\gcd(r,m)=1$である場合(つまり、$r$と$m$が互いに素である場合)
$X_r$の要素を再掲すると
$$
X_r=\left\{ r,\ m+r,\ 2m+r,\cdots,(n-2)m+r,\ (n-1)m+r\right\}
$$
でした。
今、$\gcd(r,m)=1$のため、$X_r$のどの要素も$m$で割り切れない為、
$$
(\forall x\in X_r)\quad \gcd(x,m)=1
$$
です。
さらに、$X_r$の要素を$n$で割った余りは全て異なります。
仮に、$X_r$の要素に$n$で割ったときの余りが一致しているペアがあったとします。
それを$s,t\in\mathbb{N}$を用いて$sm+r,\ tm+r$と書きましょう。
ただし、$s>t$とし、$0\leq s,t\leq n-1$に注意です。
するとこれらは$0\leq R\leq n-1$を用いて
$$
sm+r=l_1\cdot n+R,\quad tm+r=l_2\cdot n+R\quad (l_1,l_2\in\mathbb{N})
$$
と書けます。
このとき$sm+r-(tm+r)=(s-t)m$であり
$$
(s-t)m=(l_1-l_2)n
$$
となるため、$(s-t)m$は$n$の倍数です。
今$0\leq s-t\leq n-1$であるので、$s-t$は$n$で割り切れないから$m$が$n$で割り切れることになります。
しかしながらこれは仮定$\gcd(m,n)=1$に矛盾します。
故に、$X_r$の要素を$n$で割った余りは全て異なります。

さて、$X_r$の要素を$n$で割った余りは全て異なることに加え$0$から$n-1$の自然数の全てを網羅するから、$X_r$の要素のうち$\varphi(n)$個が$n$と互いに素ということが分かります。
このような類は$\varphi(m)$個存在するわけですので、結局は$\gcd(m,n)=1$のとき
$$
\varphi(m,n)=\varphi(m)\varphi(n)
$$
です。

定理0.の証明終わり

計算で確かめてみる

では、実際に確かめてみましょう。
前回挙げた例を使います。

$\varphi(100)$を求めてみます。

$100$以下の自然数で、$100$と互いに素な自然数は
\begin{eqnarray}
&&1,\ 3,\ 7,\ 9,\ 11,\ 13,\ 17,\ 19,\ 21,\ 23,\ 27,\ 29,\ 31,\ 33,\ 37,\ 39,\ 41,\ 43,\ 47,\ 49,\\
&&51,\ 53,\ 57,\ 59,\ 61,\ 63,\ 67,\ 69,\ 71,\ 73,\ 77,\ 79,\ 81,\ 83,\ 87,\ 89,\ 91,\ 93,\ 97,\ 99
\end{eqnarray}
ですので、$\varphi(100)=40$です。

$100=4\times25$で$\gcd(4,25)=1$です。
$$
\varphi(4)=2,\quad \varphi(25)=\varphi\left( 5^2\right)=5^2-5^1=20
$$
ですから、たしかに$2\times20=40$で一致していますね。

皆様のコメントを下さい！

この記事が投稿されるのは5月14日の深夜だと思います。
2023年においては「母の日」ですね。

皆さんは母の日に何かプレゼントを贈りましたか？
ぜひ教えて下さい！(実は筆者はどんなプレゼントにしようかと迷っています)

結

今回は、オイラーの$\varphi$関数の性質である乗法性について解説しました。
オイラーの$\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

φ(ab)=φ(a)φ(b)の証明(オイラーのφ関数の乗法性)

本記事の内容

前回の軽い復習

オイラー関数とは何か？

オイラーの\(\varphi\)関数の性質

この記事で言いたいこと

オイラーの\(\varphi\)関数の性質(乗法性)

と、その前に（既約類と既約の代表の一組）

主張の明示

証明その１（ちょっと難しい）

定理0.の証明(パターン1)

定理0.の証明終わり

証明その2（正直）

定理0.の証明(パターン2)

定理0.の証明終わり

計算で確かめてみる

皆様のコメントを下さい！

結

コメントをする