pを素数とする
mod pにおける原始根がすべて現れる式を見つけたので投稿します。有名かもしれないですし、mod pにおける原始根をひとつは知っていないと作れない式なのですが……
nを整数とします。
例をまずあげます。
mod5における原始根は2,3でした。
これらの数は
2^(3^n)(mod 5)
にn=1,n=2を代入すると得られます。
nが奇数のときは3が、nが偶数のときは2が現れます。
2^(3^n)(mod 5)だけではなく3^(3^n)(mod 5)でも同様です。
mod11のときは、
2^(3^n)(mod 11)
のnの値を変えることですべての原始根が得られます。
ざっくり書くと、
mod pの任意の原始根をa、mod(p-1)の任意の原始根をbとするとき、
a^(b^n)(mod p)の形でmod pのすべての原始根を表せるようです。
ただし、mod(p-1)が巡回群でない場合もあり、生成元がふたつ以上必要なときもあります。
そのときは、たとえばc,dのふたつがmod (p-1)において生成元の役割を果たすときを例にすると、
a^(c^j×d^k)(mod p)(j,kは整数)
というように式を変えれば無事すべてのmod pのすべての原始根が現れます。
以上です。少し今までの投稿と違う内容なので、分かりにくいところもあると思います。もしなにかあれば質問ください。
お読みいただきありがとうございました！
