原始根と位数
こんにちは。前回、フェルマーの小定理を取り上げました。
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\)で割ったときの表を再掲します。
mod 11 指数
| 1 2 3 4 5 6 7 8 9 10
---+------------------------------
1 | 1 1 1 1 1 1 1 1 1 1
2 | 2 4 8 5 10 9 7 3 6 1
3 | 3 9 5 4 1 3 9 5 4 1
4 | 4 5 9 3 1 4 5 9 3 1
5 | 5 3 4 9 1 5 3 4 9 1
6 | 6 3 7 9 10 5 8 4 2 1
7 | 7 5 2 3 10 4 6 9 8 1
8 | 8 9 6 4 10 3 2 5 7 1
9 | 9 4 3 5 1 9 4 3 5 1
10 |10 1 10 1 10 1 10 1 10 1
↑底
（底\(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コマンドでインストールする必要があるので、使えない場合は次のコマンドでインストールしてください。
pip install sympyそれでは、原始根を求めたり、原始根であるか調べたり、位数を求めたりするプログラムを載せます。
import sympy
n = 11
# 原始根であるか調べる
for i in range( 1, n ):
if sympy.is_primitive_root( i, n ):
print( '{0}は{1}の原始根です'.format( i, n ) )
else:
print( '{0}は{1}の原始根ではありません'.format( i, n ) )
print()
# 原始根を求める
print( '{0}の原始根は{1}です'.format( n, sympy.primitive_root(n) ) )
print()
# 位数を求める
for i in range( 1, n ):
print( '{0}を法とする{1}の位数は{2}です'.format( n , i , sympy.n_order( i, n )) )
７行目のsympy.is_primitive_root( i, n )は、\(n\)を法とする原始根に\(i\)がなっていればTrue、なっていなければFalseを戻す関数です。
１４行目のsympy.primitive_root(n)は、\(n\)を法とする原始根の１つが戻り値である関数です。
１９行目のsympy.n_order( i, n )は、\(n\)を法とする\(i\)の位数が戻り値である関数です。
実行結果は、次になります。
1は11の原始根ではありません
2は11の原始根です
3は11の原始根ではありません
4は11の原始根ではありません
5は11の原始根ではありません
6は11の原始根です
7は11の原始根です
8は11の原始根です
9は11の原始根ではありません
10は11の原始根ではありません
11の原始根は2です
11を法とする1の位数は1です
11を法とする2の位数は10です
11を法とする3の位数は5です
11を法とする4の位数は5です
11を法とする5の位数は5です
11を法とする6の位数は10です
11を法とする7の位数は10です
11を法とする8の位数は10です
11を法とする9の位数は5です
11を法とする10の位数は2です
Pythonで原始根と位数を扱う（ライブラリ不使用）
ライブラリを使わずに、書いてみました。速度を追求していない素朴なプログラムです。
def is_primitive_root( i, n ):
k = n_order( i, n )
return k == n - 1
def primitive_root( n ):
k = 1
flag = False
while not flag:
l = k
i = 2
while l != 1:
l = (l*k) % n
i += 1
if i == n:
flag = True
else:
k += 1
return k
def n_order( i, n ):
k = 1
l = i
while l != 1:
l = (l*i) % n
k += 1
return k
if __name__ == '__main__':
n = 11
# 原始根であるか調べる
for i in range( 1, n ):
if is_primitive_root( i, n ):
print( '{0}は{1}の原始根です'.format( i, n ) )
else:
print( '{0}は{1}の原始根ではありません'.format( i, n ) )
print()
# 原始根を求める
print( '{0}の原始根は{1}です'.format( n, primitive_root(n) ) )
print()
# 位数を求める
for i in range( 1, n ):
print( '{0}を法とする{1}の位数は{2}です'.format( n , i , n_order( i, n )) )
実行結果は次になります。もちろん結果はライブラリ使用版と同じです。当然ですが、ライブラリ不使用版を実行したもので、ライブラリ使用版の結果はコピペしていません。
1は11の原始根ではありません
2は11の原始根です
3は11の原始根ではありません
4は11の原始根ではありません
5は11の原始根ではありません
6は11の原始根です
7は11の原始根です
8は11の原始根です
9は11の原始根ではありません
10は11の原始根ではありません
11の原始根は2です
11を法とする1の位数は1です
11を法とする2の位数は10です
11を法とする3の位数は5です
11を法とする4の位数は5です
11を法とする5の位数は5です
11を法とする6の位数は10です
11を法とする7の位数は10です
11を法とする8の位数は10です
11を法とする9の位数は5です
11を法とする10の位数は2です
今回はこれでおしまいにします。それではまた。