素数の原始根

素数の原始根
原始根の一般的な定義

素数の原始根

位数について復習しておきます。位数とは
$a^{k} \equiv 1 (\mod m)$
となるような最小の正整数 $k$ であり、
$k = {ord}_{m} (a)$
と表しました。ここで素数 $p$ についてはフェルマーの小定理
$a^{p - 1} \equiv 1 (\mod p)$
が成り立っています。このとき、もし $p - 1$ が上の合同式を満たす最小のベキ指数であるならば、位数は $p - 1$ となります。このような条件を満たす正整数 $a = g$ を $p$ の原始根（primitive root）とよびます：
$p - 1 = {ord}_{p} (g)$
すなわち原始根 $g$ とは $g^{1}, g^{2}, \dots$ とべき乗をつくっていったときに、ベキ指数が $p - 1$ のときに初めて
$g^{p - 1} \equiv 1 (\mod p)$
となるような正整数のことです。

【定義E2】

{ord}_{p} (g) = p - 1

を満たす

g

を

p

の原始根と定義する。

たとえば $p = 7$ においては $p - 1 = 6$ 乗で初めて $1$ と合同になる数が原始根です。具体的に調べてみると …
$\begin{aligned} 3^{1} \equiv 3 & (\mod 7) \\ 3^{2} \equiv 9 \equiv 2 & (\mod 7) \\ 3^{3} \equiv 6 & (\mod 7) \\ 3^{4} \equiv 18 \equiv 4 & (\mod 7) \\ 3^{5} \equiv 12 \equiv 5 & (\mod 7) \\ 3^{6} \equiv 15 \equiv 1 & (\mod 7) \end{aligned}$
となるので $3$ は $7$ の原始根です。また、
$\begin{aligned} 5^{1} \equiv 5 & (\mod 7) \\ 5^{2} \equiv 25 \equiv 4 & (\mod 7) \\ 5^{3} \equiv 20 \equiv 6 & (\mod 7) \\ 5^{4} \equiv 30 \equiv 2 & (\mod 7) \\ 5^{5} \equiv 10 \equiv 3 & (\mod 7) \\ 5^{6} \equiv 15 \equiv 1 & (\mod 7) \end{aligned}$
となるので $5$ も $7$ の原始根です。このように原始根は複数存在することもあります。そうすると、 $g = 3, 5$ で原始根を取りつくしたかどうか心配になりますが、ここで前回学んだ定理E5を参照します：

【定理E5】素数

p

を法として、

p - 1

の任意の正の約数

d

に等しい位数をもつ整数

a

、すなわち

{ord}_{p} (a) = d

を満たす整数

a

は必ず存在し、

1, 2, \dots, p - 1

のなかに

φ (d)

個ある。

今は $p - 1$ の最大の約数である $p - 1$ を考えればいいので、

【定理E6】素数

p

の原始根は

φ (p - 1)

個あります。

$p = 7$ のときは
$φ (6) = φ (2) φ (3) = 1 \cdot 2 = 2$
なので全部で 2 個です。つまり $g = 3, 5$ で原始根を取りつくしていることがわかります。素数 $\mod 7$ のベキ乗表でも、これ以外に原始根が存在しないことを確認しておいてください。

Excel 数論 mod7の表で位数を調べる

原始根の一般的な定義

必ずしも素数ではない $m$ について、原始根を次のように定義します。

【定義E3】

{ord}_{m} (g) = φ (m)

を満たす

g

を

m

の原始根と定義します。

すなわち $m$ の原始根とは、ベキ乗して $φ (m)$ で初めて
$g^{φ (m)} \equiv 1 (\mod p)$
となるような正整数 $g$ のことです。ただし本講座では当面の間は素数の原始根を扱いますので、一般の原始根についてはあまり気にする必要はありません。

【次の講座】≫ 指数（離散対数）

素数の原始根

原始根の一般的な定義

エクセルや数学に関するコメントをお寄せください