次: 演習問題 上: 原始根と指数 前: 原始根

指数

定理 28 に述べたように $r$ を $p$ の原始根とすれば $a\not \equiv 0\quad (\bmod.\ p)$ である任意の整数 $a$ に対して

$$r^{\alpha}\equiv a\quad (\bmod.\ p)$$

となる整数 $\alpha$ が $0\le \alpha < p-1$ の範囲に必ず，しかもただ一つ 存在する．この $\alpha$ を $r$ を底としての $a$ の指数(index) といい，それを次のように表す．

$$\Ind_r(a)=\alpha$$

指数 $\alpha$ を $0\le \alpha < p-1$ の範囲にかぎる必要はない．一般に

$$r^s\equiv a\quad (\bmod.\ p)$$

ならば

$$s\equiv \alpha\quad (\bmod.\ p-1)$$

この $s$ なども指数とすれば, $a$ の指数は $p-1$ を法として一意に定まる．

$$\Ind_r(a)\equiv s\quad (\bmod.\ p-1)$$

$a\equiv b\quad (\bmod.\ p)$ であることと， $\Ind_r(a)\equiv \Ind_r(b)\quad (\bmod.\ p-1)$ であることは同値である．

したがって指数を次のように定義することもできる．

$r$ を $p$ の原始根とすれば $p$ を法とする0でない任意の剰余系の 代表である整数 $a$ に対して

$$r^{\alpha}\equiv a\quad (\bmod.\ p)$$

となる $\alpha$ が $p-1$ を法としてただ一つ存在する． つまり $\alpha$ は $p-1$ を法とする剰余系の代表となる． この剰余系を $r$ を底としての $a$ の「指数」といい， それを$\Ind_r(a)$と表す．

意味が明白なときは等号で表す．また「$\Ind_r(a)$の値」というときは，厳密には $p-1$ を法とする剰余系の一つを指すが，その剰余系のある代表値で表すこともする． 底が定まっているときは省略して$\Ind.\,a$とも記すことにする．

例 2.5.2        $p=13$ のとき．2は原始根である． $p$ を法とする剰余系の数 $a$ に対する底2の指数 $I=\Ind.\,a$ は，この節の冒頭の表より次のようになる．

$$\begin{array}{\vert c\vert rrrrrrrrrrrr\vert} \hline a... ...hline I&0&1&4&2&9&5&11&3&8&10&7&6\\ \hline \end{array}$$

定理 29
     素数 $p$ を法として原始根 $r$ を底とするとき，

$$\begin{array}{l} \Ind.\,ab\equiv \Ind.\,a+\Ind.\,b，\\ ... ...,a^n\equiv n\Ind.\,a\ ． \end{array} \quad (\bmod.\ p-1)$$

が成り立つ．■

証明     $\Ind.\,a=\alpha,\ \Ind.\,b=\beta$ とする．つまり

$$a\equiv r^{\alpha},\ \quad b\equiv r^{\beta}\quad \quad (\bmod.\ p)$$

ゆえに

$$ab\equiv r^{\alpha+\beta}\quad (\bmod.\ p)$$

$$∴\quad \Ind.\,ab\equiv \alpha+\beta\equiv \Ind.\,a+\Ind.\,b\quad (\bmod.\ p-1)$$

また

$$\Ind.\,a^n=\Ind.\,a\cdot a^{n-1}\equiv \Ind.\,a+\Ind.\,a^{n-1}\quad (\bmod.\ p-1)$$

より，帰納法で

$$\Ind.\,a^n\equiv n\Ind.\,a\quad (\bmod.\ p-1)$$

となる．□

『初等整数論講義』によれば，Jacobi は『Canon arithmeticus』(1839)において 1000 以下の 素数を法とする指数を計算している．Jacobi は計算を楽しんだのだろう．そして Cunninghana という人がこの Jacobi の表の検算をおこない，正誤表が数学雜誌 「Messenger of methematics, 46巻」(1916)に載っているそうである．

例 2.5.3        $p=13$ のとき． $7x\equiv 10\quad (\bmod.\ 13)$ を解こう． 底を2とする指数をとる．

$$\Ind.\,7+\Ind.\,x\equiv \Ind.\,10\quad (\bmod.\ 12)$$

指数表から

$$11+\Ind.\,x\equiv 10\quad (\bmod.\ 12)$$

$$∴\quad \Ind.\,x\equiv -1\equiv 11\quad (\bmod.\ 12)$$

指数表から $x\equiv 7\quad (\bmod.\ 13)$ .

指数の理論の応用として，合同方程式の解の存在に関する次の定理を得る．

定理 30
     $p$ を素数とし, $a\not \equiv 0\quad (\bmod.\ p)$ とする．

二項合同方程式

$$x^n\equiv a\quad (\bmod.\ p)$$

に解があるための必要十分条件は $f=\dfrac{p-1}{(n,\ p-1)}$ とするとき

$$a^f\equiv 1\quad (\bmod.\ p)$$

である． ■

証明     $x^n\equiv a\quad (\bmod.\ p)$ を解くには $p$ を法とする原始根 $r$ をとって

$$n\cdot\Ind_rx\equiv \Ind_ra\quad (\bmod.\ p-1)$$ (2.34)

を解けばよい． 今 $(n,\ p-1)=e$ とする．定理 12 から， この合同方程式 (2.34) が解を有するための必要十分条件は， $\Ind_ra$ が $e$ で割り切れることである． $\Ind_ra=\alpha$ とする． $\alpha$ が $e$ で割り切れるとき，$\alpha=eq$ とおけば，

$$a\equiv r^{eq}\quad (\bmod.\ p)$$

$$∴\quad a^f\equiv r^{efq}=r^{(p-1)q}\equiv 1\quad (\bmod.\ p)$$

逆に $a^f\equiv 1\quad (\bmod.\ p)$ ならば， $r^{f\alpha}\equiv 1\quad (\bmod.\ p)$ ． ゆえに $f\alpha$ は $p-1=ef$ で割りきれる． つまり $\alpha$ が $e$ で割りきれ，二項合同方程式は解をもつ． 解があるとき解の数は $e=(n,\ p-1)$ 個である．□

この定理は今日では，有限群 $K^{\times}$ がただ一つの元(原始根)で 生成される巡回群であること，およびその巡回群に関する二，三の補題で示される． ここでは『初等整数論講義』にしたがって，整数論らしい証明をおこなっている．

合同方程式 $x^n\equiv a\quad (\bmod.\ p)$ が解があるかないかにしたがって $a$ を $p$ の 「$n$ べき剰余」，または「非剰余」という． もちろん，べき剰余か非べき剰余かは，同じ剰余系に属する二数では同じである． つまりべき剰余か非べき剰余かは $p$ を法とする剰余系に関することである． 0はつねに $n$ べき剰余である． $a\not \equiv 0\quad (\bmod.\ p)$ である $a$ について言えば， $(n,\ p-1)=1$ のとき任意の $a$ が $n$ べき剰余である． $(n,\ p-1)=e>1$ のときは, $\Ind.\,a$ が $e$ の倍数となる $a$ だけが $n$ べき剰余である． $p-1=ef$ とおけば，指数が $0,\ e,\ 2e,\ \cdots,\ (f-1)e$ となる数が $n$ べき剰余である． したがって $n$ べき剰余は $p$ を法として$p-1$ 個の既約剰余類のなかの $f=\dfrac{p-1}{e}$ 個だけある．

例 2.5.4        $n=2,\ p=7$ とする． $e=2,\ f=3$ である．

実際，既約剰余系

$$1,\ 2,\ \cdots,\ 6$$

のうち，2べき剰余(平方剰余)は

$$1,\ 4,\ 2$$

の3個である．

次: 演習問題 上: 原始根と指数 前: 原始根