独学ノート（土筆の子）コミュの13の原始根は2,6,7,11

法p p-1 原始根の数φ(p-1): 原始根
3 2 1: 2
5 4 2: 2 3
7 6 2: 3 5
11 10 4: 2 6 7 8
13 12 4: 2 6 7 11
17 16 8: 3 5 6 7 10 11 12 14
19 18 6: 2 3 10 13 14 15
23 22 10: 5 7 10 11 14 15 17 19 20 21
29 28 12: 2 3 8 10 11 14 15 18 19 21 26 27
31 30 8: 3 11 12 13 17 21 22 24
37 36 12: 2 5 13 15 17 18 19 20 22 24 32 35
41 40 16: 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
43 42 12: 3 5 12 18 19 20 26 28 29 30 33 34
47 46 22: 5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45

pを素数として、法pのもとで(p-1)乗してはじめて1になる数を原始根という。
例えば、法11のもとで2は10乗しないと1にならないので(2^10=1024=11×93+1)2は法11のもとでの原始根。しかし法7のもとでは、2^3=7+1と、2^(7-1)より小さいべき乗で1となってしまうので、2は法7のもとで原始根でない。

法がpのとき原始根は（1,2,...,pのなかに） φ(φ(p)) = φ(p-1) 個存在する。

平方剰余の理論より、「p≡±1 mod 8」⇔「2は法pのもとで平方剰余である」⇒「2は法pのもとで原始根でない」ことがいえる。

整数の剰余環
0 から N−1 までの整数 a, b に対して、以下のようにして加法と乗法を定める。
加法: a ＋ b (mod N)
乗法: a × b (mod N)
mod N は N で割ったあまりを表す。このようにして作った代数系を整数の剰余環と呼び、 Z/NZ と表す。
例として、Z/4Z の加算および乗算の結果の表を示す。
表1: Z/4Z 加算表
　0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

表2: Z/4Z 乗算表
　1 2 3
1 1 2 3
2 2 0 2
3 3 2 1

Z/NZ は環になっている。加法・乗法ともに結合法則が成り立ち、単位元が存在している。加法に関しては、任意の元 a に対して −a ＝ N − a となり、逆元がただ1つ必ず存在する。乗法に関しては、必ずしも逆元を持つとは限ず、零因子は持つ場合もある。
例Z/4Z では、2 が零因子（2×2 (mod 4) ＝ 4 (mod 4) ＝ 0）。

整数の剰余環の逆元
Z/NZ の元 a が逆元を持つための条件を考えるために、以下の定理を見る。

整数係数 a, b, c を持つ不定方程式、
ax ＋ by ＝ c
が整数解を持つための必要十分条件は、 gcd(a, b) ＝ c となることである。（ただし、gcd(a, b) は a, b の最大公約数。）

(a, b がともにある整数 n の倍数のとき、 x, y の値が何であろうと、ax ＋ by の値も必ず n の倍数になる。)

まず、b を N で置き換え、c は1に固定します。
ax ＋ Ny ＝ 1
そして、両辺、N で割ったあまりを取る。

ax ≡ 1 (mod N)
結果的に、 a と N が互いに素（最大公約数が1）のときに限り、不定方程式 ax ≡ 1 (mod N) が解を持つということになります。

この解 x は、Z/NZ における a の乗法に関する逆元になるので、
a は N と互いに素な場合にのみ逆元を持つという結論が得られる。

整数の剰余体
Z/NZ の元は、N と互いに素な場合にのみ乗法に関する逆元を持つ。これは言い換えると、N が素数 p である場合には、 Z/pZ のすべての元が乗法に関する逆元を持つことになる。すなわち、Z/pZ （p は素数）は体をなす。このようにして得られた体を整数の剰余体（residual field）と呼ぶ。

例として、剰余体 Z/3Z、Z/5Z、Z/7Z の乗算結果の表を示す。

表3: Z/3Z 乗算表
　1 2
1 1 2
2 2 1

表4: Z/5Z 乗算表
　 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

表5: Z/7Z 乗算表
　1 2 3 4 5 6
1 1 2 3 4 5 6
2 2 4 6 1 3 5
3 3 6 2 5 1 4
4 4 1 5 2 6 3
5 5 3 1 6 4 2
6 6 5 4 3 2 1

自然数1,2,,,,n のなかにあるnと互いに素な整数xの個数をφ(n)で表す.
例えば， φ(1)=1 x=1
φ(2)=1 x=1,
φ(3)=2 x=1,2
φ(4)=2 x=1,3
φ(5)=4 x=1,2,3,4
φ(6)=2 x=1,5
このφ(n)をオイラーの関数という．これは整数を定義域とする関数である．
pが素数ならば，明らかにφ(p)=p-1である。

Pを素数(150桁位)として、αはPを法とする原始根とする。
α^a ≡ β( mod p )
のαとβがわかっていても、aを求めることは不可能に近い問題の事を離散対数問題と言う。

pが素数のとき，Z/p から0を抜いたものは体にならず，乗法群にしかなりません．記号では(Z/p)x と書き，『Z/p のバチ』と呼んだりする．

a a^9
1から９までの数字を９乗すると、１の桁は必ずその数自身になるそうだ。

1 1
2 512
3 19683
4 262144
5 1953125
6 10077696
7 40353607
8 134217728
9 387420489

１から９の数字を１乗、２乗、、、９乗して１の桁を拾ってみた。

1,2,3,4,5,6,7,8,9乗
1,1,1,1,1,1,1,1,1 (1)
2,4,8,6,2,4,8,6,2 (2,4,8,6)
3,9,7,1,3,9,7,1,3 (3,9,7,1)
4,6,4,6,4,6,4,6,4 (4,6)
5,5,5,5,5,5,5,5,5 (5)
6,6,6,6,6,6,6,6,6 (6)
7,9,3,1,7,9,3,1,7 (7,9,3,1)
8,4,2,6,8,4,2,6,8 (8,4,2,6)
9,1,9,1,9,1,9,1,9 (9,1)

たかだか４つの異なる数字を巡回することが判る。

Mathmaticaで１３の原始根を求めてみた。

Union[Table[PowerMod[i, j, 13], {i, 12}, {j, 13}]]

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
{2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4},
{3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9},
{4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1, 4, 3},
{5, 12, 8, 1, 5, 12, 8, 1, 5, 12, 8, 1, 5, 12},
{6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, 6, 10},
{7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, 7, 10},
{8, 12, 5, 1, 8, 12, 5, 1, 8, 12, 5, 1, 8, 12},
{9, 3, 1, 9, 3, 1, 9, 3, 1, 9, 3, 1, 9, 3},
{10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1, 10, 9},
{11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1, 11, 4},
{12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12, 1}]
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

In[34]:
= Union[{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}]
Union[{2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2}]
Union[{3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3}]
Union[{4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1, 4}]
Union[{5, 12, 8, 1, 5, 12, 8, 1, 5, 12, 8, 1, 5}]
Union[{6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, 6}]
Union[{7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, 7}]
Union[{8, 12, 5, 1, 8, 12, 5, 1, 8, 12, 5, 1, 8}]
Union[{9, 3, 1, 9, 3, 1, 9, 3, 1, 9, 3, 1, 9}]
Union[{10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1, 10}]
Union[{11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1, 11}]
Union[{12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12}]

1= {1}

2= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

3= {1, 3, 9}

4= {1, 3, 4, 9, 10, 12}

5= {1, 5, 8, 12}

6= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

7= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

8= {1, 5, 8, 12}

9= {1, 3, 9}

10= {1, 3, 4, 9, 10, 12}

11= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

12= {1, 12}