tsujimotter

[latexpage]

オイラーの定理は、法$m$としたときのオイラー関数$\phi (m)$、さらには$m$と互いに素な整数$a$を用いて、次のように表されます。

\begin{eqnarray}

a^{\phi (m)} \equiv 1 \bmod m

\end{eqnarray}

この定理は初等数論における非常に重要な定理として位置づけられています。

 

一見、オイラー関数が入っていていたりして、状況が分かりにくいですが、次の補助定理を認めてしまえば、非常に簡単に理解できるものです。

補助定理:

$\{a_1, a_2, \cdots , a_{\phi (m)}\}$ が $m$ を法とする既約剰余系で ${\gcd(c, m)=1}$ ならば，$\{ca_1, ca_2, \cdots , ca_{\phi (m)}\}$ も $m$ を法とする既約剰余系である．

 

この補助定理は、既約剰余系の要素$a_i$が法$m$と互いに素、すなわち、${\gcd(a_i, m)=1}$であることと、合同式の割り算、つまり、

$ac\equiv bc \bmod m$ ならば，$a \equiv b \bmod m/d$．ここで，$d=\gcd (c, m)$

から、容易に導くことが出来ます。よろしければやってみてください。（文献[1]の定理5.9下に証明が載っています。）

 

さて、ここで法$m$の既約剰余系を${\boldmath A}$とし、${\boldmath A}$の要素数を$|{\boldmath A}|$とすると、

\begin{eqnarray}

{\boldmath A}=\{a_1, a_2, \cdots , a_{|{\boldmath A}|}\}

\end{eqnarray}

また、${\boldmath A}$のすべての要素に対し、${\gcd(c, m)=1}$となる$c$を掛けて、既約剰余系${\boldmath A’}$を作る。

\begin{eqnarray}

{\boldmath A’}=\{ca_1, ca_2, \cdots , ca_{|{\boldmath A}|}\}

\end{eqnarray}

補助定理より、${\boldmath A}={\boldmath A’}$であるから、「${\boldmath A}$のすべての要素の積」と「${\boldmath A’}$のすべての要素の積」は等しい。

したがって、

\begin{eqnarray}

c^{|{\boldmath A}|} a_1a_2\cdots a_{A}\equiv a_1a_2\cdots a_{|{\boldmath A}|} \bmod m

\end{eqnarray}

ここで、既約剰余系の各元$a_i$は定義より法$m$と互いに素であるから、その元の積である$a_1a_2\cdots a_{|{\boldmath A}|}$も$m$と互いに素である。

したがって、両辺から$a_1a_2\cdots a_{|{\boldmath A}|}$を消去できて、

\begin{eqnarray}

c^{|{\boldmath A}|} \equiv 1 \bmod m

\end{eqnarray}

上記で$c$–>$a$と置き換えればオイラーの公式の完成ですね。ここで、法$m$における既約剰余系の要素数$|{\boldmath A}|$が、オイラー関数$\phi (m)$に一致することを思い出してください。

 

疑問：既約剰余系の要素数はオイラー関数？

ここで頭がごっちゃになっている人がいるかもしれませんので、いったん整理しましょう。

 

まず、オイラー関数の定義は、「$m$以下の$m$と互いに素な整数の数」、でした。そして、既約剰余系の定義は、「$m$以下の$m$と互いに素な整数の集合」、でした。よって、「法$m$における既約剰余系の要素数」はオイラー関数$\phi (m)$に等しくなるのは定義から明らかですね。

そして、「既約剰余系の要素は法$m$と互いに素である」、という事実から、補助定理を導き、その補助定理から、オイラーの定理を導きました。

以上が証明の流れです。

 

具体的な例を考えて、オイラーの定理の意味を考えてみましょう。

 

法を9として考えましょう($m=9$ですね)。

さて法9における、剰余類の集合は$\mathbb{Z}/9\mathbb{Z}=\left\{0, 1, 2, 3, 4, 5, 6, 7, 8\right\}$として表せます。

 

ここで法9における、既約剰余系は、9と互いに素な要素を抜き出したものですから、$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}=\left\{1, 2, 4, 5, 7, 8\right\}$となります。

この中から、どれでもいいので1つ要素を取り出して（たとえば2を取り出して）それぞれの要素と積をとってみます。それぞれの要素に2をかけて得られた要素を集めた集合は、既約剰余類$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$に一致します。これが補助定理の意味することでした。

 

図に表すと以下のようになります。

さらに2をかけ続けていき、各要素の値の変化を追いかけると、$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$の場合は、ちょうどすべての要素を巡回するように値がかわっていきます。

そして、$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$の要素の数だけ積をとって巡回すると（$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$の場合は6回）1になって、さらに1回積をとると元の値に戻ってくるのです。これがオイラーの定理の真の意味です。

 

ところで、$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$において、2は$\left(\mathbb{Z}/9\mathbb{Z}\right)^{\times}$の要素数だけかけないと元には戻りませんでした。

この例の2ように、$\left(\mathbb{Z}/m\mathbb{Z}\right)^{\times}$の要素数回だけ積をとって、初めて1になるような数を、「法mにおける原始根」といいます。（原始根が存在しないような法もあります。）

当然、それより前に1になるような数も出てくるわけです。単純に考えると、1は任意の法mにおいて、1回の積で1になりますね。このように、ある整数$a$が法$m$において、1になるために必要な積の回数を、法$m$における$a$の位数と呼びます。

 

実は、原始根や位数に関する一般的なことはあまりわかっていないそうなのです。なかなか奥が深くて面白いですね。

オイラーの定理が使いこなせると、べき乗の合同式の計算がとても速くなりますね。また、RSA暗号のような応用でも重要な要素として登場したりします。

それでは、今日はこの辺で。

 

参考文献：

[1] James J. Tattersall原著、「初等整数論9章 第2版」、森北出版株式会社

[2] ジョセフ・H・シルヴァーマン著、「はじめての数論 原著第3版」、ピアソン・エデュケーション