もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君　MENU

(数学)原始根と指数

数学

160825_06

　紹介したい数学記事はまだもう少しあるんですが, そのための前段階として書いておきべきものがあり, これはその一つです.

 

[Contents]
 

 

フェルマーの定理

thetheorier.hatenablog.com

　以前紹介したオイラーの定理, フェルマーの定理は更にこの前段階とも言えます.

　定理だけ改めて書き下しておきましょう.

 

 

[定理：フェルマーの定理]

　素数 { \displaystyle p } と, { \displaystyle p } で割り切れない整数 { \displaystyle a } について,

{ \displaystyle a^{p-1}\equiv 1 \pmod p }

 

 

原始根

　先に原始根, 指数のイメージを言ってしまえば, 原始根は「対数の底」, 指数は「対数」…の合同式版のようなものです.

 

 

準備と補題

　まず素数 { \displaystyle p } と, { \displaystyle p } で割り切れない整数 { \displaystyle a } について

{ \displaystyle a^{p-1}\equiv 1 \pmod p }

が成り立つことは上記フェルマーの定理の通りです.

 

　例えば { \displaystyle 3^{7-1}=3^{6}=729 } は { \displaystyle 729-1=728=7\times 104 } なので { \displaystyle 3^{7-1}\equiv 1\pmod 7 } ですね.

 

　しかし実は, { \displaystyle a } と { \displaystyle p } の組み合わせによっては, { \displaystyle p-1 } よりも小さい正指数で { \displaystyle 1 } と合同になることがあります.

　例えば { \displaystyle a=2 }, { \displaystyle p=7 } の場合を考えてみると, { \displaystyle 2^{7-1}=2^{6}=64 }, { \displaystyle 64-1=63=7\times 9 } なので { \displaystyle 2^{7-1}\equiv 1\pmod 7 } ではありますが, 実は { \displaystyle 2^{3}-1=8-1=7 } なので { \displaystyle 2^{3}\equiv 1\pmod 7 }, つまり { \displaystyle 7-1=6 } よりも小さい正指数 { \displaystyle 3 } で { \displaystyle 1 } と合同になります.

 

　ここで, 正指数 { \displaystyle e } について { \displaystyle a^{e}\equiv 1\pmod p } であって, かつ { \displaystyle e } よりも小さな正指数ではこのようにならない(1と合同にならない)とき, { \displaystyle a } は指数 { \displaystyle e } に対応すると言います.

 

　上の例だと { \displaystyle a=2 } は { \displaystyle p=7 } に対応しません.

　{ \displaystyle a=3, p=7 } については, { \displaystyle 7-1=6 } よりも小さな正指数では1と合同になりませんので, { \displaystyle 3 } は { \displaystyle 7 } に対応すると言えます.

 

　続いて, 定義の前に以下の補題を紹介します.

　ちょっと長文ですが後々のことを考えるとここで触れておきたいので載せておきます.

　面倒と思った方は証明は飛ばしてください.

 

[補題1]

　{ \displaystyle a } が法 { \displaystyle m } に関して指数 { \displaystyle e } に対応するとき, { \displaystyle e } の倍数 { \displaystyle k } に限ってのみ

{ \displaystyle a^{k}\equiv 1\pmod m }

である.

 

[補題1の証明]

　{ \displaystyle \gcd(a, m)=1 } であるとき, 合同方程式 { \displaystyle ax\equiv b\pmod m } の解は法 { \displaystyle m } においてただ一つとなります.

　従ってこのときの解を分数表示して差し支えありません, つまり

{ \displaystyle x\equiv \frac{b}{a}\pmod m }

とできます(この分数表示が, 自然な演算によって環を成すことは省略します).

　故にこれを負の指数で表現することも可能となります, つまり

{ \displaystyle x\equiv a^{-1}b\pmod p }

となります.

　これを利用すると, 例えば { \displaystyle a^{-k} } とは { \displaystyle a^{k}x\equiv 1\pmod m } の解, 或いは { \displaystyle \frac{1}{a^{k}} } を意味します.

　後述のために書きなおすと

{ \displaystyle x\equiv a^{-k}\pmod m \quad\dots (1) }

です.

 

　さてここで, { \displaystyle ne\geq k } となる自然数 { \displaystyle n } を定めます.

　{ \displaystyle a^{e}\equiv 1 \pmod m } より { \displaystyle a^{ne}\equiv 1\pmod m } であることは明らかです(数学的帰納法でも使えば良いでしょう).

　そして { \displaystyle a^{k}x\equiv 1\pmod m } の両辺に { \displaystyle a^{ne-k} } を乗じて整理してみると,

 

{ \displaystyle a^{ne-k+k}x\equiv a^{ne-k}\pmod m }

{ \displaystyle \Leftrightarrow a^{ne}x\equiv a^{ne-k}\pmod m }

{ \displaystyle x\equiv a^{ne-k}\pmod m }　({ \displaystyle a^{ne}\equiv 1\pmod m }　より)

 

　この解は先程の { \displaystyle (1) } と同じ合同方程式によるものです, 従って

 

 { \displaystyle a^{-k}\equiv a^{ne-k}\pmod m }

 

が言えます.

　{ \displaystyle (ne-k)-k=ne } ですから { \displaystyle -k\equiv ne-k\pmod e } です.

　言いかえれば上の事実は整数 { \displaystyle h, k } が正であるか負であるかに関係なく, { \displaystyle h\equiv k\pmod e } が成り立つ場合は

{ \displaystyle a^{h}\equiv a^{k}\pmod m }

であるということです.

 

　つまり { \displaystyle a } が { \displaystyle e } に対応するとき, { \displaystyle a^{k} \equiv 1\pmod m } となるような { \displaystyle k } は, フェルマーの定理より { \displaystyle k=e } は確実に対応しますから, { \displaystyle k\equiv e \equiv 0\pmod e }, つまり { \displaystyle e } の倍数であるものに限られるということになります. { \displaystyle \square }

 

　この補題を言いかえるなら次のようになります.

 

[補題1']

　{ \displaystyle a } が指数 { \displaystyle e } に対応するとき, つまり { \displaystyle a^{e}\equiv 1\pmod m } であり, かつ { \displaystyle e } より小さい正指数ではこのような合同式が成り立たないとき, { \displaystyle e } は { \displaystyle \varphi (m) } の約数である.

　なぜ { \displaystyle \varphi (m) } であるか…と言えば, それはオイラーの定理に由来します.

　従ってフェルマーの立場で言えばこの部分は { \displaystyle p-1 } となります.

 

　先程の { \displaystyle a=2, p=7 } の例では, 指数 { \displaystyle 3 } が対応していました.

　この { \displaystyle 3 } は { \displaystyle \varphi (7)=7-1=6 } の正約数の一つですね.

 

 

原始根の定義

　ではやっと原始根の定義に入ります.

 

[定義：原始根]

　素数 { \displaystyle p } と, { \displaystyle p } で割り切れない整数 { \displaystyle a } について, { \displaystyle a } が指数 { \displaystyle p-1 } に対応するとき, つまり { \displaystyle p-1 } よりも小さな正指数で { \displaystyle a^{e}\equiv 1\pmod p } とならないとき, { \displaystyle a } を { \displaystyle p } の原始根と呼ぶ.

 

　本来であれば原始根が存在することも証明すべきですが, 今回は省略します.

　因みに素数 { \displaystyle p } の原始根は { \displaystyle \varphi (p-1) } 個あることが分かっています(要証明).

 

 

指数

　続いては指数の説明です.

　こちらも前準備から入りたいと思います.

 

[補題2]

　素数 { \displaystyle p } の原始根の一つを { \displaystyle r } とする. このとき

{ \displaystyle 1, r, r^{2},\dots r^{p-2} }

は規約代表の1つとなる.

 

[補題2の証明]

　整数 { \displaystyle a } を素数 { \displaystyle p } で割れない数とし, { \displaystyle a } は指数 { \displaystyle m } に対応する, つまり { \displaystyle a } を整数冪 { \displaystyle m } することではじめて { \displaystyle 1 } と合同になるとします.

　このとき自然数 { \displaystyle k } について

{ \displaystyle (a^{k})^{m}\equiv (a^{m})^{k}\equiv 1\pmod p }

ですから, 以下の { \displaystyle m } 個の数

{ \displaystyle a^{0}(=1), a^{1}, a^{2},\dots a^{m-1} }

は合同方程式

{ \displaystyle x^{m}\equiv 1\pmod p }

の解であり, かつ法 { \displaystyle p } において互いに合同ではありません.

　なぜならば, この { \displaystyle m } 個の数から任意に異なる2個 { \displaystyle a^{h}, a^{k} (h\gt k) } を取り, { \displaystyle a^{h}\equiv a^{k}\pmod p } と仮定すると, { \displaystyle a^{h-k}\equiv 1\pmod p } とできることから { \displaystyle h-k } は { \displaystyle m } の倍数であることが分かります.*1

　しかし { \displaystyle h, k } は { \displaystyle 0, 1, 2, \dots ,m-1 } のいづれかであり, 例えば { \displaystyle h } がこのいづれかであれば, { \displaystyle k } はこのいづれでもなく, その逆も然りです.

　従って仮定の { \displaystyle a^{h}\equiv a^{k}\pmod p } が誤りということになります, よって

{ \displaystyle a^{0}(=1), a^{1}, a^{2},\dots a^{m-1} }

の { \displaystyle m } 個は法 { \displaystyle p } における { \displaystyle x^{m}\equiv 1\pmod p } の互いに異なる解であることが分かります.

 

　以上により, まず

{ \displaystyle 1, r, r^{2},\dots r^{p-2} }

は法 { \displaystyle p } において互いに異なる数であることが分かります.

　従ってこの組は規約代表の1組, つまり { \displaystyle a\not\equiv 0\pmod p } なる整数 { \displaystyle a } について

{ \displaystyle r^{k}\equiv a\pmod p,\quad 0\leq k\lt p-1 }

を満たす指数 { \displaystyle k } がただ一つ存在することがわかります. { \displaystyle \square }

 

 

指数の定義

　では指数の定義に入ります.

 

[定義：指数]

　補題2の通り, { \displaystyle p } を素数, { \displaystyle a } をその原始根とすると, { \displaystyle a\not\equiv 0\pmod p } となる任意の整数 { \displaystyle a } に関して

{ \displaystyle r^{\alpha}\equiv a\pmod p }

を満たす指数 { \displaystyle \alpha } が { \displaystyle 0\leq\alpha\lt p-1 } の範囲に必ず, かつただ一つ存在します.

　このとき, { \displaystyle \alpha } のことを, { \displaystyle r } を底とする { \displaystyle a } の指数と言い,

{ \displaystyle \rm{Ind}_{r}(a) = \alpha }

と書き表します.

 

　指数は上記の通り { \displaystyle 1, r, r^{2},\dots, r^{p-2} } で扱うのが常ですが, 一般に

{ \displaystyle r^{s}\equiv a\pmod p }

とすれば

{ \displaystyle s\equiv \alpha\quad(\bmod p-1) }

であるため, 上記の { \displaystyle r^{s}\equiv a\pmod p } を満たすような { \displaystyle s } についても { \displaystyle a } の指数と言えます.

 

 

指数表

　素数 { \displaystyle p } とその原始根 { \displaystyle r } における指数の関係

{ \displaystyle r^{\alpha}\equiv a\pmod p \\ \text{Ind}_r (a) = \alpha }

について, { \displaystyle a } と { \displaystyle \text{Ind}_r(a) } が1対1に対応していることは上の通りです.

　従ってその対応を表にすることができ, これを指数表と言います.

 

　例えば { \displaystyle p=7, a=3 } でやってみましょう.

　{ \displaystyle 3 } が { \displaystyle 7 } の原始根であるかどうかは, { \displaystyle p-1=7-1=6 } の正約数 { \displaystyle 1, 2, 3, 6 } のうち, { \displaystyle p-2=5 } までである { \displaystyle 1, 2, 3 } を指数として { \displaystyle 1 } と合同になるかどうかを確かめれば十分ですね(実際には指数 { \displaystyle 1 } も自明なので除外します), つまり

 

{ \displaystyle 3^{2}=9\equiv 2\not\equiv 1\pmod 7 }

{ \displaystyle 3^{3}=27\equiv -1\not\equiv 1\pmod 7 } 

 

, というわけで { \displaystyle 3 } は指数 { \displaystyle 6 } で初めて { \displaystyle 1 } と合同, つまり { \displaystyle 3 } は指数 { \displaystyle 6=7-1 } に対応するので, { \displaystyle 3 } は素数 { \displaystyle 7 } の原始根です.

　よって, まず { \displaystyle 3^{k}, k=0, 1, 2, \dots, 5=7-2 } を法 { \displaystyle 7 } について整除します.

 

{ \displaystyle 3^{0}=1\equiv 1\pmod 7 }

{ \displaystyle 3^{1}=3\equiv 3\pmod 7 }

{ \displaystyle 3^{2}=9\equiv 2\pmod 7 }

{ \displaystyle 3^{3}=2\times 3\equiv 6\pmod 7 }

{ \displaystyle 3^{4}\equiv 6\times 3\equiv 18\equiv 4\pmod 7 }

{ \displaystyle 3^{5}\equiv 4\times 3\equiv 12\equiv 5\pmod 7 }

 

　従って { \displaystyle p=7, r=3 } での指数表は以下になります.

 

{ \displaystyle p=7, r=3 } の指数表
{ \displaystyle N } 1 2 3 4 5 6
{ \displaystyle \text{Ind}_3(N) } 0 2 1 4 5 3

 

 

〆

　次回はこの指数表を利用したものを紹介したいと思います.

 

 

*1:2018.05.03 { \displaystyle a^{h-k}\equiv 0\pmod p }から訂正しました, cle-neige さんご指摘ありがとうございます！

thetheorier