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

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

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

[証明] $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$ の指数表

を見ると $\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 を原始根を使わずに表現する方法もあります。

[証明] 定理 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 つの解が存在することになります。

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