位数 (1 と合同になる最小のベキ指数)

 新しい章に入りました。今回からは位数や原始根について調べていきます。

位数の定義

 $a^k$ を $7$ で割ったときの余りを並べた表を再掲します。

 Excel 数論 mod7の表で位数を調べる

 前回記事 で説明したようにフェルマーの小定理によれば、
 
\[a^6\equiv 1\quad (\mathrm{mod}\:7)\]
が成り立ちます(表では $1$ が並んでいます)が、もちろんそれ以外にも
 
\[a^k\equiv 1\quad (\mathrm{mod}\:7)\]
になるような数 $a^k$ はあります。表で青く塗ってあるところが、それぞれの $a$ について最小のベキ指数 $k$ で $a^k\equiv 1$ をみたす数字です。たとえば $a=2$ の場合は $k=3$ のとき合同式
 
\[2^3=8\equiv 1\quad (\mathrm{mod}\:7)\]
を満たし、かつ $k=3$ はこの合同式を成り立たせる最小のベキ指数です。そこで 位数 (order) というものを次のように定義します。

[定義 E1] $a^k\equiv 1\; (\mathrm{mod}\:m)$ を満たすような最小の正整数 $k$ を $m$ に関する $a$ の位数と定義し、$\mathrm{ord}_m(a)$ と書きます。

 法 $7$ についての位数を表から読み取ると
 
\[\begin{align*}&\,\mathrm{ord}_7(1)=1\\[6pt]
&\,\mathrm{ord}_7(2)=3\\[6pt]
&\,\mathrm{ord}_7(3)=6\\[6pt]
&\,\mathrm{ord}_7(4)=3\\[6pt]
&\,\mathrm{ord}_7(5)=6\\[6pt]
&\,\mathrm{ord}_7(6)=2\\[6pt]\end{align*}\]
となります。
 

位数の基本定理

 たとえば $a=4$ のとき $\mathrm{ord}_7(4)=3$ で
 
\[4^3\equiv 1\quad (\mathrm{mod}\:7)\]
が成り立っています。以前に学んだ合同式ベキ乗に関する基本定理によると、
 
\[a\equiv b\quad (\mathrm{mod}\:m)\]
であれば
 
\[a^n\equiv b^n\quad (\mathrm{mod}\:m)\]
が成り立つので、
 
\[4^3\equiv 1\quad (\mathrm{mod}\:7)\]
についても両辺を $n$ 乗して
 
\[4^{3n}\equiv 1\quad (\mathrm{mod}\:7)\]
が成り立ちます。すなわち
 
\[4^3\equiv 4^6\equiv 4^9\equiv \cdots\equiv 1\quad (\mathrm{mod}\:7)\]
という合同式が成り立ちます。したがって
 
\[4^k\equiv 1\quad (\mathrm{mod}\:7)\]
という合同式が成り立たせる $k$ について
 
\[\mathrm{ord}_7(4)=3\,|\,k\]
が成り立つのではないかと予測できます。この段階では確証でなく予測にすぎないのは、上の議論ではたとえば $4^6$ と $4^9$ の間に $1$ と合同になる数がないとは断定できない(つまり別の周期で $1$ と合同になる数列の存在を否定できない)ので、以下の定理を証明しておく必要があります。

[定理 E1] $(a,\:m)=1$ のとき
\[a^k\equiv 1\,(\mathrm{mod}\:m)\quad\Longrightarrow\quad \mathrm{ord}_m(a)\,|\,k\]

[定理 E1 の証明] $\mathrm{ord}_m(a)=e$ とし、
 
\[k=eq+r\;(0\leq r\lt e)\]
とおきます。
 
\[1\equiv a^k\equiv a^{eq+r}\equiv (a^e)^q\,a^r\quad (\mathrm{mod}\:m)\]
 $a^e\equiv 1\;\Leftrightarrow\; (a^e)^q\equiv 1\; (\mathrm{mod}\:m)$ なので
 
\[a^r\equiv 1\quad (\mathrm{mod}\:m)\]
 $r\lt e$ なので、$r\neq 0$ とすると 位数 $e$ より小さな正数が上の合同式を満たすことになって矛盾します。よって $r=0$ となります。すなわち $k$ は $\mathrm{ord}_m(a)$ で割り切れます。(証明終)

 特に $m$ が素数 $p$ のときは、フェルマーの小定理によって
 
\[a^{\,p-1}\equiv 1\quad (\mathrm{mod}\:p)\]
が成り立つので

\[\mathrm{ord}_p(a)\,|\,p-1\]

となります。再び $\mathrm{mod}\:7$ の位数を並べてみます。
 
\[\begin{align*}&\,\mathrm{ord}_7(1)=1\\[6pt]
&\,\mathrm{ord}_7(2)=3\\[6pt]
&\,\mathrm{ord}_7(3)=6\\[6pt]
&\,\mathrm{ord}_7(4)=3\\[6pt]
&\,\mathrm{ord}_7(5)=6\\[6pt]
&\,\mathrm{ord}_7(6)=2\\[6pt]\end{align*}\]
 位数はすべて $p-1=7-1=6$ の約数になっています。

 ≫ p を法とする互いに合同でない整数のベキ乗 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。