原始根

$p - 1$ の各素因数 $q$ について $g^{(p - 1) / q} \neq \equiv 1 (mod p)$ を確かめて原始根 $g$ を見つけられる。素数 $p$ を法とする原始根の個数 $φ (p - 1)$ 、位数 $d$ の元の個数 $φ (d)$ 、 $x^{k} \equiv a (mod p)$ の解の個数（ $g cd (k, p - 1)$ 個または 0 個）を求められる

前提

法 n を法とする位数（大学数学整数論）
群の位数と元の位数（大学数学代数学）

この技能までの道筋（29 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
オイラー関数の計算（大学数学整数論）
フェルマーの小定理とオイラーの定理（大学数学整数論）
法 n を法とする位数（大学数学整数論）
群の位数と元の位数（大学数学代数学）

説明

素数 $p$ を法として位数がちょうど $p - 1$ になる整数 $g$ を、法 $p$ の原始根といいます。原始根 $g$ があると、 $p$ で割り切れない整数はすべて $g^{j}$ の形で表せるので、法 $p$ の世界が巡回群 $Z / (p - 1) Z$ の世界に置き換わります。この技能では、 $p - 1$ の素因数だけを使った判定で原始根を見つけます。さらに、原始根の個数 $φ (p - 1)$ 、位数 $d$ の元の個数 $φ (d)$ 、方程式 $x^{k} \equiv a (mod p)$ の解の個数を求められるようになります。

なぜそうしてよいのか

【判定法の理由】フェルマーの小定理より $g^{p - 1} \equiv 1$ なので、 $d = ord_{p} (g)$ は $p - 1$ の約数です。 $d < p - 1$ なら $\frac{p - 1}{d} > 1$ なので、これを割り切る素数 $q$ が 1 つとれます。 $q$ は $p - 1$ の素因数でもあり、 $d ∣ \frac{p - 1}{q}$ となるので $g^{(p - 1) / q} \equiv 1$ です。逆に、ある素因数 $q$ で $g^{(p - 1) / q} \equiv 1$ なら $d \leq \frac{p - 1}{q} < p - 1$ です。したがって「 $p - 1$ のすべての素因数 $q$ について $g^{(p - 1) / q} \neq \equiv 1 (mod p)$ 」は「 $g$ が原始根」と同じことです。 $p - 1$ の約数をすべて調べる必要はなく、素因数の数だけ計算すれば足ります。

【原始根が必ずあること】 $p$ は素数なので、 $mod p$ で積が $0$ なら因数のどちらかが $0$ です。このため因数定理がそのまま使え、 $d$ 次多項式の $mod p$ での根は高々 $d$ 個です。いま $d ∣ p - 1$ とし、位数 $d$ の元 $a$ が 1 つあるとします。 $1, a, \dots, a^{d - 1}$ は $x^{d} \equiv 1$ の互いに異なる $d$ 個の根なので、根はこれで全部です。そのうち位数がちょうど $d$ のものは $g cd (j, d) = 1$ を満たす $a^{j}$ だけなので、ちょうど $φ (d)$ 個です。よって位数 $d$ の元の個数 $ψ (d)$ は $0$ か $φ (d)$ のどちらかです。一方、 $1, \dots, p - 1$ はそれぞれ $p - 1$ のどれかの約数を位数にもつので $\sum_{d ∣ p - 1} ψ (d) = p - 1$ です。また $Z / (p - 1) Z$ の元を位数で分類すると $\sum_{d ∣ p - 1} φ (d) = p - 1$ も成り立ちます。 $ψ (d) \leq φ (d)$ なので、すべての $d$ で $ψ (d) = φ (d)$ となります。特に原始根は $φ (p - 1) \geq 1$ 個あります。

【方程式への応用】原始根 $g$ をとると、 $1, \dots, p - 1$ は $g^{0}, \dots, g^{p - 2}$ と 1 対 1 に対応します。 $p ∤ a$ のとき $a \equiv g^{t}$ 、 $x \equiv g^{y}$ と書くと、 $x^{k} \equiv a ⟺ g^{k y} \equiv g^{t} ⟺ k y \equiv t (mod p - 1)$ です。 $e = g cd (k, p - 1)$ とおくと、この 1 次合同式は $e ∣ t$ のときに限り解をもち、そのとき解は $mod p - 1$ でちょうど $e$ 個です。条件 $e ∣ t$ は $a^{(p - 1) / e} = g^{t (p - 1) / e} \equiv 1$ と同値です（ $p - 1 ∣ \frac{t ( p - 1 )}{e} ⟺ e ∣ t$ だから）。

手順

$p - 1$ を素因数分解し、相異なる素因数 $q_{1}, \dots, q_{r}$ を書き出す。調べる指数は $\frac{p - 1}{q _{1}}, \dots, \frac{p - 1}{q _{r}}$ である。
候補 $g$ （ $p ∤ g$ 。ふつうは $2, 3, \dots$ の順）について $g^{(p - 1) / q_{i}} mod p$ を計算する。どれも $1$ でなければ $g$ は原始根。1 つでも $\equiv 1$ なら次の候補に移る。
原始根 $g$ が 1 つ見つかれば、原始根の全体は $g cd (j, p - 1) = 1$ を満たす $g^{j}$ である。個数は $φ (p - 1)$ 個。 $d ∣ p - 1$ に対し、位数 $d$ の元は $φ (d)$ 個ある。
$x^{k} \equiv a (mod p)$ （ $p ∤ a$ ）の解の個数を調べるには、 $e = g cd (k, p - 1)$ とおく。 $a^{(p - 1) / e} \equiv 1$ なら解はちょうど $e$ 個、そうでなければ $0$ 個である。

例題

$23$ を法とする原始根のうち、最小の正の整数を求めよ。

例題の解答

手順1： $p - 1 = 22 = 2 \cdot 11$ なので、調べる指数は $\frac{22}{2} = 11$ と $\frac{22}{11} = 2$ である。

手順2：小さい候補から順に調べる。
・ $g = 2$ ： $2^{11} = 2048 = 23 \cdot 89 + 1$ より $2^{11} \equiv 1$ 。原始根ではない。
・ $g = 3$ ： $3^{3} = 27 \equiv 4$ より $3^{9} \equiv 4^{3} = 64 \equiv 18$ 。よって $3^{11} \equiv 18 \cdot 9 = 162 = 23 \cdot 7 + 1 \equiv 1$ 。原始根ではない。
・ $g = 4$ ： $4^{11} = (2^{11})^{2} \equiv 1$ 。原始根ではない。
・ $g = 5$ ：まず $5^{2} = 25 \equiv 2 \neq \equiv 1$ 。次に $5^{11} = 5 \cdot (5^{2})^{5} \equiv 5 \cdot 2^{5} = 160 = 23 \cdot 6 + 22 \equiv - 1 \neq \equiv 1$ 。どちらの指数でも $1$ にならないので、 $5$ は原始根である。

よって最小の正の原始根は $5$ である（参考：手順3より、法 $23$ の原始根は全部で $φ (22) = 10$ 個ある）。

答え: $5$

よくある誤り

$g^{p - 1} \equiv 1$ を確かめただけで原始根と判断してしまう誤り。フェルマーの小定理により、 $p ∤ g$ ならこれは常に成り立つ。例えば $2^{22} \equiv 1 (mod 23)$ だが、 $2^{11} \equiv 1$ なので $2$ は原始根ではない。正しくは、各素因数 $q$ について $g^{(p - 1) / q} \neq \equiv 1$ を確かめる。
$p - 1$ の素因数の一部しか調べない誤り。例えば $p = 13$ では $12 = 2^{2} \cdot 3$ なので、指数 $6$ と $4$ の両方を調べる必要がある。 $5^{6} \equiv - 1 \neq \equiv 1 (mod 13)$ だけを見て原始根としてしまうと誤りで、実際は $5^{4} \equiv 1$ なので位数は $4$ である。
原始根の個数を $φ (p) = p - 1$ 個としてしまう誤り。正しくは $φ (p - 1)$ 個。例えば法 $23$ なら $22$ 個ではなく $φ (22) = 10$ 個である。
$x^{k} \equiv a (mod p)$ の解がいつも $k$ 個あると考えてしまう誤り。正しくは $e = g cd (k, p - 1)$ 個または $0$ 個である。例えば $x^{3} \equiv 1 (mod 11)$ は $g cd (3, 10) = 1$ なので、解は $x \equiv 1$ の 1 個だけ。一方 $x^{3} \equiv 1 (mod 7)$ は $g cd (3, 6) = 3$ なので、解は $x \equiv 1, 2, 4$ の 3 個ある。また $a \equiv 0$ の場合は別扱いで、解は $x \equiv 0$ の 1 個だけである。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

原始根

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題