2 項合同方程式が解をもつ条件

2 項合同方程式が解をもつ条件①

 今回は次のような 2 項合同方程式
 
\[x^n\equiv a\quad (\mathrm{mod}\:p)\]
を解いてみます。

[定理 F4] $p$ を素数、$n$ を正整数、$g$ を $p$ の原始根の1つとするとき
\[x^n\equiv a\quad (\mathrm{mod}\:p)\]が解をもつための必要十分条件は
\[(n,\:p-1)\:|\:\mathrm{Ind}_g(a)\]であり、その個数は $(n,\:p-1)$ 個です。

[定理 F4 の証明] $x^n\equiv a$ の両辺の指数をとると
 
\[n\,\mathrm{Ind}_g(x)\equiv \mathrm{Ind}_g(a)\quad (\mathrm{mod}\:p-1)\]
 これは $\mathrm{Ind}_g(x)$ についての 1 元 1 次合同方程式 なので
 
\[x^n\equiv a\;(\mathrm{mod}\:p)\]
が解をもつための必要十分条件は
 
\[(n,\:p-1)\:|\:\mathrm{Ind}_g(a)\]
であり、このとき $(n,\:p-1)$ 個の解をもちます。(証明終)

 具体例で確認してみます。たとえば、
 
\[x^2\equiv 8\quad (\mathrm{mod}\:11)\tag{1}\]
という合同方程式は、両辺の指数をとると
 
\[2\,\mathrm{Ind}_2(x)\equiv \mathrm{Ind}_2(8)\quad (\mathrm{mod}\:10)\]
となるので、$n$ と $p-1$ の最大公約数は
 
\[(n,\:p-1)=(2,\:10)=2\]
です。また、$11$ の原始根 $2$ の指数表

$a=g^e$ 1 2 3 4 5
$e$ 0 1 8 2 4
$a=g^e$ 6 7 8 9 10
$e$ 9 7 3 6 5

を見ると $\mathrm{Ind}_2(8)=3$ なので、
 
\[(2,\:10)\mid \hspace{-.67em}/\,\mathrm{Ind}_2(8)\]
となり、(1) は解をもたないことになります。それでは
 
\[x^2\equiv 9\quad (\mathrm{mod}\:p)\tag{2}\]
の場合はどうでしょう。両辺の指数をとると
 
\[2\,\mathrm{Ind}_2(x)\equiv \mathrm{Ind}_2(9)\quad (\mathrm{mod}\:10)\]
 指数表から $\mathrm{Ind}_2(9)=6$ なので
 
\[2\,\mathrm{Ind}_2(x)\equiv 6\quad (\mathrm{mod}\:10)\tag{3}\]
 $(n,\:p-1)=(2,\:10)=2$ なので
 
\[(2,\:10)\:|\:\mathrm{Ind}_2(9)\]
という条件を満たすので、(2) は 2 個の解をもつはずです。(3) の両辺を $2$ で割ると、
 
\[\mathrm{Ind}_2(x)\equiv 3\quad (\mathrm{mod}\:5)\tag{4}\]
という合同方程式に帰着します。$\mathrm{mod}\:10$ の解は
 
\[\mathrm{Ind}_2(x)\equiv 3,\;8\quad (\mathrm{mod}\:10)\]
となります。指数表から対応する真数を探して
 
\[x\equiv 8,\;3\quad (\mathrm{mod}\:11)\]
という解が得られます。検算してみると
 
\[\begin{align*}
8^2&=64\equiv 9\quad (\mathrm{mod}\:11)\\[6pt]
3^2&=9\equiv 9\quad (\mathrm{mod}\:11)\end{align*}\]
となって、確かに合同方程式を満たしていることがわかります。
 

2 項合同方程式が解をもつ条件②

 定理 F4 を原始根を使わずに表現する方法もあります。

[定理 F5] $p$ を素数、$n$ を正整数とするとき、2 項合同方程式
\[x^n\equiv a\quad (\mathrm{mod}\:p)\]が解をもつための必要十分条件は
\[a^{\frac{p-1}{d}}\equiv 1\quad (\mathrm{mod}\:p)\] ただし、$d=(n,\:p-1)$ です。

[定理 F5 の証明] 定理 F4 より、2 項合同方程式
 
\[x^n\equiv a\quad (\mathrm{mod}\:p)\]
が解をもつための必要十分条件は
\[(n,\:p-1)\:|\:\mathrm{Ind}_g(a)\]
なので、
 
\[d\:|\:\mathrm{Ind}_g(a)\quad\Longleftrightarrow\quad a^{\frac{p-1}{d}}\]
を示せばよいことになります。まず $d\:|\:\mathrm{Ind}_g(a)$ が成り立っているとして、$\mathrm{Ind}_g(a)=kd\;(k\in\mathbb{Z})$ とおくと 原始根の定義 より
 
\[a\equiv g^{kd}\quad (\mathrm{mod}\:p)\]
と表せます。$d\:|\:p-1$ より $(p-1)/d$ は整数なので
 
\[a^{\frac{p-1}{d}}\equiv (g^{kd})^{\frac{p-1}{d}}=g^{k-1}=(g^{p-1})^k\equiv 1\quad (\mathrm{mod}\:p)\]
となります。今度は逆に

\[a^{\frac{p-1}{d}}\equiv 1\; (\mathrm{mod}\:p)\]
が成り立っているとすると、両辺の指数をとって
 
\[\frac{p-1}{d}\,\mathrm{Ind}_g(a)\equiv 0\quad (\mathrm{mod}\:p)\]
 $d=(n,\:p-1)$ なので $p-1=d\;(k\in\mathbb{Z})$ とおけて
 
\[l\,\mathrm{Ind}_g(a)\equiv 0\quad (\mathrm{mod}\:p)\]
 すなわち
 
\[\mathrm{Ind}_g(a)\equiv 0\quad (\mathrm{mod}\:p)\]
なので、$d\:|\:\mathrm{Ind}_g(a)$ が成立します。(証明終)

 [定理 F5] であれば指数表を用いる必要がないので、電卓さえあれば解の有無をすぐに調べることができます。先ほどの合同方程式
 
\[x^2\equiv 8\quad (\mathrm{mod}\:11)\tag{1}\]
に解が存在するかどうかを [定理 F5] で調べてみます。
 
\[\frac{p-1}{d}=\frac{10}{(2,\;10)}=5\]
となるので
 
\[a^{\frac{p-1}{d}}=8^5=32768\equiv 10\; (\mathrm{mod}\:11)\]
 $a^{\frac{p-1}{d}}\not\equiv 1$ なので解はありません。
 
\[x^2\equiv 9\quad (\mathrm{mod}\:11)\tag{2}\]
の場合は
 
\[a^{\frac{p-1}{d}}=9^{\frac{10}{2}}=9^5=59049\equiv 1\; (\mathrm{mod}\:11)\]
となるので、この合同方程式には 2 つの解が存在することになります。

 ≫ 平方剰余 ≫ 整数論入門講座

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

コメントをどうぞ

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