tsujimotterのノートブック

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

原始根の数のかぞえかた

数学 整数論

以前、第２回プログラマのための勉強会 というところで「時計の世界の整数論」という発表をしました。

「時計の世界の整数論」は， p が素数のときの \mod p 上での整数論についてまとめたものです。その中で以下の定理がありました。

f:id:tsujimotter:20150723070104p:plain


図は， p = 11 として \mod {11} におけるべき乗をすべて列挙した表ですが， n = 2, 6, 7, 8 において， n^1, \ldots, n^{10} の間に 1, 2, \ldots, 10 のすべての数が巡回されていることが分かります。

このような元 n のことを「原始根」と呼びます。素数 p においては以下の「原始根定理」が成り立つことが知られています。

原始根定理：
p が素数のとき， \mod p においては，少なくとも１つの原始根が存在する．

\mod {11} における原始根は， n = 2, 6, 7, 8 の４つですね。



ところで，上の発表を作っているときは，原始根 n = 2, 6, 7, 8 は，特に法則なくたまたま現れるのだと考えていました。原始根は少なくとも１つはあることが分かるけれど，実際に計算してみないと，その個数も分からないのであると。


私のお気に入りである以下の整数論のブログ記事を読んでいたときに，実は原始根にはパターンがあるのだと気づきました。正確に言うと，この記事にはちゃんと書いてあったのですが私が理解しきれていませんでした。
biteki-math.hatenablog.com


自分の中で改めて考えてみたら，モヤモヤとしていた整数論の知識がスッキリ整理されて感動しましたので，その感動を伝えたいと思ってこの記事を書き始めました。

しばし，お付き合いください。



前提

この記事は，「時計の世界の整数論」の発表内容を前提に書いています。以下のようにスライドと動画がまとめられていますので，まだ見ていない方は（「原始根定理」が登場するまであたりを）ぜひ見てから読んでみてください。


mod p の元を原始根で表す

まず，原始根定理を仮定することからはじめましょう。

\mod p における原始根を r とおくと， \mod p のすべての元のうち， 0 以外のものは以下のように原始根のべき乗で表せることが分かります。

\{r^0, r^1, r^2, \ldots, r^{p-2}\}

ただし，以上はすべて \mod p における同値類を表していて，その数そのものではありません。

ここで， r^{p-1} 以降の数が，上に含まれていないことに注意してください。フェルマーの小定理より，

r^{p-1} \equiv 1 \pmod{p}

が成り立ち，以降は同じ数が繰り返し現れるためです。


少し用語を整理しておきましょう。

n を整数としたとき， \mod n における同値類を剰余類と呼び，その集合を \mathbb{Z}/n\mathbb{Z} と表記します。また \mathbb{Z}/n\mathbb{Z} のうち， n と互いに素である剰余類を既約剰余類といい，その集合を (\mathbb{Z}/n\mathbb{Z})^{\times} と書きます。 p が素数のとき， (\mathbb{Z}/p\mathbb{Z})^{\times} には 0 を除く p より小さいすべての元に対応した剰余類が入ります。

また， (\mathbb{Z}/n\mathbb{Z})^{\times} は乗法について群をなすことが知られています。したがって，これを 既約剰余類群ともいいます。一方， \mathbb{Z}/n\mathbb{Z} は加法について群をなします。このことを加味して，加法群 \mathbb{Z}/n\mathbb{Z} のように呼んだりします。


さて， \mod {p} における原始根 r のべき乗の集合は，既約剰余類群 (\mathbb{Z}/{p}\mathbb{Z})^{\times} を表していることがわかります。

(\mathbb{Z}/{p}\mathbb{Z})^{\times} = \{r^0, r^1, r^2, \ldots, r^{p-2}\}

以上から， (\mathbb{Z}/{p}\mathbb{Z})^{\times} は，原始根 r によって生成される 巡回群 なので，このように書いてもいいでしょう。

(\mathbb{Z}/{p}\mathbb{Z})^{\times} = \langle r \rangle

ほかの原始根

さて，ここで r^1 = r は１つめの原始根だったわけですが，ほかにも原始根が存在してもよいわけですよね。それを確認してみましょう。

たとえば， p = 11 としたとき，

(\mathbb{Z}/{11}\mathbb{Z})^{\times} = \{r^0, r^1, r^2, r^3, r^4, r^5, r^6, r^7, r^8, r^9\}

となりますが，以下のように r^3 を原始根とすることも出来そうです。

(\mathbb{Z}/{11}\mathbb{Z})^{\times} = \{r^0, r^3, (r^3)^2,(r^3)^3, (r^3)^4, (r^3)^5, (r^3)^6, (r^3)^7, (r^3)^8, (r^3)^9\}
=\{r^0, r^3, r^{3\cdot 2}, r^{3\cdot 3}, r^{3\cdot 4}, r^{3\cdot 5}, r^{3\cdot 6}, r^{3\cdot 7}, r^{3\cdot 8}, r^{3\cdot 9} \}
=\{r^0, r^3, r^6, r^9, r^{12}, r^{15}, r^{18}, r^{21}, r^{24}, r^{27} \}

フェルマーの小定理から，べき乗は r^{10} で一周することを考慮すると，

(\mathbb{Z}/{11}\mathbb{Z})^{\times} =\{r^0, r^3, r^6, r^9, r^2, r^5, r^8, r^1, r^{4}, r^{7} \}

と表せて，たしかに指数がすべて巡回していることが確認できました。


同様に，原始根を r^7, r^9 としたときも，以下のように巡回できます。

(\mathbb{Z}/{11}\mathbb{Z})^{\times} =\{r^0, r^7, r^4, r^1, r^8, r^5, r^2, r^9, r^{6}, r^{3} \}

(\mathbb{Z}/{11}\mathbb{Z})^{\times} =\{r^0, r^9, r^8, r^7, r^6, r^5, r^4, r^3, r^2, r^1 \}


結局のところ，指数 k を何度も足し合わせていったときに \mod {10} のすべての数を回るのであれば， r^k が原始根になっていることがわかりますね。この記事では，このように k の定数倍 ak （ただし 0 \leq a < (p-1) ）が \mod{(p-1)} の元をすべて回ることを「完全巡回」と呼ぶことにしましょう。


このように 「 r^k が \mod {11} で原始根であること」は「その指数 k が \mod {10} で完全巡回すること」に対応していることがわかります。

群の同型

もっと一般的なケースについて考えてみましょう。すなわち， (\mathbb{Z}/p\mathbb{Z})^{\times} の元と，それらを原始根のべき乗で表したときの指数との関係を考えます。

まずは， (\mathbb{Z}/p\mathbb{Z})^{\times} の原始根を１つ選んで r とし，これを使った写像 f を考えます。

f: r^k \mapsto k

p = 11 の場合の状況を図に表すとこんな具合です。

f:id:tsujimotter:20160113210617p:plain:w400

この写像は，以下の２つの性質を満たします。

1. 既約剰余類 (\mathbb{Z}/p\mathbb{Z})^{\times} の元 r^k と１つ位数の小さい剰余類 \mathbb{Z}/(p-1)\mathbb{Z} の元 k を一対一対応させる写像になっています。（全単射）

2. さらに，写像 f には x, y \in (\mathbb{Z}/p\mathbb{Z})^{\times} に対して以下の等式を満たします。

f(xy) = f(x) + f(y)

この式は，積を和に変換している等式になっていることに気づくでしょう。 (\mathbb{Z}/p\mathbb{Z})^{\times} は乗法に関して群を成し， \mathbb{Z}/(p-1)\mathbb{Z} は加法に関して群を成しますので，写像 f は群の演算を保存している，とみることもできます。


以上の２点を満たす写像 f を 群同型写像 と言い，群同型写像によって結ばれる２つの群 (\mathbb{Z}/p\mathbb{Z})^{\times}， \mathbb{Z}/(p-1)\mathbb{Z} は 群同型 であると言います。このことは，以下のように簡潔に表現されます。

(\mathbb{Z}/p\mathbb{Z})^{\times} \simeq (\mathbb{Z}/(p-1)\mathbb{Z})


以上により， (\mathbb{Z}/p\mathbb{Z})^{\times}， \mathbb{Z}/(p-1)\mathbb{Z} は同型な群であることがわかったので，今度は \mathbb{Z}/(p-1)\mathbb{Z} について考えていきましょう。

完全巡回の条件

先の議論により，指数 k が \mod (p-1) において完全巡回するときに限り， r^k が \mod p の原始根となるのでした。次は， \mod{(p-1)} において完全巡回する元の条件を考えましょう。

n 時間時計において 0 から始まって数 k を加え続けることを考えてみましょう。みなさん経験則で知っているように思いますが n と k が互いに素であるときに限り，すべての数を通ります。

たとえば p = 11 のとき， p-1 = 10 ですから， 10 と互いに素な数は 1, 3, 7, 9 です。したがって， 10 時間時計においては，次の図のように 1, 3, 7, 9 が完全巡回することになります。

f:id:tsujimotter:20160113193258p:plain:w380


このことは，ユークリッドの互除法によって示せます。

n と k が互いに素であれば，ユークリッドの互除法により， ak + bn = 1 となるような a, b が存在します。したがって \mod n において ak \equiv 1 であるから， ak を最大 n 回加えれば， n 時間時計のすべての数を１度ずつ巡回しますね。逆に， n と k が互いに素でなければ， ak + bn = 1 を満たす a, b は存在しませんから， k をいくら加えても 1 に辿りつくことはありません。


一方で， p-1 と互いに素な剰余類の集合は (\mathbb{Z}/(p-1)\mathbb{Z})^{\times} ですから， k \in (\mathbb{Z}/(p-1)\mathbb{Z})^{\times} のとき k は \mod{(p-1)} を完全巡回する，と言い換えてもいいでしょう。


話を原始根に戻すと，その元 k を指数として r^k を作ると，これが (\mathbb{Z}/p\mathbb{Z})^{\times} の原始根になります。これで，原始根の見つけ方がわかりましたね。

図にするとこんな感じです。

f:id:tsujimotter:20160113163455j:plain:w480

(\mathbb{Z}/(p-1)\mathbb{Z})^{\times} の元の数は \varphi(p-1) ですから，原始根の数が \varphi(p-1) 個であることもわかりました。


これですっきり解決です！

結論

  • p が素数のとき， \mod p においては，少なくとも１つの原始根が存在する。
  • r を \mod p における原始根とし， k \in (\mathbb{Z}/(p-1)\mathbb{Z})^{\times} であるとき， r^k もまた \mod p の原始根である。
  • 原始根の数は， |(\mathbb{Z}/(p-1)\mathbb{Z})^{\times}| = \varphi(p-1) に等しい。

これを使うと，１つの原始根をみつけることで，すべての原始根を列挙することが可能です。


最後に，具体例をいくつか計算して終わりましょう。

p = 11 の場合

原始根の個数は \varphi(p-1) = \varphi(10) = 4 です。
r = 2 とすると， \{r^0, r^1, r^2, \cdots, r^{9}\} = (\mathbb{Z}/p\mathbb{Z})^{\times} より， r = 2 は原始根の１つです。
(\mathbb{Z}/(p-1)\mathbb{Z})^{\times} の元は \{1, 3, 7, 9\} であるから，対応する \{2^1, 2^3, 2^7, 2^9\} が原始根となります。すなわち \mod p で考えると \{2, 8, 7, 6\} の４つが原始根です。

p = 13 の場合

原始根の個数は \varphi(p-1) = \varphi(12) = 4 です。
r = 2 とすると， \{r^0, r^1, r^2, \cdots, r^{11}\} = (\mathbb{Z}/p\mathbb{Z})^{\times} より， r = 2 は原始根の１つです。
(\mathbb{Z}/(p-1)\mathbb{Z})^{\times} の元は \{1, 5, 7, 11\} であるから，対応する \{2^1, 2^5, 2^7, 2^{11}\} が原始根となります。すなわち \mod p で考えると \{2, 6, 11, 7\} の４つが原始根です。

p = 17 の場合

原始根の個数は \varphi(p-1) = \varphi(16) = 8 です。
r = 3 とすると， \{r^0, r^1, r^2, \cdots, r^{15}\} = (\mathbb{Z}/p\mathbb{Z})^{\times} より， r = 3 は原始根の１つです。
（ r = 2 は \mod{17} では，原始根にはなりません。）

(\mathbb{Z}/(p-1)\mathbb{Z})^{\times} の元は \{1, 3, 5, 7, 9, 11, 13, 15\} であるから，対応する \{3^{1}, 3^{3}, 3^{5}, 3^{7}, 3^{9}, 3^{11}, 3^{13}, 3^{15}\} が原始根となります。すなわち \mod p で考えると \{3, 10, 5, 11, 14, 7, 12, 6\} の８つが原始根です。


ぜひみなさんも自分で確かめてみてくださいね。

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

おまけ：原始根を求める Ruby スクリプト

gist.github.com


実行結果：

$ ruby primitive_root.rb 
p = 11
phi(p-1) = 4
r = 2
primetive roots: [2, 6, 7, 8]

p = 13
phi(p-1) = 4
r = 2
primetive roots: [2, 6, 7, 11]

p = 17
phi(p-1) = 8
r = 3
primetive roots: [3, 5, 6, 7, 10, 11, 12, 14]