合同式の方程式の解き方

こんにちは、リンス(@Lins016)です。
今回は合同式の方程式の解き方について学習していこう。

合同式の方程式

合同式の方程式は取り扱わない学校もあると思うけど、問題集とかには一応発展や補足的なところに載ってるよね。

テストに出ないかもしれないけど、そんなに難しいわけじゃないから、合同式の理解を深めるために考えてみよう。

合同式の方程式の答え方

まずはじめに合同式の方程式とその答え方について話をするね。

今回学習する合同式の方程式っていうのは
\(\small{ \ 4x \equiv 3 \pmod 5 \ }\)のような\(\small{ \ ax \equiv b \pmod m \ }\)の形の方程式。

方程式っていうと\(\small{ \ x=2 \ }\)みたいに\(\small{ \ x \ }\)の解を求めるって言うのが基本だよね。
でも合同式は余りに注目した式だから、\(\small{ \ x=2 \ }\)みたいに\(\small{ \ 1 \ }\)つの解が求まるんじゃなくて、\(\small{ \ x \equiv 2 \pmod 5 \ }\)みたいな解の形になるんだ。つまりこの場合\(\small{ \ x \ }\)は\(\small{ \ 5 \ }\)で割って\(\small{ \ 2 \ }\)余る数ってことね。

つまり\(\small{ \ ax \equiv b \pmod m \ }\)から\(\small{ \ x \equiv p \pmod m \ }\)を求めるっていうのが解法になるんだ。

でも実は\(\small{ \ ax \equiv b \pmod m \ }\)の形にもいくつかパターンがあって、その形に合わせて解き方を変えていくんだ。
\(\small{ \ 3 \ }\)つのパターンがあるから、確実に押さえていこう。

合同式の方程式の解き方①

最初のパターンは\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ a \ }\)と\(\small{ \ m \ }\)が互いに素の場合ね。

さっき挙げた\(\small{ \ 4x \equiv 3 \pmod 5 \ }\)もこの形だよね。それじゃこれを考えてみよう。
\(\small{ \ \pmod 5 \ }\)っていうのは\(\small{ \ 5 \ }\)で割った余りについて考えるわけだから、\(\small{ \ 5 \ }\)で割った余りは\(\small{ \ 0, \ 1, \ 2, \ 3, \ 4 \ }\)に分類できるよね。

\(\small{ \ \begin{array}{c|ccccc}
x & 0 & 1 & 2 & 3 & 4 \\
\hline
4x & 0 & 4 & 8\equiv3 & 12\equiv2 & 16\equiv1
\end{array} \ }\)

だから\(\small{ \ 4x \equiv 3 \pmod 5 \ }\)を満たすのは\(\small{ \ x \equiv 2 \pmod 5 \ }\) って言えるよね。
余りの分類がそう多くない式だったらこれで問題ないけど、余りの分類が多い次の式を見てみよう。

\(\small{ \ 8x \equiv 4 \pmod 9 \ }\)
これをさっきと同じ解き方をすると

だから\(\small{ \ 8x \equiv 4 \pmod 9 \ }\)を満たすのは\(\small{ \ x \equiv 5 \pmod 9 \ }\)って言えるよね。

でもさっきより余りの分類が多くて大変だったよね。だから余りの分類が多いときは違う方法で解いてみよう。

\(\small{ \ ax \equiv b \pmod m \ }\)と解く場合、\(\small{ \ ak \equiv 1 \pmod m \ }\)を満たす\(\small{ \ k \ }\)を見つけよう。この\(\small{ \ m \ }\)で割った余りが\(\small{ \ 1 \ }\)になるっていうのがポイントだからね。

\(\small{ \ 8x \equiv 4 \pmod 9 \ }\)の場合は、\(\small{ \ 8\times8 \equiv 1 \pmod 9 \ }\)になるから、
\(\small{ \ 8x \equiv 4 \pmod 9 \ }\)の両辺を\(\small{ \ 8 \ }\)倍して
\(\small{ \ 64x \equiv 32 \pmod 9 \ }\)
ここで \(\small{ \ 64x \equiv 1\times x \pmod 9 \ }\)、\(\small{ \ 32 \equiv 5 \pmod 9 \ }\)より
\(\small{ \ x \equiv 5 \pmod 9 \ }\)になるよね。

実はこの解き方って表を書いて\(\small{ \ 9 \ }\)で割って\(\small{ \ 1 \ }\)余るのを調べるのと、手間はそんなに変わらないんだけど、全部書く必要がないからこっちのほうが楽だよね。

この解き方を確実に押さえておこう。

\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ a \ }\)と\(\small{ \ m \ }\)が互いに素のとき、\(\small{ \ ak \equiv 1 \pmod m \ }\)を満たす\(\small{ \ k \ }\)は\(\small{ \ 1 \ }\)〜\(\small{ \ m-1 \ }\)の中にただ一つしかないんだ。上に書いた\(\small{ \ 2 \ }\)つの表を見ても、\(\small{ \ x \ }\)を\(\small{ \ 4 \ }\)倍や\(\small{ \ 8 \ }\)倍したものの余りの数も必ず\(\small{ \ 1 \ }\)通りしか存在していない、つまり余りの数がタブって重なるものは\(\small{ \ 1 \ }\)つもないんだ。このことから\(\small{ \ a \ }\)と\(\small{ \ m \ }\)が互いに素のとき、\(\small{ \ \mathrm{mod} \ m \ }\)でただ\(\small{ \ 1 \ }\)つの解を持つことになるからね。

合同式の方程式の解き方②

次に\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ a \ }\)と\(\small{ \ m \ }\)の最大公約数\(\small{ \ d \ }\)が\(\small{ \ d\gt1 \ }\)で\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れるときについて考えていこう。

文字で言われてもピンとこないけど
\(\small{ \ 3x \equiv 12 \pmod {15} \ }\)のような問題ね。全部の数字が\(\small{ \ 3 \ }\)と\(\small{ \ 15 \ }\)の最大公約数\(\small{ \ 3 \ }\)で割れる場合ね。

\(\small{ \ 3x \equiv 12 \pmod {15} \ }\)って\(\small{ \ 3x-12\equiv 0 \pmod {15} \ }\)のことだから、\(\small{ \ 3x-12=15k \ }\)（\(\small{ \ k \ }\)は整数）って書くことができるよね。
この両辺を\(\small{ \ 3 \ }\)で割ると\(\small{ \ x-4=5k \ }\)になるから、\(\small{ \ x=5k+4 \ }\)から\(\small{ \ x \equiv4 \pmod5 \ }\)が言えるよね。

ただ元の問題は\(\small{ \ 15 \ }\)で割った余りで分類してるから、これに合わせてみよう。
\(\small{ \ x \equiv4 \pmod5 \ }\)は\(\small{ \ 5 \ }\)で割ると\(\small{ \ 4 \ }\)余る数だから\(\small{ \ x=5k+4 \ }\)
ここからちょっと無理矢理だけど
\(\small{ \ x=5k+4, \ 5l+5+4, \ 5n+10+4 \ }\)
\(\small{ \ x=5k+4, \ 5l+9, \ 5n+14 \ }\)
\(\small{ \ x=15k'+4, \ 15l'+9, \ 15n'+14 \ }\)
って変形することができるよね。
ちなみにこの\(\small{ \ +4, \ +9, \ +14 \ }\)の部分は\(\small{ \ 15 \ }\)未満の数だからね。

だからこれから求める答えは
\(\small{ \ x \equiv4 \pmod{15} \ }\)
\(\small{ \ x \equiv9 \pmod{15} \ }\)
\(\small{ \ x \equiv14 \pmod{15}\ }\)
になるんだ。

ちなみにこの\(\small{ \ 3 \ }\)つの答えをまとめて\(\small{ \ x \equiv4, \ 9, \ 14 \pmod{15} \ }\)って書くからね。

これから一般的に\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ d\gt1 \ }\)、\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れるとき、\(\small{ \ \mathrm{mod} \ \displaystyle\frac{m}{d} \ }\)だと\(\small{ \ 1 \ }\)つの解を持って、\(\small{ \ \mathrm{mod} \ m \ }\)で\(\small{ \ d \ }\)個の解を持つって言えるんだ。

合同式の方程式の解き方③

最後に\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ a \ }\)と\(\small{ \ m \ }\)の最大公約数\(\small{ \ d \ }\)が\(\small{ \ d\gt1 \ }\)で\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れないときについて考えていこう。

つまり\(\small{ \ 3x \equiv 5 \pmod {15} \ }\)のような問題ね。
これって\(\small{ \ 3x-5 \equiv 0 \pmod {15} \ }\)になるから、\(\small{ \ 3x-5=15k \ }\)（\(\small{ \ k \ }\)は整数）になるよね。

ただ右辺は\(\small{ \ 3 \ }\)の倍数だけど、左辺は\(\small{ \ 3 \ }\)の倍数じゃないよね。だからこの式は成り立たないんだ。つまり解がないってこと。

さっきの合同式の方程式の解き方②と違うのは\(\small{ \ 3x \equiv 5 \pmod {15} \ }\)の\(\small{ \ 5 \ }\)が\(\small{ \ 3 \ }\)と\(\small{ \ 15 \ }\)の最大公約数で割れないってところだよね。割れるなら\(\small{ \ 3x-5=15k \ }\)の右辺も左辺も\(\small{ \ 3 \ }\)の倍数になるはずだからね。

だから一般的に\(\small{ \ ax \equiv b \pmod m \ }\)の\(\small{ \ d\gt1 \ }\)、\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れないとき、この方程式は解を持たないってことになるからね。

それぞれのパターンに合わせて問題を解こう。

(3)の問題は正攻法だと計算が多すぎるから少し工夫して解こう。あと(4)みたいな\(\small{ \ x \equiv a \pmod m \ }\)の\(\small{ \ m \ }\)より\(\small{ \ a \ }\)が大きい場合は小さくしてから問題を考えよう。

合同式の性質を理解した上で計算式を変形して答えを求めよう。

Point 合同式の方程式の解き方

①合同式の性質を押さえた上で計算式を理解する
②\(\small{ \ 3 \ }\)つのパターンの解き方を確実に押さえる