原始根の定義と具体例（高校生向け）

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

フェルマーの小定理より，$p$ が素数なら $1\leq a <p$ なる任意の自然数 $a$ に対して $a^{p-1}\equiv 1\pmod{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$ 回ずつ巡っています。これは一般的に成り立つ重要な定理です。

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

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

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

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

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

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

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

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