【１】原始根

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

　　ａ^p＝ａ　　（ｍｏｄｐ）

　　ａ^p-1＝１　　（ｍｏｄｐ）

すなわち，ｐを素数とするとａをどんな数にとっても余りが１になるというものである．

　ａをランダムに選んでいって，それでも余りが１になればｐは素数の候補となるし，１以外の余りがひとつでも出ればｐは合成数であることになる．

　とくに

　　ａ^p＝ａ　　（ｍｏｄｐ）

　　ａ^p-1＝１　　（ｍｏｄｐ）

の後者はｚ^n＝１という円分方程式（円周等分方程式）との関係も取りざたされるところである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

そこで，ｎを奇素数とする，ｎで割り切れない任意の数ａに対し，

　　ａ，ａ^2，ａ^3，・・・，ａ^n-1　　（ｍｏｄｎ）

を作る．このとき，常に

　　ａ^n-1＝１　　（ｍｏｄｎ）

が成立するが，ａのベキの次数がｎ−１に到達する以前に，小さな次数ｋに対して　

　　ａ^k＝１　　（ｍｏｄｎ）

が成立することがある．

　逆に，ｎ−１で初めて

　　ａ^n-1＝１　　（ｍｏｄｎ）

が起こることもあり，そのような数ａを法ｎに関する原始根とよぶ．すなわち，原始根の周期はｎ−１といえるのである．どのような奇素数ｎに対しても法ｎに関する原始根は存在する（ガウス）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　例として，ｎ＝１９，ａ＝２の場合を調べてみると

　　２^1＝２，２^2＝４，２^3＝８，２^4＝１６，２^5＝１３，２^6＝７，２^7＝１４，２^8＝９，２^9＝１８，２^10＝１７，２^11＝１５，２^12＝１１，２^13＝３，２^14＝６，２^15＝１２，２^16＝５，２^17＝１０，２^18＝１

→２は法１９に関する原始根である．ord19(2)=18

　ｎ＝１９，ａ＝３の場合を調べてみると

　　３^1＝３，３^2＝９，３^3＝８，３^4＝５，３^5＝１５，３^6＝７，３^7＝２，３^8＝６，３^9＝１８，３^10＝１６，３^11＝１０，３^12＝１１，３^13＝１４，３^14＝４，３^15＝１２，３^16＝１７，３^17＝１３，３^18＝１

→３は法１９に関する原始根である．ord19(3)=18

　ｎ＝１９，ａ＝４の場合を調べてみると

　　４^1＝４，４^2＝１６，４^3＝７，４^4＝９，４^5＝１７，４^6＝１１，４^7＝６，４^8＝５，４^9＝１

→４は法１９に関する原始根ではない．ord19(4)=9

　ｎ＝１９，ａ＝５の場合を調べてみると

　　５^1＝５，５^2＝６，５^3＝１１，５^4＝１７，５^5＝９，５^6＝７，５^7＝１６，５^8＝４，５^9＝１

→５は法１９に関する原始根ではない．ord19(5)=9

　１０を原始根とする素数，たとえば，７の場合，ｎ＝７，ａ＝１０の場合を調べてみると

１０^1＝３，１０^2＝２，１０^3＝６，１０^4＝４，１０^5＝５，１０^6＝１

→１０は法７に関する原始根である．ord7(10)=6

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝