■アルティンの定数(その42)

 7を法とする2のベキ乗(n=7,a=2)の場合を調べてみると

  2^1=2,2^2=4,2^3=1,2^4=2,2^5=4,2^6=1

この数列の周期は3で、整数2は7を法として位数3をもっているという。ord7(2)=3

フェルマーの定理より、位数はp-1の約数でなければならない。p=7に対して位数は決して4にはなりえないのである。

===================================

 7を法とする3のベキ乗(n=7,a=3)の場合を調べてみると

  3^1=3,3^2=2,3^3=6,3^4=4,3^5=5,3^6=1

7を法とする3の位数は6である。ord7(3)=6

位数はp-1の約数でなければならないので、これはとりうる最大値である。

それゆえ、3は7を法とする原始根と呼ばれる。

===================================

もう一つの原始根=pを法とするgの逆元を見つけたい。

  g2=g1^φ(p)-1 (mod p)

φ(p)=p-1より、

  g2=g1^p-2 (mod p)

上の例ではg1=3,p=7であるから

3・5=15=1 (mod 7)より、5は逆元であることが確かめられる。

===================================

7を法とする、もう一つの原始根であることを確かめてみよう。

 7を法とする5のベキ乗(n=7,a=5)の場合を調べてみると

  5^1=5,5^2=4,5^3=6,5^4=2,5^5=3,5^6=1

7を法とする5の位数は6である。ord7(5)=6

===================================