一歩先を行く整数論：原始根の例題と応用を徹底解説
目次
原始根とは？
原始根（げんしこん）とは、ある素数 \( p \) に対して、その法のもとで全ての非零剰余類を生成する整数のことです。 言い換えると、整数 \( g \) が素数 \( p \) に対する原始根であるとは、次のような意味です：
\[ \{g^1 \bmod p, g^2 \bmod p, \dots, g^{p-1} \bmod p\} = \{1, 2, \dots, p-1\} \]つまり、\( g \) の累乗を法 \( p \) で取っていくと、\( 1 \) から \( p-1 \) の全ての整数が一度ずつ現れるという性質を持ちます。
原始根の存在と条件
すべての自然数に対して原始根が存在するわけではありません。以下の条件のときに原始根が存在します。
- \( p \) が素数のとき：原始根は必ず存在します。
- \( n = 2, 4, p^k, 2p^k \)（ただし \( p \) は奇素数、\( k \geq 1 \)）：このときのみ \( n \) に対して原始根が存在します。
したがって、合成数（例えば \( 15 \) や \( 20 \)）には原始根が存在しない場合もあります。
基本的な例題
例題1：7に対する原始根を求めよ。
まず \( 7 \) は素数なので、原始根が存在します。\(\phi(7) = 6\) です。
候補となる整数 \( g \) に対して \( g^k \mod 7 \) の値を \( k = 1, 2, \dots, 6 \) まで調べます。
\( g = 3 \) のとき：
\[ 3^1 \equiv 3 \mod 7 \\ 3^2 \equiv 2 \mod 7 \\ 3^3 \equiv 6 \mod 7 \\ 3^4 \equiv 4 \mod 7 \\ 3^5 \equiv 5 \mod 7 \\ 3^6 \equiv 1 \mod 7 \]1～6まで全て揃っているので、3は7の原始根です。
例題2：11に対する原始根を一つ求めよ。
11は素数なので原始根は存在します。\(\phi(11) = 10\)。
\( g = 2 \) を試します：
\[ 2^1 \equiv 2 \\ 2^2 \equiv 4 \\ 2^3 \equiv 8 \\ 2^4 \equiv 5 \\ 2^5 \equiv 10 \\ 2^6 \equiv 9 \\ 2^7 \equiv 7 \\ 2^8 \equiv 3 \\ 2^9 \equiv 6 \\ 2^{10} \equiv 1 \mod 11 \]1〜10の整数がすべて揃っているので、2は11の原始根です。
応用的な例題
例題3：原始根を用いて合同方程式 \( 5^x \equiv 9 \mod 23 \) を解け。
23は素数なので原始根が存在します。まず、23に対する原始根を見つけます。
調べると、5が原始根であることがわかります。
このとき、5の冪乗を順に計算し、どこで9になるかを探します：
\[ 5^1 \equiv 5 \\ 5^2 \equiv 2 \\ 5^3 \equiv 10 \\ 5^4 \equiv 4 \\ 5^5 \equiv 20 \\ 5^6 \equiv 8 \\ 5^7 \equiv 17 \\ 5^8 \equiv 16 \\ 5^9 \equiv 11 \\ 5^{10} \equiv 9 \mod 23 \]よって解は \( x \equiv 10 \mod 22 \)（23のオイラー関数 \(\phi(23)=22\)）。
例題4：任意の素数 \( p \) に対し、原始根の個数を求めよ。
原始根の個数は \(\phi(p-1)\) です。例えば \( p = 11 \) の場合、\( p – 1 = 10 \) なので、
\[ \phi(10) = 4 \]つまり、11には4個の原始根があります。
原始根の応用
暗号理論
原始根はディフィー・ヘルマン鍵交換などの公開鍵暗号の基礎をなしています。例えば、大きな素数 \( p \) とその原始根 \( g \) を使って、共通鍵を安全に交換するプロトコルが構築されます。
周期性の解析
原始根を用いることで、特定の数列の周期性や性質を調べることができます。例えば、ある数列の最小周期を求める際に役立ちます。
合同方程式の解法
先述のように、原始根を使うことで指数型の合同方程式を解くことができます。これは大学入試や数学オリンピックでもよく出題される応用です。
