■循環小数とアルティンの原始根予想(その1)

フェルマーの小定理とは,

  a^p=a  (modp)

  a^p-1=1  (modp)

すなわち,pを素数とするとaをどんな数にとっても余りが1になるというものである.

 aをランダムに選んでいって,それでも余りが1になればpは素数の候補となるし,1以外の余りがひとつでも出ればpは合成数であることになる.

 とくに

  a^p=a  (modp)

  a^p-1=1  (modp)

の後者はz^n=1という円分方程式(円周等分方程式)との関係も取りざたされるところである.

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

そこで,nを奇素数とする,nで割り切れない任意の数aに対し,

  a,a^2,a^3,・・・,a^n-1  (modn)

を作る.このとき,常に

  a^n-1=1  (modn)

が成立するが,aのベキの次数がn−1に到達する以前に,小さな次数kに対して 

  a^k=1  (modn)

が成立することがある.

 逆に,n−1で初めて

  a^n-1=1  (modn)

が起こることもあり,そのような数aを法nに関する原始根とよぶ.すなわち,原始根の周期はn−1といえるのである.どのような奇素数nに対しても法nに関する原始根は存在する(ガウス).

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

 例として,n=19,a=2の場合を調べてみると

  2^1=2,2^2=4,2^3=8,2^4=16,2^5=13,2^6=7,2^7=14,2^8=9,2^9=18,2^10=17,2^11=15,2^12=11,2^13=3,2^14=6,2^15=12,2^16=5,2^17=10,2^18=1

→2は法19に関する原始根である.

 n=19,a=3の場合を調べてみると

  3^1=3,3^2=9,3^3=8,3^4=5,3^5=15,3^6=7,3^7=2,3^8=6,3^9=18,3^10=16,3^11=10,3^12=11,3^13=14,3^14=4,3^15=12,3^16=17,3^17=13,3^18=1

→3は法19に関する原始根である.

 n=19,a=4の場合を調べてみると

  4^1=4,4^2=16,4^3=7,4^4=9,4^5=17,4^6=11,4^7=6,4^8=5,4^9=1

→4は法19に関する原始根ではない.

 n=19,a=5の場合を調べてみると

  5^1=5,5^2=6,5^3=11,5^4=17,5^5=9,5^6=7,5^7=16,5^8=4,5^9=1

→5は法19に関する原始根ではない.

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

 10を原始根とする素数,たとえば,7の場合,n=7,a=10の場合を調べてみると

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

→10は法7に関する原始根である.

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