9 原始根と指数
9.1 原始根
13を法とする剰余系から0を除いた各剰余のべきを縦方向に順次書いてみる．1が出ればそこか らは同じことがくり返される．それは省略している．
剰余a 1 2 3 4 5 6 7 8 9 10 11 12
a2 4 9 3 12 10 10 12 3 9 4 1
a3 8 1 12 8 8 5 5 1 12 5
a4 3 9 1 9 9 1 3 3
a5 6 10 2 11 4 7
a6 12 1 12 12 1 12
a7 11 7 6 2
a8 9 3 3 9
a9 5 5 8 8
a10 10 4 4 10
a11 7 11 2 6
a12 1 1 1 1 1 1 1 1 1 1 1 1
フェルマの定理によればpが素数で,aがpで割り切れないとき，
ap−1≡1 (mod. p)
である．したがって a12 の段に1が並ぶのは当然であるが，2，6，７，11 は12乗してはじめて 1と合同であり，しかも途中の １, a, a2, · · ·, a11が13を法とする既約剰余系の代表の組となっ ている．pが素数の場合，既約でない剰余系は0のみである．そこでaがp−1乗してはじめて1 と合同になるとき，aをpを法としての原始根という．略してpの原始根ともいう．
さて「原始根」という呼び名はすでに第7節「1のn乗根」で出ている．複素数全体の中でn乗 してはじめて1になるものを「1の原始(n乗)根」と呼んだ．今は pを法とする剰余の集合
K={0, 1, 2, · · ·, p−1}
のなかで, p−1乗してはじめて1と合同になるものを考えている．この場合，pを法とする剰余 系の代表として数aがe乗して1と合同になるなら，eはp−1の約数である．はじめて1と合同 になるとき eはaの(pを法とする)指数というのであった．指数がp−1となる場合にそれを原 始根というのである．
ちなみに「群，体」の意味を知っている人のために注意すれば，上の集合K はp個の要素から なる有限集合であるが，立派に和・差・積・商が定まる．いわゆる「体」である．またK から0 を除いた K× は乗法に関してp−1 個の要素からなる「群」である．
次の定理が示すように原始根の順次のべきからから, K× のすべての要素が得られる．つまり, 原始根はこの「群を生成する」要素であるともいえる．
定理 27
素数pを法として原始根が存在する．rをその一つとすれば，
１, r, r2, · · ·, rp−2 は既約剰余系の一組である．
証明 aをpを法とする既約剰余系の一つの代表である数とする．言いかえればa6≡0 ( mod. p) をとる． aの指数をmとする．am≡1 (mod. p)なので
a0= 1, a1, · · ·, am−1 (34) はいずれも
xm≡1 (mod. p) (35)
の解である．これらは互いに同じ剰余系に属さない．なぜなら, 1<=i <=m−1に対して ai≡aj (mod. p) ⇐⇒ ai−j ≡1 (mod. p)
である．定理 24からi−j はmの倍数である．−m+ 2<=i−j <=m−2なのでこれは i=j の ときのみである．定理14から(34)が(35)の解のすべてである．
さてm=p−1ならa自身が原始根である．m < p−1のとき．aをもとにmより大きい指数 の数を構成できることを示す．
pを法とする既約剰余系はp−1 個あるので，この場合(34)のいずれとも異なる剰余系がある．
そのような剰余系に属する数 b をとる．b の指数をn とする．このときnは m の約数でない．
もし約数ならbm≡1 (mod. p)となる．したがってbも合同方程式(35)の解となりb に関する 仮定に反する．そこで
(1) (m, n) = 1のとき． abの指数は mnである．
なぜなら，まず(ab)mn=amnbmn≡1 (mod. p)であるが，逆に(ab)x≡1 (mod. p)と する．このとき
(ab)mx≡bmx≡1 (mod. p)
定理21からmxはnの倍数であるが(m, n) = 1からxが nの倍数である．
同様に x は m の倍数でもあり， 定理 3 からx は m とn の最小公倍数の倍数である．
(m, n) = 1から最小公倍数はmn．ゆえにab の指数はmnである．mn > mよりpを法 としてmより大きい指数の数が構成できた．
(2) (m, n) =d >1のとき．mとnの最小公倍数をlとする．このときl=m0n0, (m0, n0) = 1 でm0はmの約数，n0はnの約数となるものをとる．これはかならずできる．dを互いに 素な積d=d1d2 に分け(一方が1でもよい)
m0=md1
d , n0= nd2
d
とすればよい．このときamm0, bnn0 はそれぞれ指数がm0, n0である．(m0, n0) = 1より amm0, bnn0 の指数はm0n0=l．nはmの約数ではないのでl > m．やはりpを法としてm より大きい指数の数が構成できた．
真に増加する指数の列ができ，しかもp−1を越えないので有限回の操作で必ず指数p−1の数 が構成できる．つまり原始根 rは必ず存在する．すでに見たように(34)は互いに合同でない．し たがって
１, r, r2, · · ·, rp−2
も互いに合同でない．つまりこれらは p−1個の既約剰余系の一組の代表である． ■ 既約剰余系でみれば(k, p−1) = 1であることがrk が原始根であるための必要十分条件である．
したがって原始根はϕ(p−1)個ある．
例 9.1 ϕ(13−1) = 4なので四つある．実際2, 6, 7, 11 練習問題 9.1 (解答35) p= 41法とする原始根を一つ求めよ．