原始根と位数
こんにちは。前回、フェルマーの小定理を取り上げました。
https://joho-ka.mints.ne.jp/fermats-little-theoremこの中で用いた表をもとに今回の原始根と位数について考えていきます。
原始根とは
その中で、a^bを自然数nで割ったときの余りがどのようになっているかを表にするプログラムを作り、nが素数であるときにa^{p-1}をpで割ったときの余りが必ず1になっていることを確かめました。このときに用いた表を見ていると、a^{p-1}をpで割ったときの余りだけが1になっているようなaと、何度も余りが1になるようなaがありました。繰り返しになりますが、前回の表のうち、素数11で割ったときの表を再掲します。
（底aが0の場合と指数bが0の場合は除きました）
ここで、2^b \bmod 11について確かめます。
2^1 \equiv 2 \equiv 2 \bmod 11
2^2 \equiv 4 \equiv 4 \bmod 11
2^3 \equiv 8 \equiv 8 \bmod 11
2^4 \equiv 16 \equiv 5 \bmod 11
2^5 \equiv 32 \equiv 10 \bmod 11
2^6 \equiv 64 \equiv 9 \bmod 11
2^7 \equiv 128 \equiv 7 \bmod 11
2^8 \equiv 256 \equiv 3 \bmod 11
2^9 \equiv 512 \equiv 6 \bmod 11
2^{10} \equiv 1024 \equiv 1 \bmod 11
となり、余りrが1 \leq r \leq 10 = 11-1の範囲の整数をすべて網羅しています。言い換えると、余りは2,4,8,5,10,9,7,3,6,1とすべて網羅しています。このようにすべて網羅するようなaのことを原始根（原始元と載っている場合もある）といいます。
原始根について次の定理があります。
任意の素数pに対して、pを法とする原始根は少なくとも１つ存在する
（a^nをpで割った余りが、1,2,\cdots,p-1をすべて網羅する原始根aは少なくとも１つ存在する）
11を法とする原始元は2の他に、6,7,8も原始根になっています。
位数とは
次に位数についてまとめます。初等整数論において、互いに素であるa,nに対してa^m \equiv 1 \bmod nとなる最小の正の整数mをnを法とするaの位数といいます。先ほどの例では、2^m \equiv 1 \bmod 11となる最小の正の整数は10でした。これを、11を法とする2の位数は10であるといいます。
11を法とする位数を表にまとめてみます。
| 位数（m） | a（a^m \equiv 1 \bmod 11） |
| 1 | a=1 |
| 2 | a=10 |
| 5 | a=3,4,5,9 |
| 10 | a=2,6,7,8 |
Pythonで原始根と位数を扱う（ライブラリ使用）
Pythonでsympyというライブラリを用いると原始根と位数を簡単に求めることができます。pipコマンドでインストールする必要があるので、使えない場合は次のコマンドでインストールしてください。
それでは、原始根を求めたり、原始根であるか調べたり、位数を求めたりするプログラムを載せます。
７行目のsympy.is_primitive_root( i, n )は、nを法とする原始根にiがなっていればTrue、なっていなければFalseを戻す関数です。
１４行目のsympy.primitive_root(n)は、nを法とする原始根の１つが戻り値である関数です。
１９行目のsympy.n_order( i, n )は、nを法とするiの位数が戻り値である関数です。
実行結果は、次になります。
Pythonで原始根と位数を扱う（ライブラリ不使用）
ライブラリを使わずに、書いてみました。速度を追求していない素朴なプログラムです。
実行結果は次になります。もちろん結果はライブラリ使用版と同じです。当然ですが、ライブラリ不使用版を実行したもので、ライブラリ使用版の結果はコピペしていません。
今回はこれでおしまいにします。それではまた。