合同方程式、計算のコツ
$a$ と $m$ を互いに素である自然数とする。
合同方程式 $ax \equiv b \pmod{m}$ を解くときは、両辺を何倍かしてうまいこと $x$ の係数を $1$ にしなければならないが、工夫の仕方によっては楽に解けることも多い。
このページでは計算の工夫をいくつか紹介してみることにする。
【工夫その１】
$ax \equiv b \pmod{m}$ において、$a$ と $m$ が十分近い場合は、$a$ を $a-m$ に変えてみよう。
【例題】
合同方程式 $12x \equiv 2 \pmod{13}$ を解け。
【解法】
次のように計算する。
\[ \begin{aligned}
12x &\equiv 2 \pmod{13} \\
-x &\equiv 2 \pmod{13} \\
x &\equiv -2 \pmod{13} \\
x &\equiv 11 \pmod{13}
\end{aligned} \]
【例題】
合同方程式 $11x \equiv 3 \pmod{13}$ を解け。
【解法】
次のように計算する。
\[ \begin{aligned}
11x &\equiv 3 \pmod{13} \\
-2x &\equiv 3 \pmod{13} \\
2x &\equiv -3 \pmod{13}
\end{aligned} \]
（$x$ の係数が $2$ になったので問題が簡単になっている。）両辺を7倍して
\[ \begin{aligned}
14x &\equiv -21 \pmod{13} \\
x &\equiv -21 \pmod{13} \\
x &\equiv 5 \pmod{13}
\end{aligned} \]
【工夫その２】
$ax \equiv b \pmod{m}$ の両辺を適当に何倍かして、$x$ の係数を現状の $a$ より小さくする。
【例題】
合同方程式 $7x \equiv 3 \pmod{19}$ を解け。
【解法】
まず、両辺を3倍してみると
\[ \begin{aligned}
21x &\equiv 9 \pmod{19} \\
2x &\equiv 9 \pmod{19} \\
\end{aligned} \]
である。（$x$ の係数が $2$ になったので最初の問題よりは簡単になっている。）さらに両辺を10倍して
\[ \begin{aligned}
20x &\equiv 90 \pmod{19} \\
x &\equiv 90 \pmod{19} \\
x &\equiv 14 \pmod{19}
\end{aligned} \]
【例題】
合同方程式 $13x \equiv 17 \pmod{23}$ を解け。
【解法】
まず、両辺を2倍してみると
\[ \begin{aligned}
26x &\equiv 34 \pmod{23} \\
3x &\equiv 11 \pmod{23} \\
\end{aligned} \]
である。（$x$ の係数が $3$ になったので最初の問題よりは簡単になっている。）さらに両辺を8倍して
\[ \begin{aligned}
24x &\equiv 88 \pmod{23} \\
x &\equiv 19 \pmod{23}
\end{aligned} \]