原始根② 指数計算 - プライムス

前回の原始根における記事で素数 $p$ を法とする原始根の存在を示しました。
mathnote.info
今回は原始根を用いて乗法群における対数の類似である指数を導入し、その性質について紹介します。

参考文献
indexの定義
指数とべき乗剰余
指数と位数の関係
おわりに

参考文献

(1)Elements of number theory

リンク

(2)整数論入門

リンク

indexの定義

まず原始根について簡単に復習します。
整数 $m$ と $(a,m)=1$ を満たす整数に対して
\begin{equation*}
a^r\equiv 1 \; (\text{mod} \; m)
\end{equation*}を満たす最小の正整数 $r$ を $a$ のmod $m$ における位数と呼び $\text{ord}_m(a)$ と書きます。
さらに $\text{ord}_m(a)=\phi(m)$ を満たす $a$ をmod $m$ の原始根と呼びます。
一般にmod $m$ の原始根が存在するかどうかは分かりませんが、冒頭で紹介したように前回の記事で素数 $p$ を法とする原始根の存在を証明しました*1。

以下、素数 $p$ をひとつ固定します。

Definition1(指数)

$g$ をmod $p$ の原始根とし、 $a$ を $(a,p)=1$ を満たす整数とする。このとき
\begin{equation*}
g^r \equiv a \; (\text{mod} \; p)
\end{equation*}を満たす最小の非負整数 $r$ を $g$ を底とする $a$ の指数と呼び $\text{ind}_g(a)$ と書く。

前回の記事のlemma 3から $p \nmid a,b$ の時
\begin{equation}
a\equiv b \; (\text{mod} \; p) \; \Leftrightarrow \; \text{ind}_g(a)=\text{ind}_g(b)　\label{eq2}
\end{equation}が容易に分かります。

以下、mod $p$ の原始根 $g$ を一つ固定して議論します*2。また $\text{ind}_g(a)$ を略記して $\text{ind}(a)$ と書くことにします。指数は対数と似た次のような性質を持ちます。

Proposition 2

$p\nmid a,b$ のとき
\begin{equation*}
\text{ind}(ab) \equiv \text{ind}(a)+\text{ind}(b) \; (\text{mod}\; p-1)
\end{equation*}が成立する。

証明前回の記事のLemma 3及び
\begin{equation*}
g^{\text{ind}(ab)} \equiv ab \equiv g^{\text{ind}(a)} g^{\text{ind}(b)} \; (\text{mod} \; p)
\end{equation*}より従う。(QED)

掛け算を行う際に対数表を用いて計算する方法は有名ですが、Proposition 2から指数表を用意することで対数と同様に掛け算を足し算に変換できることが分かります。

例として $p=37$ の指数表を見ていきます。
$g=2$ としたときの指数表は次のようになります。

この表は

各行の見出しが指数の10の位
各列の見出しが指数の1の位
行列の成分が2^(10×行の見出し+列の見出し)をmod $37$ で見たときの値

というように対応しています。この表は指数と整数の相互参照が出来るようになっています。読み方の具体例を挙げます。

(例1) 26の指数 $\text{ind}(26)$ を知りたい場合、まず表の成分から26を見つける。26は2行目の3列にあるので見出しを見ることで $\text{ind}(26)=12$ がわかる。

(例2) 逆に指数が19になる整数を見つけたい場合、表の2行10列目の成分である35が指数19を持つ。つまり $\text{ind}(35)=19$ となる。

(例3) 26×35をmod $37$ で計算したい。指数表からそれぞれの指数が12, 19であることがわかるのでProposition 2から
\begin{equation*}
\text{ind}(26\times 35)\equiv 12+19 =31 \; (\text{mod}\; 36)
\end{equation*}となる。指数が31となる数は指数表から22であることがわかるので\eqref{eq2}から
\begin{equation*}
26\times 35 \equiv 22 \; (\text{mod}\; 37)
\end{equation*}が得られる。

指数とべき乗剰余

次に指数を用いて合同方程式
\begin{equation}
x^n \equiv a \; ( \text{mod} \; p) \label{eq1}
\end{equation}について考えます。 $p\nmid a$ で\eqref{eq1}が解をもつとき $a$ は $n$ 乗剰余であると言います。たとえば平方剰余についてはGaussによる有名な定理がありますが、一般の剰余に対して指数を用いて次のことが言えます。

Proposition 3

$d=(n,p-1)$ と置く。 $p\nmid a$ のとき次の三つは同値

\eqref{eq1}が解を持つ
$d|\text{ind}(a)$
$a^{(p-1)/d} \equiv 1 \; (\text{mod}\; p)$ *3

証明 ( $1 \Leftrightarrow 2$ ) \eqref{eq2}とProposition 2から、\eqref{eq1}が解を持つことは
\begin{equation*}
n \; \text{ind} (x) \equiv \text{ind}(a) \; (\text{mod} \; p-1)
\end{equation*}が解を持つことと同値。この一次合同方程式が解を持つことは $d|\text{ind}(a)$ となることと同値。
( $2 \Leftrightarrow 3$ ) \eqref{eq2}を用いて
\begin{align*}
&\text{ind}(a) \equiv 0 \; (\text{mod}\; d) \\
\Leftrightarrow \quad &\frac{p-1}{d} \text{ind}(a) \equiv 0 \; (\text{mod}\; \frac{p-1}{d}d = p-1) \\
\Leftrightarrow \quad &a^{(p-1)/d} \equiv 1 \; (\text{mod} \; p)
\end{align*}となる。(QED)

Proposition 3から指数表があれば具体的な整数 $a,n$ に対して\eqref{eq1}が解を持つかどうか簡単に判定することが出来ます。

$p=37,g=2$ の場合の指数表を再掲して具体例を見てみます。

(例1) $x^{14}\equiv 26 \; (\text{mod}\; 37)$ が解を持つかどうか考える。このとき $d=(14,36)=2$ であり、指数表から $\text{ind}(26)=12$ なので $d|\text{ind}(26)$ が成立。Proposition 3からこの方程式は解を持つことがわかる。

(例2) $x^{14} \equiv 15 \; (\text{mod} \; 37)$ は解を持たない。なぜなら指数表から $\text{ind}(15)=13$ であり $d\nmid \text{ind}(15)$ となるため。

指数と位数の関係

指数について色々と紹介してきましたが、最後に指数と位数の関係について述べて終わりにしたいと思います。

Proposition 4

$\delta|p-1$ とする。このとき $p\nmid a$ に対して $a$ の位数が $\delta$ になることと
\begin{equation*}
(\text{ind}(a),p-1)=\frac{p-1}{\delta}
\end{equation*}が成立することは同値。

証明 $\text{ord}_p(a)=\delta$ とする。定義から
\begin{equation*}
a^{\delta} \equiv 1 \; (\text{mod}\; p)
\end{equation*}が成立。従ってProp 3から $(p-1)/\delta$ は $\text{ind}(a)$ の約数であることがわかる。さらに $\text{ord}_p(a)$ の最小性から、 $p-1$ と $\text{ind}(a)$ の公約数のうち $(p-1)/\delta$ が最大のものとなる。従って
\begin{equation*}
(\text{ind}(a),p-1)=\frac{p-1}{\delta}
\end{equation*}が成立する。逆に等式が成立しているなら $\delta$ は
\begin{equation*}
\frac{p-1}{c} |\text{ind}(a)
\end{equation*}を満たす $c|p-1$ のうち最小の数である。このときProp 3から
\begin{equation*}
a^c \equiv 1 \; ( \text{mod} \; p)
\end{equation*}となるが、 $\delta$ の最小性から $\text{ord}_p(a)=\delta$ がわかる。(QED)

この命題をもちいて原始根の数を計算することが出来ます。

Corollary 5

$\delta| p-1$ とする。このとき $\text{mod}\; p$ の元で位数 $\delta$ のものはちょうど $\phi(\delta)$ 個存在する。特にmod $p$ の原始根はちょうど $\phi(p-1)$ 個存在する。

証明 Proposition 4から
\begin{equation*}
( r,p-1)=\frac{p-1}{\delta}
\end{equation*}を満たす $r=1,\dots , p-1$ を数え上げればよい。そのような $r$ は $(p-1)/\delta$ の倍数なので
\begin{equation*}
\frac{p-1}{\delta}, \; 2\; \frac{p-1}{\delta}, \dots , \; \delta \; \frac{p-1}{\delta}
\end{equation*}のうち
\begin{equation*}
r=c \; \frac{p-1}{\delta} \quad ((c,\delta)=1)
\end{equation*}と書ける数で全てである。従って位数 $\delta$ の元はちょうど $\phi(\delta)$ 個ある。