合同式を使いこなせるようになりたいけど、いまいちよく分からないよ。分かりやすく書かれたテキストもないし。一次合同式ってどうやって解けばいいの？
こんな悩みを解決していきます。
✔︎本記事の内容
１．合同式の基本を押さえましょう
２．合同式の性質
３．テキストには書かれていないけど、みんな使っている式変形とは？
４．一次合同式の解き方４タイプ
ちなみにこの記事を書いている私は
- 数学講師歴２０年以上
- 大学院の応用数学を学ぶ。専門は情報幾何学。
- 数学検定１級取得済
ですが、私自身の数学検定１級合格の決め手となったのも、合同式を用いた整数問題でした。
合同式を使いこなせるようにしておくことは、大学受験や数学検定１級受検で必須です。
今回は\(23x\equiv 7 \pmod {41}\)のような、一次合同式の解き方を分かりやすく解説していきます。
合同式の基本を押さえましょう
「\(a\)を\(m\)で割った余り」と「\(b\)を\(m\)で割った余り」が等しいことを
\begin{equation}
\qquad\qquad a\equiv b \pmod m
\end{equation}
と書き、「\(a\)と\(b\)は\(m\)を法として合同である」といいます。
（例）23を5で割ったときの余りと、8を5で割ったときの余りは、ともに3で等しいので
\[ \qquad\qquad 23 \equiv 8 \pmod 5\]
と表します
合同式の性質
\(a \equiv b \pmod m, \;\; c \equiv d \pmod m \)のとき
\(１． a+c \equiv b+d \pmod m \)
\(２． a-c \equiv b-d \pmod m \)
\(３． ac \equiv bd \pmod m \)
\(４． a^n \equiv b^n \pmod m \;\;(nは自然数) \)
要するに、加法・減法・乗法については、等式の変形と同じ操作ができると考えてＯＫです。
ただし、原則として割り算はできません。合同式の両辺を割ってもいい場合は、ある条件が満たされたときだけです。今回の解説では、割り算を使わないようにしますのでご安心ください。
テキストには書かれていないけど、みんな使っている式変形
次の事実を知っておくと、合同式の計算が簡単になります。
具体例で解説しますね。
\[ 5x\equiv 0 \pmod 5\]
\(5x\)を5で割った余りは0なので、自明ですね。
次々に5を引くことができる
\[ 23\equiv 18 \equiv 13 \equiv 8 \equiv 3 \pmod 5\]
\(23\)は\(23=18+5\)と変形できます。ここで現れた5を法としている5で割ると余りは0なので、\(23\equiv 13\)が成り立ちます。同様に\(18=13+5\)だから\(18\equiv 13\)となります。
つまり、\(\pmod 5\)の場合、5を次々に引いた数もすべて合同であるということなのです。もちろん、5を次々に足していっても大丈夫です。
次のような\(x\)を含む式であっても同じことがいえます。
\(x\)の係数から次々に5を引くことができる\[ 23x\equiv 18x \equiv 13x \equiv 8x \equiv 3x \pmod 5\]
\(23x=18x+5x\)と変形でき、ここで現れた\(5x\)を5で割った余りは0なので、\(23x \equiv 18x\)が成り立ちます。以下同様です。
つまり、\(\pmod 5\)の場合、\(23x\)の係数から\( 5\) を次々に引いたものもすべて合同であるということがいえます。
このような操作は合同式の変形で、頻繁に使いますので押さえておきましょう。
一次合同式の解き方４タイプ
一次合同式を解くときのポイント
\(x\)の係数が1になるような式変形をする
これだけです！
それでは、一次合同式の４つのタイプについて解説していきます。
タイプ１
問題１\begin{equation}
23x \equiv 4 \pmod 5 \cdots ①\end{equation}
まずは、やさしめの問題からスタートです。
\( 23\) を\( 5\) で割った商は\( 4\) ，余りは\( 3\) であるから
\[ (5\cdot 4 +3)x \equiv 4 \pmod 5 \]
左辺のカッコをはずしたときの現れる\(5\cdot 4x\)の項を、\( 5\) で割った余りは\( 0\) なので
\begin{equation}
3x \equiv 4 \pmod 5 \;\; \cdots ②
\end{equation}
となります。
ここで、①と②を連立方程式と同じような方法で式変形し、\(x\)の係数が1になるようにしていきます。
②を8倍すると
\begin{equation}
24x \equiv 32 \pmod 5 \cdots ③
\end{equation}
③から①を引いて
\begin{equation}
x \equiv 28 \pmod 5
\end{equation}
さらに\( 28 =5\cdot 5+3\)から，\(28 \equiv 3 \pmod 5\)となるので
\begin{equation}
x \equiv 3 \pmod 5 \cdots ④
\end{equation}
これが答えです。
④は
「\(x\)を5で割った余りは3を5で割った余りに等しい」
ということを意味しており、ここから
「\(x\)を5で割った余りは3である」ことが分かります。
したがって、\(x \)は整数\(k\)を用いて
\[ x=5k+3 \]
と表すことができます。
タイプ２
31x \equiv 19 \pmod 7 \cdots ①\end{equation}
問題１と同じ変形をしていきますが、今回は右辺にも手を加えます。
\[ (7\cdot 4 +3)x \equiv 7\cdot 2+5 \pmod 7 \]
よって
\begin{equation}
3x \equiv 5 \pmod 7 \cdots ②
\end{equation}
となります。
②を\( 10\) 倍すると
\begin{equation}
30x \equiv 50 \pmod 7 \cdots ③
\end{equation}
①から③を引いて
\begin{equation}
x \equiv -31 \pmod 7
\end{equation}
右辺を正の数にしておきたいので、\( 7\) の倍数を右辺に加えます。
右辺はできるだけ小さい正の整数にしておきたいので、次のようにします。
\begin{equation}
x \equiv -31+7\cdot 5 \pmod 7
\end{equation}
これより
\begin{equation}
x \equiv 4 \pmod 7
\end{equation}
これが答えです。\(x\)を具体的に表すと
\(x=7k+4\;\;(kは整数)\)
となりますね。
タイプ３
問題３
\begin{equation}
30x \equiv 1 \pmod 7 \cdots ①
\end{equation}
問題１とほぼ同じですが、少し工夫が必要です。
\[ (7\cdot 4 +2)x \equiv 1 \pmod 7 \]
これより
\begin{equation}
2x \equiv 1 \pmod 7 \cdots ②
\end{equation}
となります。
ここで、問題１のように、①と②を用いて、\(x\)の係数を1にしたいのですが、上手くいきません。
例えば②の式を15倍すると\(30x\equiv 15\)で①からこの式を引くと\(x\)が消えてしまいます。
②を16倍すると\(32x \equiv 16\)ですが、この式から①を引いても\(2x\equiv -15\)で、\(x\)の係数が1になりません。
そこで先ほど紹介した方法を使ってみましょう。
\(x\)の係数から次々に5を引くことができる\[ 23x\equiv 18x \equiv 13x \equiv 8x \equiv 3x \pmod 5\]
この例と同様に、②の左辺を7だけずらします。
\begin{equation}
9x \equiv 1 \pmod 7 \cdots ③
\end{equation}
あとは、②と③を連立させて\(x\)の係数が\( １\) になるように変形していきます。
②×4から
\begin{equation}
8x \equiv 4 \pmod 7 \cdots ④
\end{equation}
③から④を引いて
\begin{equation}
x \equiv -3 \pmod 7 \cdots ④
\end{equation}
\begin{equation}
x \equiv -3 +7 \equiv 4 \pmod 7
\end{equation}
\(\pmod 7\)の\( 7\) だけずらした式を２つ用意しておくことで、答えを求めることができました。
タイプ４
問題４
\begin{equation}
23x \equiv 7 \pmod {41} \cdots ①
\end{equation}
最後は\(\pmod {41}\)の41が\(x,\;\;y\)の係数\( 7\) より大きい場合です。
いくつかやり方はありますが、次のようにしてみます。
①の両辺を2倍すると
\begin{equation}
46x \equiv 14 \pmod {41} \cdots ②
\end{equation}
\begin{equation}
(41\cdot 1+5)x \equiv 14 \pmod {41}
\end{equation}
よって
\begin{equation}
5x \equiv 14 \pmod {41}
\end{equation}
両辺を9倍して
\begin{equation}
45x \equiv 126 \pmod {41} \cdots ③
\end{equation}
②から③を引いて
\[ x \equiv -112 \pmod {41} \]
右辺に41の3倍を加えて
\[ x \equiv -112+43\cdot 3 \pmod {41} \]
よって
\[ x \equiv 11 \pmod {41} \]
まとめ
今回は一次合同式の解き方について解説しました。
ポイントは\(x\)の係数が1になるように、２つの式を連立させることです。
一次合同式にはもっと面倒なタイプもありますが、大学入試や数学検定１級のレベルであれば、今回のタイプを学んでおけば十分だと思います。
実際に、数学検定１級でよく出題される、連立合同式も今回ご紹介した解法を組み合わせていくだけです。
次の本では１次合同式のやや難しい問題や２次合同式も扱っていますので参考にしてみてください。
※タイトルは「線形代数」ですが、最初に合同式の内容が掲載されています
合同式は慣れてしまえば簡単です。
今回ご紹介した方法を参考にして、合同式の式変形が自然にできるようにたくさん練習してみてください。
この機会に、合同式を得意分野にしてしまいましょう！
最後までお読みいただき、ありがとうございました。
