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

tsujimotterのノートブック

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

群論におけるフェルマーの小定理

数学 整数論 代数学

ご無沙汰しております。約3ヶ月ぶりの投稿です。

4月より職場がかわったのですが、仕事に慣れるまでに期間がかかってしまい、ブログの更新が滞っておりました。その間も日曜数学は楽しく続けておりましたので、少しずつブログの方でも公開していけたらと思います。


久しぶりの記事のテーマは「フェルマーの小定理」です。フェルマーの小定理と言っても、よく知られるような数論的なものではなく、群論的 なフェルマーの小定理の類似物です。実は、フェルマーの小定理は群論的にも考えることができるんです。しかも、その証明の方法が巧妙で面白い。


今回の記事は、群論をちょっとだけかじったことがある、少し前の私のような人を想定した記事です。知らない人にはちょっと難しいかもしれませんが、雰囲気だけ追ってもらって、数学的な発想の面白さを共感してもらえたら嬉しいです。


なお今回の記事では、テーマがフェルマーの小定理ということもあって、素数が多々登場します。 p という記号はすべて、素数を表すためだけに用いたいと思います。

数論的なフェルマーの小定理

まずは、フェルマーの小定理の基本形から復習しましょう。

(数論的な)フェルマーの小定理
 p を素数としたとき, p と互いに素な整数  a に対して以下がなりたつ.
  a^{p-1} \equiv 1 \pmod{p}

フェルマーの小定理は

 \mod p a をべき乗していくと
 p-1 回で  1 に戻ってくる

ことを主張する定理です。私のブログでも度々登場しています。基本的かつ便利な定理です。
tsujimotter.hatenablog.com


証明はそれほど難しくありませんので、やってみましょう。


まず  \left\{1, \; 2, \; 3, \; \cdots, \; p-1\right\} を、すべて  a 倍した集合を考えます。

 \left\{a, \; 2a, \; 3a, \; \cdots, \; (p-1)a \right\}

これらは \mod p においては元の集合と一致するはずです。なぜなら、もし一致しないのであれば

 ka \equiv k'a \pmod{p}

となるような  k \not\equiv \; k' の組が存在するはずですが、 a \mod{p} における逆元  a^{-1} をかけると

 k \equiv k' \pmod{p}

となってしまい、  k \not\equiv \; k' と矛盾するからです。 \mod{p} において  p と互いに素な  a に逆元が存在することは、以下のように示すことができます。

 a, p を互いに素な整数としたとき,ユークリッドの互除法により,
 ab + kp = 1

を満たすような整数  b, k が存在する. \mod p をとると,

 ab \equiv 1 \pmod{p}

となって, a \mod{p} における逆元  b の存在が示せた.


さて、先の2つの集合が  \mod{p} で一致するということは、それらの元すべてを掛け合わせても合同関係が成り立つということです。よって、以下の合同式が得られます。

 \begin{eqnarray} 1a \cdot 2a \cdot 3a \cdot \;\cdots \; \cdot(p-1)a \; &\equiv& \;  1 \cdot 2\cdot 3 \cdot \;\cdots \; \cdot (p-1)  \pmod{p} \\
 \therefore  \left\{ 1 \cdot 2\cdot 3 \cdot \;\cdots \; \cdot (p-1) \right\} a^{p-1} \; &\equiv&  \; 1 \cdot 2\cdot 3 \cdot \;\cdots \; \cdot (p-1)  \pmod{p} \end{eqnarray}


ここで

  1 \cdot 2\cdot 3 \cdot \;\cdots \; \cdot (p-1)

の逆元を両辺にかけると

  a^{p-1} \; \equiv  \; 1   \pmod{p}

となり、フェルマーの小定理が得られました。


 (\mathbb{Z}/p\mathbb{Z})^{\times} からの見方

次に、このフェルマーの小定理を群論的に捉え直すことを試みましょう。そのための準備として「 \mod{p} で合同な元をあつめた集合」を用意します。

 \overline{a} := \left\{ \; k \; \middle| \; k \equiv a \pmod{p} \; \right\}

このような集合を( p を法とする) a剰余類 といいます。以下では、この剰余類を使った2つの集合を準備します。


1つめは「 p を法とする剰余類すべて」をあつめた集合です。このような集合を  \mathbb{Z}/p\mathbb{Z} と表します(読み方は「ゼットオーバーピーゼット」)。すべての剰余類を集めると言っても、無限集合にはなりません。なぜなら、

 \overline{5} = \overline{5 + p}

のように一致する剰余類同士が「つぶれてしまう」からです。

結局、独立な剰余類は  \overline{0}, \; \overline{1}, \; \cdots, \; \overline{p-1} p 個で

 \mathbb{Z}/p\mathbb{Z} = \{ \overline{0}, \; \overline{1}, \; \overline{2}, \; \cdots, \; \overline{p-1} \}

となります。


2つめに用意するのは「 \mathbb{Z}/p\mathbb{Z} のうち、 p と互いに素な剰余類のみ」をあつめた集合です。これを  (\mathbb{Z}/p\mathbb{Z})^{\times} と表記することにします(読み方は「ゼットオーバーピーゼットバツ」*1)。右肩の  \times は「積の記号」だと思ってください。

実際そのような剰余類は、  \mathbb{Z}/p\mathbb{Z} においては「 \overline{0} 以外のすべての剰余類」です。したがって

 (\mathbb{Z}/p\mathbb{Z})^{\times} = \{ \overline{1},\; \overline{2},\; \cdots,\; \overline{p-1} \}

となります。


剰余類はそれぞれ集合ですが、これらの間にも、通常の数のような「和」と「積」を考えることができます。例を挙げると

 \begin{eqnarray} \overline{3} + \overline{5} &=& \overline{8} \\ 
  \overline{3} \cdot \overline{5} &=& \overline{15} \end{eqnarray}

のような感じです。


このように演算を定義すると、 (\mathbb{Z}/p\mathbb{Z})^{\times} が「積」に対して群をなすことがわかります*2

ちなみに  \mathbb{Z}/p\mathbb{Z} は「加法」に対して群をなし、  (\mathbb{Z}/p\mathbb{Z})^{\times} は「乗法」に対して群をなします。前者は「加法群」といって、後者は「乗法群」と呼んだりするそうです。 乗法だから、掛け算の記号である  \times がついていたんですね。


さて、このような準備をしておくと、フェルマーの小定理は次のように言い換えることができます。

フェルマーの小定理の言い換え
 p を素数としたとき, g \in (\mathbb{Z}/p\mathbb{Z})^{\times} に対して以下が成り立つ.
  g^{\#(\mathbb{Z}/p\mathbb{Z})^{\times}} = \overline{1}


「なぜわざわざ、このようなまどろっこしい言い換えをするのか?」と思ったかもしれません。この言い換えは、これから述べる一般化のための布石です。


よーく観察すると、一般の群に対しても似たような命題を考えることができそうです。

  •  (\mathbb{Z}/p\mathbb{Z})^\times は群をなす ( (\mathbb{Z}/p\mathbb{Z})^\times を一般の群  G に置き換えれそう)
  •  g は 群  (\mathbb{Z}/p\mathbb{Z})^\times の任意の元 ( g \in G に置き換えれそう)
  • 指数の肩の  \# (\mathbb{Z}/p\mathbb{Z})^\times は 群  (\mathbb{Z}/p\mathbb{Z})^\times の要素数 ( \# G に置き換えれそう)
  • 右辺の  \overline{1} は 群  \# (\mathbb{Z}/p\mathbb{Z})^\times の単位元 ( \overline{1} を単位元  e\in G に置き換えれそう)


これらの考察に基づいて以下が予想されます。実際、この予想は真であり、これこそが今回のテーマである「群論的なフェルマーの小定理」です。

(群論的な)フェルマーの小定理
 G を(有限の要素をもつ)群としたとき, g\in G に対して,以下が成り立つ.
 g^{\#G} = e

ただし, e G の単位元.

 G を有限の要素を持つ群(有限群)に限定していますが、それは無限の群を考えてしまうと  \# G が整数とならないためです。以下、この記事では群は有限群のみを扱うことにします。


それでは「群論的なフェルマーの小定理」の証明にチャレンジしたいと思います。ただし、冒頭で述べたような数論的な証明は、そのままでは使えないことに注意してください。

「数論的なフェルマーの小定理」の証明で用いた手順を踏襲すると

  g_1 a \cdot g_2 a \cdot g_3 a \cdot \;\cdots \; \cdot g_{\# G} a
 \; = \;  \left\{ g_1 \cdot g_2\cdot g_3 \cdot \;\cdots \; \cdot g_{\# G} \right\} a^{\# G}

のような変形をしたくなります。しかしながら、一般の群は可換ではないので こんなことはできません*3。もう少し異なるアプローチが必要です。


一般の群を考える際は 「群の公理」 に立ち戻る必要があります。すなわち、証明に使える道具は、以下に挙げる「4つの公理」だけです。

群の定義
空集合ではない集合  G に演算  \cdot が定義でき,以下の  (1) から  (4) が成り立つとき, Gという.

 \;\;(1)\;\;\;\; すべての  g, h\in G に対して,次式が成り立つ (演算が閉じている)

 g\cdot h \in G

 \;\;(2)\;\;\;\;すべての  g, h, k\in G に対して,次式が成り立つ(結合則)

 (g \cdot h)\cdot k = g \cdot (h\cdot k) = g \cdot h\cdot k

 \;\;(3)\;\;\;\;単位元と呼ばれる元  e\in G が存在し,すべての元  g\in G に対して次式が成り立つ(単位元の存在)

 g\cdot e = e\cdot g = g

 \;\;(4)\;\;\;\;すべての  g\in G に対して,次式を満たす逆元  g^{-1} が存在する (逆元の存在)

 g\cdot g^{-1} = g^{-1}\cdot g = e

さて、使える武器はこれだけです。一体どうやって証明していくのでしょう。


以下で紹介する方法は、群の公理に基づく抽象的な証明です。でも、だからこそ面白い。この感覚をぜひ味わっていただきたいです。

証明の概略

それでは群の公理を使って、群論的なフェルマーの小定理を示していきましょう。証明までは全部で 4ステップ です。

このあとの説明では  g のべき乗が頻繁に登場します。 0 以上の整数  n に対して  g^n を以下で定義します。

 g^n := \begin{cases} e &  (n = 0)\\
\underbrace{g\cdot g\cdot g \cdot \; \cdots \; \cdot g}_{n\; \text{times}} & (n > 0) \end{cases}


以上の表記ができるのは、結合則のおかげ ということに注意してください。

結合則が成り立たない場合は、積の結合順序によって演算の結果が変わってしまい、べき乗が一意に定まりません。

STEP1: 位数は有限である

まずは、群  G の任意の元  g に対してべき乗を考えます。実は  g をべき乗していくと、いつかは必ず単位元  e に一致するのです。

すなわち

 g^k = e

を満たす正整数  k が存在します。このような最小の  k g位数と呼ぶことにしましょう。


 g をべき乗が有限回で  e に戻ることは、次のように示すことができます。

まず、任意の  g\in G に対して、
 g^a = g^b

を満たすような正整数  a > b が存在します。というのも、群  G の要素の数は有限なので、 g のべき乗を  G の要素数より多くもってくれば、鳩ノ巣原理より、少なくとも1組は値が等しい組み合わせが存在するからです。

ここで、 g の逆元  g^{-1} を両辺に  b 回掛けると、

 g^a(g^{-1})^b = e
 \therefore g^{a-b} = e

 (a-b) >0 より  a-b = k とおけば、 g^k = e となる正整数  k の存在が示せた。

証明に「鳩ノ巣原理」を使うのが面白いですね!それでは次に進みましょう。

STEP2:  g が生成する巡回群は  G の部分群である

 g^k が単位元に戻るということは、 g をべき乗していくと「同じ並びが繰り返される」ことになります。この繰り返し単位1つ分をまとめて、次のような  G の部分集合  H をつくりましょう。

 H := \left\{  g^1, \; g^2, \; g^3, \; \cdots , g^k (= e) \right\}


この集合  H G の部分群であることは明らかです。なぜだかわかるでしょうか。

まず, H は積に対して閉じている. g のべき乗同士をいくら掛け合わせても  H の外へは飛び出さないし,ましてや  G を飛び越えることもない.結合則は当然満たす.また,単位元  g^k (= e) が存在する。任意の  g^i に対して, g^{k-i} という逆元が存在する.


また、定義より H の要素数  \# H は、  g の位数  k に一致することに注意してください。

  \# H = k

なお、この  H のように、たった1つの元  g のべき乗によってのみ生成される群のことを巡回群といいます。重要な群なので覚えておくとよいでしょう。

STEP3: ラグランジュの定理

次に、STEP2 で作った部分群  H を使って、群  G を分割することを考えます。

 G を群とし  H をその部分群とする.このとき,以下が成り立つような  m 個の  G の部分集合の組み, H, \; g_2 H, \; g_3 H, \; \cdots , \; g_{m} H が存在する.


 G = H \; \cup \; g_2 H \; \cup \; g_3 H  \; \cup \; \cdots \; \cup \; g_{m} H
かつ
 g_iH \neq g_jH\;\; \Longrightarrow \;\; g_i H \; \cap \; g_j H = \emptyset


ただし  gH は, H のすべての元に  g をかけてできた集合を表す.

 gH \; :=\; \left\{ \; gh\; \middle| \; h \in H \; \right\}

上記の命題では、すべての  G の元は分割  H, \; g_2 H, \; g_3 H, \; \cdots , \; g_{m} H のいずれかに属しており、かつ、それぞれの分割は(まったく同じものでなければ)共通部分を持たない、ということを主張しています。

このような分割を考えたとき、その分割の最小の個数  m (G\;\colon\; H) と書くことにします。部分群  H による  G の最小の分割数は、分割の方法によらず一意に定まることがわかります。したがって、 (G\;\colon\; H) のような記号で表すことができるのです。


上に述べたことは、図で表現するとわかりやすいかもしれません。

f:id:tsujimotter:20160802022339p:plain:w500

要するに G のちょうどぴったりな分割」 H を用いて得られるということを表しています。

図からわかるように  G という群の元は、縦が  \#H 個、横が  (G\;\colon\; H) 個の「長方形」に並べることができます。この長方形の面積を考えることにより、以下が成り立つことがわかるでしょう。

ラグランジュの定理
 G を群とし  H をその部分群とする.このとき,以下が成り立つ.

 \#G\; =\; \#H\; \cdot \;(G\;\colon\; H)


以上の結果により、 g の位数  k = \#H G の要素数  \# G の約数となることが、ただちにわかります。 面白いですね。

このラグランジュの定理は、もちろん群論によって証明できるのですが、ここに挟むと流れが悪くなるので記事の最後におまけとして載せたいと思います。

STEP4: 解決

仕上げです。これまでの結果を用いて、フェルマーの小定理を示しましょう。

使うのは、

 \#G\; =\; \#H\; \cdot \;(G\;\colon\; H)
 g^{\#H}\; = \;e
の2つです。


一気に式変形していきましょう。

 \begin{eqnarray} g^{\#G} &=& g^{\#H\; \cdot \;(G\;\colon\; H)} \\
 &=& \left(g^{\#H}\right)^{(G\;\colon\; H)}  \\
 &=& e^{(G\;\colon\; H)} \\
 &=& e \end{eqnarray}


やりましたね!これにて目的の

 g^{\# G} = e

が証明できました!

まとめ

いかがだったでしょうか。今回は群論の道具を用いて、フェルマーの小定理を一般化した定理を証明しました。

証明の手順を簡単にまとめると

  1.  g の位数の存在を保証する
  2.  g の生成する巡回群が, G の部分群  H であることを示す
  3.  G H で割った集合の大きさから  G H の間の要素数の関係を導く(ラグランジュの定理)

というものでした。なかなかトリッキーで面白いですよね!


群論の面白さの1つに、具体的な群を考えることなく4つの公理のみで議論を進められることがあると思います。慣れてくると、抽象的で何の縛りもないようにみえた4つの公理が、思いのほか「きつい条件」であったことに気づきます。このきつい条件によって、「ラグランジュの定理」や「フェルマーの小定理」のような、まったく自明でない事実が一般的に証明できてしまうわけです。すごい!


それでは、今日はこの辺で。
長々と読んでくださってありがとうございました!

おまけ:ラグランジュの定理の証明

ラグランジュの定理において証明すべきことは、以下の2つです。

まず示したいのは

 \#H = \#(gH)

です。 これは簡単です。

 H の元に  g をかけたものが  gH なので, \#H \geq \#(gH) であることは明らかです.

もし  \#H > \#(gH) であるなら,相異なる  h_1, h_2 \in H gh_1 = gh_2 となる組が存在するはずです.一方で,両辺に  g^{-1} をかけると, h_1 = h_2 となってしまい,これは矛盾します.

よって, \#H = \#(gH) となるほかありません.

これによって  G を分割していた

 H, \; g_2 H, \; g_3 H, \; \cdots, \; g_{(G\;\colon\; H)} H

のすべてが、同じ要素数を持つ  G の部分集合であることがわかりました。上の図でいうと「縦の長さが揃うこと」が示せたことになります。


2つめに示すのは

 g_iH \neq g_jH\;\; \Longrightarrow \;\; g_i H \; \cap \; g_j H = \emptyset

です。これは対偶をとって考えましょう。

 g_i H \; \cap \; g_j H \neq \emptyset \;\; \Longrightarrow \;\; g_iH = g_jH

条件より, g_i H g_j H の共通部分に  g_i h_1 = g_j h_2 となる元が存在する.ただし, h_1, h_2 \in H


ここで,両辺に  h_1 の逆元  h_1^{-1} を右からかける.

 g_i = g_j (h_2 h_1^{-1})

上式は, g_i g_j H の元であることを意味している. g_i h \in H をかけると,

 g_i h = g_j (h_2 h_1^{-1}h)

となるが,これは  g_i H の任意の元が  g_j H の元となったことを意味している.したがって,

 g_i H \subset g_j H


一方で,元の式の両辺に  h_2 の逆元  h_2^{-1} を右からかける.

 g_i(h_1 h_2^{-1}) = g_j

こちらは, g_j g_i H の元であることを意味している. g_j h \in H をかけると,

 g_j h = g_i (h_1 h_2^{-1}h)

となるが,これは  g_j H の任意の元が  g_i H の元となったことを意味している.したがって,

 g_i H \supset g_j H


以上より, g_i H = g_j H であることがわかった.

これにより、すべての分割  g_i H は、他の分割  g_j H と一致しない限り共通部分をもたない、ということがわかりました。

参考文献

こちらを参考にしました。

整数論1: 初等整数論からp進数へ

整数論1: 初等整数論からp進数へ

関連記事

フェルマーの最終定理のクンマーによる解法を紹介した記事ですが,肝心なところで今回証明したフェルマーの小定理を用います( G = \mathscr{C}_K とする)。イデアル類群の位数(類数という)が重要になるのは、この定理のおかげですね。
tsujimotter.hatenablog.com


RSA暗号の記事です。キーポイントで「オイラーの定理(今回の定理の系で  G = (\mathbb{Z}/m\mathbb{Z})^\times としたもの)」が出てきます。
tsujimotter.hatenablog.com



*1:と私は読んでいます

*2:本記事には関係ありませんが、   (\mathbb{Z}/p\mathbb{Z})^{\times} が群であるのは、 p が素数でないときも一般に成り立つ事実です。参考までに。

*3:もちろん、アーベル群(交換則が成り立つ群、すなわち可換群)に限定すれば、この方法で問題ありません。