利用者:Issei765/Draft

原始根とは法nにおいてφ(n)-1乗して初めて1となる数である。ただし、φ(n)はオイラーのφ関数である。nを素数pとすれば、p-1乗して初めて1となる数と定義できる。原始根は数論や代数学において重要な意味を持つ。

概要

例を挙げて説明する。今簡単のため素数pを7に固定する。フェルマーの小定理より、a=1,2,..6 に対して、

$a^{6}\equiv 1{\pmod {7}}$

が成立する。この定理の意味するところは、aを6乗してpで割ると余りが1であるということである。しかし、ある数は6乗しなくても1となってしまう。たとえば、

$2^{3}\equiv 1{\pmod {7}}$

である。一方6乗しなければ1とならない数も存在する。たとえば、3の冪を順番に書き出すと

${\begin{aligned}3^{1}&\equiv 3\\3^{2}&\equiv 2\\3^{3}&\equiv 6\\3^{4}&\equiv 4\\3^{5}&\equiv 5\\3^{6}&\equiv 1\end{aligned}}$

である。このようにp-1乗しないと1にならない数を原始根という。 任意の素数は必ず原始根を持つことが証明されている。例えば7の場合は3, 5が原始根である。2,4は3乗すると1に、6は2乗すると1になってしまうので原始根ではない。

原始根の性質

pの原始根をrとすれば、

{$1,r,r^{2},\cdots ,r^{p-1}$}

は1からp-1までの数が全て現れ、かつ、出現は一度だけである。