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

本記事の内容

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

本記事を読むに当たり、オイラーの$\varphi$関数について知っている必要があるため、以下の記事も合わせてご覧ください。

オイラーのφ関数とは？性質は？導入背景は？

...

for-spring.com

2023.05.06

前回の軽い復習

そもそも、オイラーの$\varphi$関数とは何だったか？ということも含め、前回説明したことについて軽く復習します。

オイラー関数とは何か？

$n$以下の自然数に対し、$n$と互いに素な整数の個数を対応させる関数$\varphi:\mathbb{N}\longrightarrow \mathbb{N}$をオイラーの$\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.の証明は【代数学の基礎シリーズ】初等整数論編 その16を御覧ください。

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

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

この記事で言いたいこと

一言で述べれば

です。

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

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

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

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

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

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

主張の明示

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

今回は、この定理の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.の証明は【代数学の基礎シリーズ】初等整数論編 その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,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$関数の性質のうち重要なものを解説します！

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！

初等整数論について、以下の書籍をオススメします！