整数の性質

合同式の方程式の解き方

重要度 難易度

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

スポンサーリンク

合同式の方程式

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

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

合同式の方程式の解き方

\(\small{ \ ax \equiv b \pmod m \ }\)
ただし、\(\small{ \ ax \not\equiv 0 \pmod m \ }\)、\(\small{ \ a \ }\)と\(\small{ \ m \ }\)の最大公約数を\(\small{ \ d \ }\)とする
①\(\small{ \ d=1 \ }\)(\(\small{ \ a \ }\)と\(\small{ \ m \ }\)は互いに素)のとき
\(\small{ \ \mathrm{mod} \ m \ }\)でただ\(\small{ \ 1 \ }\)つの解を持つ

②\(\small{ \ d\gt1 \ }\)、\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れるとき
\(\small{ \ \mathrm{mod} \ \displaystyle\frac{m}{d} \ }\)でただ\(\small{ \ 1 \ }\)つの解を持つ
(\(\small{ \ \mathrm{mod} \ m \ }\)で\(\small{ \ d \ }\)個の解を持つ)

③\(\small{ \ d\gt1 \ }\)、\(\small{ \ b \ }\)が\(\small{ \ d \ }\)で割り切れないとき
解を持たない

合同式の方程式の答え方

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

今回学習する合同式の方程式っていうのは
\(\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{ \ \begin{array}{c|ccccccccc}
x & 0 & 1 & 2 & 3 & 4 & 5& 6& 7& 8\\
\hline
8x & 0 & 8 & 16\equiv7 & 24\equiv6 & 32\equiv5 & 40\equiv4 & 48\equiv3 & 56 \equiv 2& 64\equiv1
\end{array} \ }\)

だから\(\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 \ }\)余るのを調べるのと、手間はそんなに変わらないんだけど、全部書く必要がないからこっちのほうがだよね。

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

point
\(\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 \ }\)で割り切れないとき、この方程式は解を持たないってことになるからね。

例題を確認
問題解答

次の合同式を満たす\(\small{ \ x \ }\)をそれぞれ法\(\small{ \ m \ }\)において\(\small{ \ x \equiv a \pmod m \ }\)の形で表せ。ただし\(\small{ \ a \ }\)は\(\small{ \ m \ }\)より小さい自然数とする。
(1)\(\small{ \ 7x \equiv 3 \pmod 5 \ }\)
(2)\(\small{ \ 4x \equiv 8 \pmod {12} \ }\)
(3)\(\small{ \ 17x \equiv 3 \pmod {29} \ }\)
(4)\(\small{ \ 5x \equiv 15 \pmod {13} \ }\)

(1)\(\small{ \ 7x \equiv 3 \pmod 5 \ }\)
両辺を\(\small{ \ 3 \ }\)倍すると
\(\small{ \ 21x \equiv 9 \pmod 5 \ }\)
\(\small{ \ \therefore x \equiv 4 \pmod 5 \ }\)

(2)\(\small{ \ 4x \equiv 8 \pmod {12} \ }\)
\(\small{ \ 4x-8=12k \ }\)(\(\small{ \ k \ }\)は整数)
\(\small{ \ x-2=3k \ }\)
\(\small{ \ x \equiv 2 \pmod 3 \ }\)
\(\small{ \ \therefore x\equiv 2, \ 5, \ 8, \ 11 \pmod{12} \ }\)

(3)\(\small{ \ 17x \equiv 3 \pmod {29} \ }\)
両辺を\(\small{ \ 2 \ }\)倍すると
\(\small{ \ 34x \equiv 6 \pmod {29} \ }\)
\(\small{ \ 5x \equiv 6 \pmod {29} \ }\)
さらに両辺を\(\small{ \ 6 \ }\)倍して
\(\small{ \ 30x \equiv 36 \pmod {29} \ }\)
\(\small{ \ \therefore x \equiv 7 \pmod {29} \ }\)

(4)\(\small{ \ 5x \equiv 15 \pmod {13} \ }\)
\(\small{ \ 5x \equiv 2 \pmod {13} \ }\)
両辺を\(\small{ \ 8 \ }\)倍して
\(\small{ \ 40x \equiv 16 \pmod {13} \ }\)
\(\small{ \ \therefore x \equiv 3 \pmod {13} \ }\)

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

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

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

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

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

この記事が気に入ったら
いいね ! しよう

Twitter で

-整数の性質

-,

  • この記事を書いた人
  • 最新記事

リンス

名前:リンス
職業:塾講師/家庭教師
性別:男
趣味:料理・問題研究
好物:ビール・BBQ