読者です 読者をやめる 読者になる 読者になる

tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

オイラー関数についての補足

数学 整数論

一昨日の RSA 暗号の記事で、オイラー関数  \varphi(m) という関数が登場しました。暗号理論に限らず、整数論においてとても大事な関数となっていますので、ちょっと補足したいなと思いました。

特に、関数の引数が「2つの素数の積」となる場合の説明をまったくしていなかったので、それについてまとめたいと思います。


まずは、何はともあれ定義から再掲しましょう。

オイラー関数の定義:
 m より小さい正の整数で  m と互いに素な数の個数を  \varphi(m) と書いて,これをオイラー関数と呼ぶ.


 m に具体的な数字を入れて考えてみましょう。

 m = 10 のとき

この例は、前の記事にも書きましたが、おさらいとしてもう一度書きましょう。

 m より小さい正の整数は次の  9 個です。

 \{1, 2, 3, 4, 5, 6, 7, 8, 9\}

ここで、 10 2\cdot 5 と素因数分解されますから、素因数である  2 5 を約数に持つかどうか考えれば良いですね。

 2 を約数に持つ数は  \{2, 4, 6, 8\} 4 個、一方  5 を約数に持つ数は  \{5\} 1 個だけです。したがって、これらを引いた残りの  4 個が  10 と互いに素な数となります。一応列挙すると、

 \{1, 3, 7, 9\}

結局、 \varphi(m) = 4 ですね。

これを図にするとこんな感じになります。

f:id:tsujimotter:20150120222925p:plain:w320

ちなみに、重要なポイントですが、 2 5 に対して、それぞれの×の位置が重ならないことに注意してください。

 m が素数のとき

 m より小さい数は  \{1, 2, \ldots, m-1\} m-1 個です。

さぁ、ここで問題です。これらの数の中で、素数  m と互いに素な数はどれでしょう?

・・・

もちろん、すべてですね。笑

 m と互いに素、すなわち、 m 1 以外の公約数を持つためには、( m が素数より)  m の倍数にならなければいけませんが、そうなるためには  m より大きくなければいけません。上に挙げた数はすべて  m より小さい数なので、それはありえませんね。したがって、すべて互いに素な数になります。

よって、 \varphi(m) = m-1 となります。

一昨日の記事で述べた通り、 m が素数であるときは、フェルマーの小定理と関連しますから、この結果は非常に重要です。

 m が2つの素数の積で表される数のとき

さて、最後です。 m p, q という2つの素数の積で表される数のときを考えましょう。すなわち、

 m = pq

この状況は、RSA 暗号で重要な役割を果たしましたね。


さて、先ほどと同様に  m より小さい数を考えると、それは

 \{1, 2, \ldots, m-1\}
 m-1 個です。


ここで、 m = pq より、上で挙げた数が素因数  p q を約数に持つかを考えます。 p, q を素因数に持たない数が、私たちが求める  m と互いに素な数です。


イメージしやすいように  p = 3,  q = 5 としたときの例を図にしてみましょう。 m = 3\cdot 5 = 15 です。

f:id:tsujimotter:20150120223032p:plain:w400

 p を素因数に持つ数は  p の倍数です。したがって、 pq より小さい  p の倍数は、

 \{p, 2p, \ldots, (q-1)p\}

となります。これは、全部で  (q - 1) 個です。(図の例では  q-1 = 4 となってたしかに合っていますね。)

一方で、 q を素因数に持つ数は  q の倍数です。したがって、 pq より小さい  q の倍数は、

 \{q, 2q, \ldots, (p-1)q\}

 (p - 1) 個です。(同様に、図の例では  p-1 = 2 となって、ちゃんと合致しています。)


ここでポイントとなるのは、それぞれの約数が重ならない、という点です。もし重なる数が存在するとしたら「  p の倍数,かつ, q の倍数」ということになります。したがって、こういった数は 「 p, q の最小公倍数の倍数」となるはずです。 p, q の最小公倍数は  pq ですが、 m より小さい数のリストにそのような数は存在しません。


したがって、結局  m 以下の数で  m と互いに素になる数の個数は、全体の個数  (m-1) から  (q-1),  (p-1) を引いた数になりますね。よって

 \begin{eqnarray} &&(m-1) - (q-1) - (p-1) \\
&&= pq - p - q + 1\\
&&= (p-1)(q-1) \end{eqnarray}

となります。つまり

 \varphi(m) = (p-1)(q-1)

となって目的の式が得られました。

一応、 p = 3,  q = 5 を入れて確かめてみると、

 \varphi(m) = \varphi(3\cdot 5) = (3-1)(5-1) = 8

となります。図のリストの中から、×がついていない数を並べると、

 \{1, 2, 4, 7, 8, 11, 13, 14\}

 8 個ですから、ちゃんと一致していますね。あーよかった。


めでたし、めでたし。ということで、簡単ですが今日の記事を終わりたいと思います。それでは。

謝辞

 m = pq のときの計算式の導出は、例の「RSA暗号について質問してきた知人」に教えてもらった方法です。オイラー関数の定義について tsujimotter が教えていると、「じゃあ合成数だったらこうなるね」と図を使って説明してくれたのでした。その導出方法があまりに美しかったので、そのインスピレーションをいただいて今回の記事となりました。知人に感謝です。

関連記事

一昨日のRSA 暗号に関する記事です。本記事はこちらの補足として書きました。

RSA 暗号がようやく分かった気がしたのでまとめてみる - tsujimotterのノートブック