[b][size=150][b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][br]＜原始根ってなんだっけ？＞[/size][/b][br]７で割った余りで数を同一視する整数の世界、[br]つまり、mod７でのべき乗計算をしてみる。[br][br]aのべき乗を順次計算してみよう。[br]たとえば、[br]a=2 (mod 7)なら, [br]2[sup]1[/sup]≡2 (mod 7), [br]2[sup]2[/sup]≡4 (mod 7), [br]2[sup]3[/sup]≡1 (mod 7), [br]2[sup]4[/sup]≡2 (mod 7), [br]2[sup]5[/sup]≡4 (mod 7), [br]2[sup]6[/sup]≡1 (mod 7)[br]と、[b][color=#0000ff]２，４，１を２回繰り返す[/color][/b]。[br]powermod(2,k,7)のkを動かしても1,2,4しか結果がでない。[br]初めて１と合同になるのは６乗ではなく、3乗だ。だから周期３乗で繰り返す。[br][br]a=3 (mod 7)なら、[br]3[sup]1[/sup]≡3 (mod 7), [br]3[sup]2[/sup]≡2 (mod 7), [br]3[sup]3[/sup]≡6 (mod 7), [br]3[sup]4[/sup]≡4 (mod 7), [br]3[sup]5[/sup]≡5 (mod 7), [br]3[sup]6[/sup]≡１と、[color=#0000ff][b]繰り返すことなく６乗まで粘って１[/b][/color]になる。[br]この最後までねばるヤツが原始根だ。[br]３を使うと、そのべき乗でmod7の0以外の要素7-1=６個が全部出そろう。[br]powermod(3,k,7)のkを1から6までまわすと、1から6の剰余がすべて出そろう。[br]３は[color=#0000ff][b][size=150]すべての元の生成者になれるという意味で生成元、原始根[/size][/b][/color]だ。[br]aが原始根なら、[color=#0000ff][b]p-1乗で初めて[size=150]a[sup]p-1[/sup]≡1(mod p)となる。[br][/size][/b][/color][br][color=#0000ff][b][size=150]順番はともかく、かぶりがない、１対１対応だ。[br]だから、逆算にも役立つ。そういう、ありがたい要素が原始根だ。[br][/size][/b][/color][br][b][size=150]＜原始根はレアなの？＞[/size][/b][br]そんなありがたい原始根だけど、有り、難い、つまりレアな存在というものではない。[br]mod7でみてみよう。[br]1[sup]1[/sup]≡1 (mod 7), [br]2[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]3[sup]6[/sup]≡1 (mod 7), [br][/color][/b]4[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]5[sup]6[/sup]≡1 (mod 7), [br][/color][/b]6[sup]2[/sup]≡1 (mod 7)[br]原始根は3だけではない、５もそうだ。[br]原始根を3,5をｒとすると、[br]L=[1,2,3,4,5,6]の要素ｘを順にpowermod(r,x,7)=Lになる。[br]mod 7の原始根は３と５の2個があることがわかった。[br][br][b][size=150]＜指数の約数＞[/size][/b][br]こんどは原始根以外にスポットライトをあてよう。[br]たとえば、２は３乗で１になり、振り出しに戻る。[br]原始根と同じ６乗で１になる必要があるから、３乗を２回くりかえして６乗になる。[br]たとえば、６は２乗で１になり、振り出しに戻る。[br]原始根と同じ６乗で１になる必要があるから、２乗を３回くりかえした６乗になる。[br]つまり、原始根は最大周期６乗で１になったけど、原始根以外でも６乗すれば必ず１になる。[br]これはオイラーの小定理からそうなる。[br]だから、その手前の周期のｘ乗で１になるとしたら、ｘ乗をｙ回くりかえして６乗になる。[br][br]つまり、[b]ｘは６の約数になる[/b]ということだ。[br]aが原始根でないときは、[color=#0000ff][b][size=150]a[sup]m[/sup]≡1(mod p)[/size][/b][/color]なら、[color=#0000ff][b][size=150]mはp-1のp-1より小さい約数だ。[/size][/b][/color]

原始根だけ特別扱いしないで、平等に調べて全体をみよう。[br]1[sup]1[/sup]≡1 (mod 7), [br]2[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]3[sup]6[/sup]≡1 (mod 7), [br][/color][/b]4[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]5[sup]6[/sup]≡1 (mod 7), [br][/color][/b]6[sup]2[/sup]≡1 (mod 7)[br]周期が６の要素は3,6の２個。[br]周期が３の要素は2,4の２個。[br]周期が２の要素は6の1個。[br]周期が1の要素は1の1個。[br]2+2+1+1=6（個）[br]x=[6,3,2,1]に対してy=[2,2,1,1]となる関数はないかな？[br][br]mod11ならどうだろうか？ [br] 1[sup]1 [/sup]≡1 (mod 11), [br] 2[sup]10[/sup]≡1 (mod 11), [br] 3[sup]5 [/sup]≡1 (mod 11), [br] 4[sup]5 [/sup]≡1 (mod 11), [br] 5[sup]5 [/sup]≡1 (mod 11), [br] 6[sup]10[/sup]≡1 (mod 11)[br] 7[sup]10[/sup]≡1 (mod 11), [br] 8[sup]10[/sup]≡1 (mod 11), [br] 9[sup]5 [/sup]≡1 (mod 11), [br]10[sup]2 [/sup]≡1 (mod 11), [br]周期が10の要素は4個。[br]周期が5 の要素は4個。[br]周期が2 の要素は1個。[br]周期が1 の要素は1個。[br]4+4+1+1=10[br]x=[10,5,2,1]に対してy=[4,4,1,1]となる関数はないかな？[br]この２つの事例から[br][color=#0000ff][b][size=150]x=1ならy=1,[br]素数x=p（2,3,5）ならy=p-1。[br]合成数x=pq(6,10)ならy=(p-1)(q-1)となっている。[br][/size][/b][/color][br]もう見当がつきましたか？[br]これは、[color=#0000ff][b][size=150]オイラー関数φ[/size][/b][/color]そのものだね！[br]要素そのものではなく約数と個数と互いに素に着目することで、全体像が見えてきたね。[br][br]つまり、[br]mod pの剰余x(１からp-1個)に対して、powermod(x,k,p)の値の周期はp-1の約数になる。[br][size=150][b][color=#0000ff][size=150][b][color=#0000ff]周期1は[/color][/b][color=#0000ff][b]1個(ｘ＝１)[/b][/color][/size]。[br]周期n(素数)はn[/color][/b][color=#0000ff][b]-1個[/b][/color][/size]。[br][color=#0000ff][b][size=150]周期d(合成数)になる要素はφ(d)個。[br][/size][/b][/color]1+n-1+....φ(d)=ｐ−１（個）になる。[br]p-1の約数すべてにわたって周期ごとの要素数を合計するとp-1になる。[br]つまり、[br][color=#0000ff][b][size=200]∑φ(d)=p-1[br][/size][/b][/color][br][color=#0000ff][b][size=150]周期が最大のp-1になる要素が原始根だったから、[br][/size]どんな素数ｐでも[br][size=200]原始根はφ(p−1)個あるということだ。[br][/size][/b][/color][color=#0000ff][b][size=200][br][/size][/b][/color]

素数pには原始根が必ずあり、その個数はφ(p-1)だとわかった。[br][br]では、１からp-1のうち、どれが原始根になるのか？[br]それは、p-1個の要素を順にp-1乗まで調べないとみつからないのか？[br][br]たとえば、p=7のとき[br]1[sup]1[/sup]≡1 (mod 7), [br]2[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]3[sup]6[/sup]≡1 (mod 7), [br][/color][/b]4[sup]3[/sup]≡1 (mod 7), [br][b][color=#0000ff]5[sup]6[/sup]≡1 (mod 7), [br][/color][/b]6[sup]2[/sup]≡1 (mod 7)[br]で、3,5が原始根だった。[br][br]3[sup]1[/sup]≡3 (mod 7), [br]3[sup]2[/sup]≡2 (mod 7), [br]3[sup]3[/sup]≡6 (mod 7), [br]3[sup]4[/sup]≡4 (mod 7), [br]3[sup]5[/sup]≡5 (mod 7), [br]3[sup]6[/sup]≡1 (mod 7)[br][br]5[sup]1[/sup]≡5 (mod 7), [br]5[sup]2[/sup]≡4 (mod 7), [br]5[sup]3[/sup]≡6 (mod 7), [br]5[sup]4[/sup]≡2 (mod 7), [br]5[sup]5[/sup]≡3 (mod 7), [br]5[sup]6[/sup]≡1 (mod 7)[br][br]と順に計算すれば、aをp-2回aにかけてそのつど剰余を書き出してみつかった。[br][br][b][size=150]＜p-1の素因数分解＞[/size][/b][br]p-1=6=2・3と素因数分解される。[br]p[sub]1[/sub][sup]e1[/sup]p[sub]2[/sub][sup]e2[/sup]....となったとき、[br]要素aについて、[br][color=#0000ff][b][size=150]どの素数p[sub]i[/sub]についても　a[sup](p-1)/p[/sup][sub]i[/sub]≡1(mod p)でないなら、aは原始根となる。[br]６の周期乗はどれも１(mod p)になるので、一番あやしいのは6の自明でない約数乗、２乗、３乗で１(mod p)になることだ。[/size][/b][/color][color=#0000ff][b][size=150]だから、２乗、３乗だけを調べれば良い。[br][/size][/b][/color]a=1は論外。[br]a=2から６までで、２乗と３乗だけ剰余をしらべよう。φ(6)=(2-1)(3-1)=2個原始根があるはず。[br]2[sup]2[/sup]≡4 、2[sup]3[/sup]≡8≡1 (mod 7)　３乗で１になるから２はアウト。[br][b][color=#0000ff]3[sup]2[/sup]≡9=2 [b][color=#0000ff]3[sup]3[/sup]≡6 [b][color=#0000ff](mod 7) 　２乗も３乗も1にならないからOK。[/color][/b][/color][/b][br][/color][/b]4[sup]2[/sup]≡16=2 , 4[sup]3[/sup]≡8=1(mod 7) ３乗で１になるからアウト。[br][b][color=#0000ff]5[sup]2[/sup]≡25=4 , [b][color=#0000ff]5[sup]3[/sup]≡12=5[b][color=#0000ff](mod 7) [b][color=#0000ff]２乗も３乗も1にならないからOK。[br][/color][/b][/color][/b][/color][/b]２個見つかったから終了。[br][br][/color][/b]面白いのは、p=5やp=17のとき。[br]p-1=4,16のように素因数は2しかない。[br]だから、[br]p=5のときは4/2=2乗が１にならないとすぐ原始根とわかる。[br]p=17のときは16/2=8乗が１にならないとすぐ原始根とわかる。[br][br]（理由）[br]p-1＝p[sub]1[/sub][sup]e1[/sup]p[sub]2[/sub][sup]e2[/sup]...　(素因数分解１）とする。[br]aが原始根でなければ、[br]p-1より小さいp-1の約数ｍでa[sup]m[/sup]≡1(mod p)となる。[br]だから、m=p[sub]1[/sub][sup]f1[/sup]p[sub]2[/sub][sup]f2[/sup]...　　（素因数分解２）とする。[br][br]２つの素因数分解１，２を比較したときに、p-1とｍの大小関係から[br]指数eのリストと指数ｆのリストで必ずｆにeより小さいものがある。[br]それが１番目なら、[color=#0000ff][b](p-1)/p[sub]1[/sub]でもmのｋ倍(kは１以上）になる[/b][/color]。[br]だから、a[sup](p-1)/p[sub]1[/sub][/sup]≡(a[sup]m[/sup])[sup]k[/sup]≡1[sup]k[/sup]≡1(mod p)となる。[br][br]これが１回もおきないなら、m=p-1となり、aが原始根ということになるね。[br][br][color=#0000ff][b][size=150]質問：原始根を求める関数はどうやって作りますか？juliaやpythonで[br][/size][/b][/color][color=#0000ff][b][size=150][br][/size][/b][/color]

（剰余n、原始根の個数、原始根のリスト）を返す、関数primitiveRoot(n)を作ることができる。[br]100以下の素数に対して、原始根のリストを表示してみよう。[br][br][color=#0000ff]#[IN]julia[br]#=====================================================================[br]#素数判定関数[br]function isPrime(n)[br] lim = Int(round(n^0.5))[br] if n<2[br] return false[br] end[br] for num in 2:lim[br] if n % num ==0 [br] return false[br] end [br] end[br] return true[br]end[br]#オイラー関数[br]function eu(n)[br] divs=filter( m -> n % m==0,1:n) #nの約数リスト[br] ps= filter(p -> isPrime(p),divs) #nの素因数リスト[br] zs= [1-1/x for x in ps] #素数の倍数を除く割合リスト[br] return Int(n *prod(zs))[br]end[br]#素数ｎの原始根を求める関数[br]function primitiveRoot(n)[br] q=n-1[br] divs=filter( m -> q % m==0,1:q) #qの約数リスト[br] ps= filter(p -> isPrime(p),divs) #qの素因数リスト[br] ids = [q÷x for x in ps] #テスト用の指数リスト[br] rems = [ x for x in 1:q] #テスト対象の剰余リスト[br] #powermodが1になるものを抜き出すために−１して積が０になると除外する。[br] tested=[prod([powermod(x,id,n)-1 for id in ids]) for x in rems] [br] #非ゼロになるインデックスが原始根となる。[br] return findall(!iszero,tested)[br]end[br][br]P =filter(n->length(filter( m -> n % m==0,1:n))==2, 5:100)　[br]pp=[(x,eu(x),primitiveRoot(x)) for x in P][br][br][/color][color=#0000ff]#=====================================================================[br][OUT][br][/color]23-element Vector{Tuple{Int64, Int64, Vector{Int64}}}:[br] (5, 4, [2, 3])[br] (7, 6, [3, 5])[br] (11, 10, [2, 6, 7, 8])[br] (13, 12, [2, 6, 7, 11])[br] (17, 16, [3, 5, 6, 7, 10, 11, 12, 14])[br] (19, 18, [2, 3, 10, 13, 14, 15])[br] (23, 22, [5, 7, 10, 11, 14, 15, 17, 19, 20, 21])[br] (29, 28, [2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27])[br] (31, 30, [3, 11, 12, 13, 17, 21, 22, 24])[br] (37, 36, [2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35])[br] (41, 40, [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35])[br] (43, 42, [3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34])[br] (47, 46, [5, 10, 11, 13, 15, 19, 20, 22, 23, 26 … 31, 33, 35, 38, 39, 40, 41, 43, 44, 45])[br] (53, 52, [2, 3, 5, 8, 12, 14, 18, 19, 20, 21 … 32, 33, 34, 35, 39, 41, 45, 48, 50, 51])[br] (59, 58, [2, 6, 8, 10, 11, 13, 14, 18, 23, 24 … 40, 42, 43, 44, 47, 50, 52, 54, 55, 56])[br] (61, 60, [2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59])[br] (67, 66, [2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63])[br] (71, 70, [7, 11, 13, 21, 22, 28, 31, 33, 35, 42 … 55, 56, 59, 61, 62, 63, 65, 67, 68, 69])[br] (73, 72, [5, 11, 13, 14, 15, 20, 26, 28, 29, 31 … 42, 44, 45, 47, 53, 58, 59, 60, 62, 68])[br] (79, 78, [3, 6, 7, 28, 29, 30, 34, 35, 37, 39 … 54, 59, 60, 63, 66, 68, 70, 74, 75, 77])[br] (83, 82, [2, 5, 6, 8, 13, 14, 15, 18, 19, 20 … 62, 66, 67, 71, 72, 73, 74, 76, 79, 80])[br] (89, 88, [3, 6, 7, 13, 14, 15, 19, 23, 24, 26 … 63, 65, 66, 70, 74, 75, 76, 82, 83, 86])[br] (97, 96, [5, 7, 10, 13, 14, 15, 17, 21, 23, 26 … 71, 74, 76, 80, 82, 83, 84, 87, 90, 92])[br]