原始根の数のかぞえかた

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

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

図は， として におけるべき乗をすべて列挙した表ですが， において， の間に のすべての数が巡回されていることが分かります。

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

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

における原始根は， の４つですね。

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

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

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

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