【数検1級対策】連立一次合同式の解法

本記事では，数学検定1級で頻出の連立一次合同式の解法についてまとめていきます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

連立一次合同式の解法

具体例

\begin{cases}
12x \equiv 28 \pmod{32}\\[0.7em]
5x \equiv 9 \pmod{13}
\end{cases}

解答

まず，$12x\equiv 28\pmod{32}$を解きます。$12,28,32$の最大公約数は$4$であることに注意すると，合同式の性質のうち商に関する性質を利用して，$4$と$32$が互いに素でないことから

となります。すると，与えられた連立一次合同式は

\begin{cases}
3x \equiv 7 \pmod 8\\[0.7em]
5x \equiv 9 \pmod{13}
\end{cases}

となります。ここで，一般に$a\equiv b\pmod{p}$のとき$ac\equiv bc\pmod{pc}$としてもよいことに注意すると，法を揃えることができ，

\begin{cases}
39x \equiv 91 \pmod{104}\\[0.7em]
40x \equiv 72 \pmod{104}
\end{cases}

となります。したがって，$x \equiv 85 \pmod{104}$が得られます。

連立一次合同式のそれぞれを「$x\equiv$」に変形して別の変数$k$を持ち出して計算する方法もありますが，最後に法を揃える際の議論が分かりにくいです。最初に法を揃えることによりシンプルに解くことができるためオススメです。