一次合同式を解く２つの方法と、解けるための条件

前回、時計の文字盤と同じ考え方で、合同式の世界を理解した。

次に、合同式の世界における四則演算について確認した。

じゃ、次は？

次に何をしらべよう？

→方程式を調べてみないか？？

$2x\equiv 1 (\mod 5)$解ける

$2x \equiv 1 (\mod 4)$解けない

何が違う？？

一次合同式とは？

今回は一次合同式について学んでいきます。

我々が普段使っている数の世界では、

これはそう難しい問題ではありませんでした。

例えば、

$2x=1$

を解いてみましょう。

両辺を$2$で割って、

$x=\dfrac{1}{2}$

です。

そりゃそうです。

中学1年生で習って以来親しんできた一次方程式そのままですから。

しかし、合同式の世界でこれをしようとすると、

途端に状況が複雑になります。

例えば、

$2x \equiv 1 (\mod 5)$

を解いてみましょう。

…

困りませんか？

さっきのように両辺を$2$で割ろうにも、

$\dfrac{1}{2}$は整数ではありません。

合同式の世界では、

割った余りが等しい数たちを扱っています。

余りが分数になることはないので、

合同式の世界では分数を扱うことはできないのです。

では、どうするか？？

答えは、シンプル。

ちょっと原始的ですけど、

代入作戦です！

$2x \equiv 1 (\mod 5)$

は、５で割った余りの世界です。

整数を５で割った余りは、０，１，２，３，４

しかありません。

なので、$x$に０，１，２，３，４を順番に代入していけば

いつかは答えにたどり着くはず。

試してみましょう。

$2x \equiv 1(\mod 5)$

に$x=0$を代入しましょう。

$2x=2×0=0$

これは１と合同になりようがありません。駄目です。

次に$x=1$を代入しましょう

$2x=2×1=2$

２は１と合同ではありません。

次です。$x=3$ならどうだ！！

$2x=2×3=6 \equiv 1 (\mod 5)$

これです！！

答えは見つかりましたが、折角なので$x=4$もやるだけやっておきますか

$2x=2×4=8 \equiv 3(\mod 5)$

以上のことから、

$2x\equiv 1 (\mod 5)$

を満たす整数$x$は、

$x=3$

でした！！

このことから、$\mod 5$の世界では、

$3$が$\dfrac{1}{2}$と同じような働きをすると解釈できます。

（ちょっと難しい言葉を使うなら、$\mod 5$　の世界では、２の逆元は３ということです。）

代入作戦を頑張れば、面倒ではあるものの、一応答えは求まりそうです。

本当にそうでしょうか？？

少しだけ条件を変えて一次合同式を観察しなおしてみましょう。

例えば、

$2x \equiv 1 (\mod 4)$

を解いてみましょう。

整数を４で割った余りは０，１，２，３です。

$x=0$を代入してみましょう

$2x=2×0=0$

駄目です。次です。$x=1$

$2×1=2$

駄目です。次！　$x=2$

$2x=2×2=4 \equiv 0 (\mod 4)$

駄目か…　なら$x=3$だ！！

$2x=2×3=6 \equiv 2 (\mod 5)$

あれ！？

$2x \equiv 1 (\mod 4)$

って、解が存在しなくない？

そうなんです。

一次合同式は、解が存在する場合と、存在しない場合があります。

いつでもできるわけではないわけです。

では、解ける場合と解けない場合の違いはなんでしょう？

それに、例えば

$3x \equiv 1 (\mod 100)$

とかを考えだしたら、代入作戦では限界があります。

そこで、合同式の割り算の時のルールを参考に、

もう少し考えを深めていきましょう！

キーワードは、「互いに素」です

一次合同式のはどんなとき解けるのか？

先ほどは代入作戦で方程式を解いていきましたが、このやり方は$\mod n$の$n$の値が大きいとき大変でした。

そこで、脳筋代入作戦ではなく、合同式本来がもつ性質に着目していく必要があります。

$2x\equiv 5 (\mod 7)$

を解いてみましょう。

合同式の別表現として、差が$\mod n$の$n$の数の倍数になっている、というものがありました

すなわち、

$2x-5=7k$　$(kは整数)$

これを変形すると、

$2x-7k=5$

となります。

これ、どこかで見たことありませんか？

一次不定方程式です！！

途中経過は省略しますが、

$2x-7k=5$

を解くと、$x=7m-15, k=2m-5$　$(mは整数)$です。

$x=7m-15$を　$\mod 7$で考えましょう。

ちょっと途中式を書きすぎかもしれませんが、ご容赦を。

$x=7m-15 \equiv 0×m-15 \equiv -15 \equiv -15+0 \equiv -15+7 $

$\equiv -8+0 \equiv -8+7 \equiv -1+0 \equiv -1+7 \equiv 6 (\mod 7)$

つまり、$2x \equiv 5 (\mod 7)$

の解は、$x \equiv 6 (\mod 7)$ となります！

できました！！

解いて見て分かったこと。

合同式の方程式が解けるための条件は、一時不定方程式が解ける条件と一致する

ここで、大活躍した一次不定方程式についておさらいしましょう。

一次不定方程式

$ax+by=c$

が解けるための条件は何でしたか？

それは、$c$が$a$と$b$の最大公約数の倍数であること

つまり、

$ax=b (\mod k)$

が解けるための条件は、

$b$が$a$と$k$の最大公約数の倍数であること、

となります。

ちょっと難しい記号を使うと、

$b$が$GCD(a, k)$の倍数であること、となります。

証明

～脳内会議～

素直に先ほどの一次不定方程式の話を持ち出していきましょう。

まとめ

いかがでしたか？

・$ax\equiv b (\mod k)$は一応代入作戦で脳筋すれば解ける

・$ax\equiv b (\mod k)$を解くことは本質的にはに１次不定方程式を解くことと同じ

・ゆえに、解けるための条件も１次不定方程式と同じ

この３点を抑えていただければと思います

ではまた次の記事でお会いしましょう！