【１】原始根とフェルマーの定理

　有限体Ｆpの０以外の元をａとします．このとき，ａをｐ回足すとはじめて０になります．素数７を例にとって，Ｆ7でａ＝３を何回もたしてみると

　　３＋３＝６

　　３＋３＋３＝６＋３＝２

　　３＋３＋３＋３＝２＋３＝５

　　３＋３＋３＋３＋３＝５＋３＝１

　　３＋３＋３＋３＋３＋３＝１＋３＝４

　　３＋３＋３＋３＋３＋３＋３＝４＋３＝０

このｐを有限体Ｆpの「標数」といいます．

　また，ａをｐ−１回掛けると１になります．Ｆ7において

　　ａ＼^n　　１　　２　　３　　４　　５　　６

　　　１　　　１　　１　　１　　１　　１　　１

　　　２　　　２　　４　　１　　２　　４　　１

　　　３　　　３　　２　　６　　４　　５　　１

　　　４　　　４　　２　　１　　４　　２　　１

　　　５　　　５　　４　　６　　２　　３　　１

　　　６　　　６　　１　　６　　１　　６　　１

最後の列はすべて１です．

　このように，ｐで割り切れない整数ａに対して，フェルマーの（小）定理

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

が成り立つというわけです．また，このことからａ^(p-2)がａの逆元となることも理解されます．

　　１／ａ＝ａ^(p-2)

Ｆ7では，

　　１／３＝３^5＝５，１／６＝６^5＝６

　この表において，１は１乗してはじめて１になりますが，２は３乗して，３は６乗して，４は３乗して，５は６乗して，６は２乗してはじめて１になります．何乗かして１になるとき，その最小のものを「位数」と呼びます．ｐ＝７のとき，ａ＝１，２，３，４，５，６の位数はそれぞれ１，３，６，３，６，２ですが，ここで位数として現れる数はすべて６＝７−１の約数です．一般にＦpの位数はｐ−１の約数となります．

　また，ｐと互いに素な整数ａがｐ−１乗してはじめて１になるとき，ａを「原始根」といいます．Ｆ7においては３，５が原始根です．

　Ｆ5においては

　　ａ＼^n　　１　　２　　３　　４

　　　１　　　１　　１　　１　　１

　　　２　　　２　　４　　３　　１

　　　３　　　３　　４　　２　　１

　　　４　　　４　　１　　４　　１

より２，３が原始根となります．

　任意の素数について原始根ｒは少なくとも１つ存在します．１つとは限らないため，原始根ｒの選び方は１通りではありませんが，１つ選んで固定します．そしてＦpにおける原始根ｒが与えられたとき，０以外のすべての元は，

　　ａ＝ｒ^i　　　（i=0〜p-2）

の形に表すことができます．ｉを（ｒに関する）「指数」と呼びます．Ｆpの０以外のすべての元はｒを生成元とする位数ｐ−１の巡回群というわけです．

　Ｆ7において，原始根ｒ＝３とすると

　　　ｉ　　：　０，１，２，３，４，５

　　ａ＝ｒ^i：　１，３，２，６，４，５

ですから，６の指数は３，１の指数は０ということになります．また，原始根としてｒ＝５を選ぶと

　　　ｉ　　：　０，１，２，３，４，５

　　ａ＝ｒ^i：　１，５，４，６，２，３

で，同様に６の指数は３，１の指数は０となります．

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

【２】まとめ

　Ｆpにおける原始根ａが与えられたとき，０以外のすべての元は，

　　ａ^i　　　（i=0〜p-2）

の形に表すことができます．

　したがって，ｋをｐ−１で割り切れないものとすると各逆数１／１，１／２^k，・・・，１／（ｐ−１）^k　　（ｍｏｄ　ｐ）は，すべての剰余１，２^k，・・・，（ｐ−１）^k　　（ｍｏｄ　ｐ）をきっかり１回だけ覆うという意味で，再配列によって

　　１＋１／２^k＋１／３^k＋・・・＋１／（ｐ−１）^k

　＝１＋２^k＋３^k＋・・・＋（ｐ−１）^k　　（ｍｏｄ　ｐ）

となります．

　また，　１，２，・・・，ｐ−１は順序を無視すれば，法ｐに関する原始根をｇとすると法ｐに関してｇ，２ｇ，・・・，（ｐ−１）ｇと合同，すなわち，１，２^k，・・・，（ｐ−１）^k　　（ｍｏｄ　ｐ）は，ｇ，（２ｇ）^k，・・・，（（ｐ−１）ｇ）^k　　（ｍｏｄ　ｐ）をきっかり１回だけ覆うという意味で，再配列によって

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k

　＝ｇ^k＋（２ｇ）^k＋（３ｇ）^k＋・・・＋（（ｐ−１）ｇ）^k　　（ｍｏｄ　ｐ）

となるのです．

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