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

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

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

[証明] $x^n\equiv a$ の両辺の指数をとると
$$n{\mathrm{Ind}}_g(x)\equiv {\mathrm{Ind}}_g(a)(\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)$ 個の解をもちます。（証明終）

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

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

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

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

[証明] 定理 F4 より、2 項合同方程式
$$x^n\equiv a(\mathrm{mod}p)$$
が解をもつための必要十分条件は
$$(n,p-1)|{\mathrm{Ind}}_g(a)$$
なので、
$$d|{\mathrm{Ind}}_g(a)⟺a^{\frac{p-1}{d}}$$
を示せばよいことになります。まず $d|{\mathrm{Ind}}_g(a)$ が成り立っているとして、${\mathrm{Ind}}_g(a)=kd(k\in \mathbb{Z})$ とおくと原始根の定義より
$$a\equiv g^{kd}(\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(\mathrm{mod}p)$$
となります。今度は逆に
$$a^{\frac{p-1}{d}}\equiv 1(\mathrm{mod}p)$$
が成り立っているとすると、両辺の指数をとって
$$\frac{p-1}{d}{\mathrm{Ind}}_g(a)\equiv 0(\mathrm{mod}p)$$
$d=(n,p-1)$ なので $p-1=d(k\in \mathbb{Z})$ とおけて
$$l{\mathrm{Ind}}_g(a)\equiv 0(\mathrm{mod}p)$$
すなわち
$${\mathrm{Ind}}_g(a)\equiv 0(\mathrm{mod}p)$$
なので、$d|{\mathrm{Ind}}_g(a)$ が成立します。（証明終）

[定理F5] であれば指数表を用いる必要がないので、電卓さえあれば解の有無をすぐに調べることができます。先ほどの合同方程式
$$\begin{array}{}\text{(1)}& x^2\equiv 8(\mathrm{mod}11)\end{array}$$
に解が存在するかどうかを [定理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$ なので解はありません。
$$\begin{array}{}\text{(2)}& x^2\equiv 9(\mathrm{mod}11)\end{array}$$
の場合は
$$a^{\frac{p-1}{d}}=9^{\frac{10}{2}}=9^5=59049\equiv 1(\mathrm{mod}11)$$
となるので、この合同方程式には 2 つの解が存在することになります。

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