xk ≡ 1 (mod p) の根の個数

$x^k\equiv 1\;(\mathrm{mod}\:p)$ の根の個数

 素数 $p$ を法とする $k$ 次合同方程式
 
\[x^k\equiv 1\quad (\mathrm{mod}\:p)\]
の根が最大でいくつあるのかを述べたのが次の定理です。

[定理 E3] $x^k\equiv 1\;(\mathrm{mod}\:p)$ の根の個数は $k$ を超えない。

[定理 E3 の証明]
 数学的帰納法で証明します。$k=1$ のときは
 
\[x\equiv 1\quad (\mathrm{mod}\:p)\]
なので、これは 1 元 1 次合同方程式 で $(1,\:p)=1$ なので解は 1 つです。次に $k-1\;(k\geq 2)$ のときに根の個数が $k-1$ を超えないと仮定します。このとき合同方程式
 
\[x^k\equiv 1\quad (\mathrm{mod}\:p)\]
に根が1つもないならば定理は成り立っています。もし根が1つでもあって、それを $x_1$ とすれば
 
\[x_1^k\equiv 1\quad (\mathrm{mod}\:p)\]
が成り立ちます。よって
 
\[x^k-x_1^k\equiv 0\quad (\mathrm{mod}\:p)\]
 左辺は $x=x_1$ を因数にもつので、$k-1$ 次式 $g(x)$ を用いて
 
\[x^k-x_1^k=(x-x_1)\,g(x)\]
と書くことができます。したがって
 
\[(x-x_1)\,g(x)\equiv 0\quad (\mathrm{mod}\:p)\]
 $x_1$ と合同でない根を $x_2$ とすると
 
\[(x_2-x_1)\,g(x)\equiv 0\quad (\mathrm{mod}\:p)\]
 $x_2-x_1\not\equiv 0,\:\:(x_2-x_1,p)=1$ なので
 
\[g(x_2)\equiv 0\quad (\mathrm{mod}\:p)\]
 すなわち $x_2$ は $k-1$ 次合同方程式の解であり、仮定によりその根の個数は $k-1$ 個を超えません。したがって、
 
\[x^k\equiv 1\quad (\mathrm{mod}\:p)\]
の根の個数は $k$ 個を超えないことになります。(証明終)

 法が素数ならば、$x^2\equiv 1$ の根は 2 個以内、$x^3\equiv 1$ の解は 3 個以内ということです。これを $n$ 次合同方程式の場合に一般化した定理はラグランジュの定理とよばれますが、それについてはもう少し先で紹介します。

 ≫ 整数のベキ乗の位数を計算する公式 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください