2014/08/31

原始根の定義と具体例(高校生向け)

分野: 整数問題  レベル: 数学オリンピック

原始根の定義:
($3$ 以上の)素数 $p$ と $1$ 以上 $p$ 未満の整数 $r$ が以下の性質を満たすとき $r$ を法 $p$ に対する原始根と呼ぶ。
「 $r,r^2,\cdots,r^{p-2}$ のいずれもが $p$ で割って余り $1$ でない」
(また,$r=1$ は $p=2$ に対する原始根である,とする。)

原始根はより発展的な定理を証明するのに非常に強い道具です。また,数学オリンピックでも知っていると有利になる問題がときどき出題されます。

群論の言葉を使えばもう少しスッキリ書ける部分もありますが,高校生に理解しやすいよう努めました。前提知識として必要なのはフェルマーの小定理合同式の定義と簡単な性質のみです。

原始根と位数について

$r,r^2,r^3,\cdots$ と $r$ のベキを増やしていき,はじめて「 $p$ で割った余りが $1$ となる」ような指数のことを $r$ の位数と言います。

$\:\mathrm{mod}\:7$ で考えたとき,$2,2^2$ は $7$ で割って余りが $1$ ではないが $2^3=8$ は $7$ で割って $1$ となるので法 $7$ に対する $2$ の位数は $3$ となる。

フェルマーの小定理より $p$ が素数なら $1\leq a <p$ なる任意の自然数 $a$ に対して $a^{p-1}\equiv 1\:\mathrm{mod}\:p$ なので素数 $p$ で考えたときの位数は必ず $p-1$ 以下です。

この「位数」という言葉を使うと原始根は「位数が $p-1$ であるもの」と簡潔に表現することができます。

原始根の具体例

引き続き法 $7$ で考えてみます。
上記の例により $2$ は原始根でないことが分かります。

次に $3$ を考えてみると,
$3\equiv 3, \\3^2=9\equiv 2, \\3^3\equiv 2\cdot 3\equiv 6,\\
3^4\equiv 6\cdot 3\equiv 4,\\ 3^5\equiv 4\cdot 3\equiv 5,\\ 3^6\equiv 5\cdot 3\equiv 1$
となり $3$ の位数は $6$ です。つまり $3$ は $7$ に対する原始根です。

このように原始根のべき乗の余りは「 $3,2,6,4,5,1$ 」のように $1$ から $6$ をそれぞれ $1$ 回ずつ巡っています。これは一般的に成り立つ重要な定理です。

原始根の重要な定理

先ほどの例を一般化したものです。

$r$ が $p$ に対する原始根のとき $r,r^2,\cdots,r^{p-1}$ を $p$ で割ったあまりは全て異なり,その余りは $1$ から $p-1$ を一巡する。

※こちらを原始根の定義とする流儀もあるようです。

証明は比較的簡単です,(フェルマーの小定理を誘導として)入試で出るかもしれません。

証明

背理法で示す。 $r$ が原始根なのに $r^{n}$ たちの余りが全て異ならないと仮定する。
つまり $r^{m}\equiv r^{n}$ となる自然数 $m,n \:( p-1 \geq m > n)$ が存在する。
これは $r^n(r^{m-n}-1)\equiv 0$ と同値。
ここで,$r$ と $p$ は互いに素なので $r^{m-n}-1\equiv 0$
これは原始根の定義($r$ の位数が $p-1$ であること)に矛盾する。

よって,$r,r^2,\cdots,r^{p-1}$ のべき乗たちの余り(全部で $p-1$ 個ある)は全て異なり $0$ ではないので,$1$ から $p-1$ を一巡する。

原始根の存在定理

任意の素数 $p$ に対して原始根 $r$ が存在する。

これは原始根定理と呼ばれる非常に偉大な定理です。

任意の素数 $p$ に対してべき乗たちの余りが一巡するような $r$ が存在するというのが非常に嬉しい性質で,これを利用してより複雑な定理を証明することができるのです。

原始根定理の証明はけっこう大変です。
初等的な証明は例えば原始根定理の証明(青空学園)にあります。

原始根定理は数学オリンピックで証明なしで使ってOKです。(数オリ関連の(公式な)書籍にそのような記述がありました)

原始根の応用についてはもう少し詳しく解説する予定です。追記:位数の性質と原始根の応用
分野: 整数問題  レベル: 数学オリンピック