1. 高校数学の美しい物語
  2. 原始根の定義と具体例(高校生向け)

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

更新日時 2021/03/07
原始根の定義

33 以上の)素数 pp11 以上 pp 未満の整数 rr が以下の性質を満たすとき,rr を法 pp に対する原始根と呼ぶ。

r,r2,,rp2r,r^2,\cdots,r^{p-2} のいずれもが pp で割って余り 11 でない」

(また,r=1r=1p=2p=2 に対する原始根である,とする。)

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

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

目次
  • 原始根と位数について

  • 原始根の具体例

  • 原始根の重要な定理

  • 原始根の存在定理

原始根と位数について

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

mod7\:\mathrm{mod}\:7 で考えたとき,2,222,2^277 で割って余りが 11 ではないが 23=82^3=877 で割って 11 となるので法 77 に対する 22 の位数は 33 となる。

フェルマーの小定理より,pp が素数なら 1a<p1\leq a <p なる任意の自然数 aa に対して ap11(modp)a^{p-1}\equiv 1\pmod{p} なので,素数 pp で考えたときの位数は必ず p1p-1 以下です。

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

原始根の具体例

引き続き法 77 で考えてみます。

上記の例により 22 は原始根でないことが分かります。

次に 33 を考えてみると,

33,32=92,3323634634,35435,365313\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

となり 33 の位数は 66 です。つまり 3377 に対する原始根です。

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

原始根の重要な定理

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

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

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

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

証明

背理法で示す。rr が原始根なのに rnr^{n} たちの余りが全て異ならないと仮定する。

つまり rmrnr^{m}\equiv r^{n} となる自然数 m,n(p1m>n)m,n \:( p-1 \geq m > n) が存在する。

これは rn(rmn1)0r^n(r^{m-n}-1)\equiv 0 と同値。

ここで,rrpp は互いに素なので rmn10r^{m-n}-1\equiv 0

これは原始根の定義(rr の位数が p1p-1 であること)に矛盾する。

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

原始根の存在定理

任意の素数 pp に対して原始根 rr が存在する。

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

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

原始根定理の証明はけっこう大変です。

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

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

原始根の応用についてはもう少し詳しく解説する予定です。追記:位数の性質と原始根の応用

人気記事
  1. 高校数学の美しい物語
  2. 原始根の定義と具体例(高校生向け)