2次合同方程式(3)
[ 例題 ] 次の合同方程式を解け。
\[ x^2 \equiv 4 \pmod{25} \]
[ 解法① ]
与えられた方程式を変形すると $(x-2)(x+2) \equiv 0 \pmod{25}$ となる。
よって、次の3通りが考えられる。
(i) $x-2 \equiv 0 \pmod{25}$
(ii) $x+2 \equiv 0 \pmod{25}$
(iii) $x-2 \equiv 0 \pmod{5}$ かつ $x+2 \equiv 0 \pmod{5}$
(i), (ii)より $x \equiv 2, 23 \pmod{25}$ が得られる。
一方、(iii) を満たす $x$ は存在しない。
以上より解は $x \equiv 2, 23 \pmod{25}$ である。
[ 解法② ]
合同式の法を $25$ とする。
解の候補は $x \equiv 0,1,2, \dots, 24$ である。
これらの候補のうち $x^2 \equiv 4$ を満たすものをしらみ潰しに探すと $x \equiv 2, 23$ のみが解であることが分かる。
以上より解は $x \equiv 2, 23 \pmod{25}$ である。
[1] 合同方程式 を解くと $x \equiv$ $\pmod{25}$ である。
[2] 合同方程式 を解くと $x \equiv$ $\pmod{25}$ である。
[3] 合同方程式 を解くと $x \equiv$ $\pmod{49}$ である。
[4] 合同方程式 を解くと $x \equiv$ $\pmod{49}$ である。
なお、[3][4]については次の表を参考にしてよい。
| $x$ |
$\cdots$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
$21$ |
$22$ |
$23$ |
$24$ |
| $x^2$ |
$\cdots$ |
$225$ |
$256$ |
$289$ |
$324$ |
$361$ |
$400$ |
$441$ |
$484$ |
$529$ |
$576$ |
| $x^2 \!\! \mod{49}$ |
$\cdots$ |
$29$ |
$11$ |
$44$ |
$30$ |
$18$ |
$8$ |
$0$ |
$43$ |
$39$ |
$37$ |
[ 補足 ]
言うまでもないかもしれないが、mod $49$ を計算するときは $49$ の倍数だけ数をずらすことになる。
そこで、$49 = 50 - 1$ に注目すると、次のような工夫が考えられる。
・ある数から $49$ を引く → $50$ を引いて $1$ を加える
・ある数から $98 \, (= 49 \times 2)$ を引く → $100$ を引いて $2$ を加える
・ある数から $147 \, (= 49 \times 3)$ を引く → $150$ を引いて $3$ を加える
このように計算すると、直接（筆算で） $49$ で割った余りを求めたり、直接（筆算で） $49$ の倍数を引き算したりするよりも、計算がずっと簡単になるはずである。