１次合同式を解く - Ex8.5 - パンの木を植えて

おはようございます．

作業用BGMをiPhoneに取り込んでいたのですが，iMacと同期したら全部消えてしまいました．

かなしいね．なぜAppleはCDから音楽取り込むひとびとを迫害するのか．

今回はシルヴァーマンの続きを読んでいきます．

今回の問題は合同式のやつです．

問8.5

以下の合同式に対して，互いに合同ではない解をすべて求めよ．

(a) $8x \equiv 6 \mod 14$

(b) $66x \equiv 100 \mod 121$

まず(a)からいきましょう．

$8x \equiv 6 \mod 14$ というのは，$8x-6 = 2(4x-3)$ が $14$ で割り切れるということを主張しています．$14=2 \times 7$ なので，$4x-3$ が $7$ で割り切れることと同値です．

つまり，法を変えて $4x \equiv 3 \mod 7$ と同値になります．

このようにして法と１次の係数が互いに素になるところまで持っていければこっちのものです．

$4$ は $7$ と互いに素なので，法 $7$ で割ることができます．この場合 $4^{-1} = 2$ ですね．

したがって両辺に $2$ を乗じて $x \equiv 6 \mod 7$ です．

元の問題では法は $14$ だったので戻すと，解は $x \equiv 6, 13 \mod 14$ ですね．

(b) 以降もすべて同様です．ノートを貼って済ませてしまいましょう．

１次の係数と法が互いに素になるようにして，あとは割るだけ．

ただし，解が存在しないこともありますので，それは要注意です．

これだけだとつまらないので，計算機に検算をしてもらいましょう．

ちょうど次の次あたりの問題で多少賢いアルゴリズムを実装するという話があるので，思いっきり頭のわるいアルゴリズムを組んでみましょう．

いつかの記事で書いたと思いますが，私は Anaconda を使って VSCode 上で JupyterNotebook に働いてもらっています．

こんなコードを書きました．

ちゃんとpythonコードも書くとこんな感じです．

# １次の合同式を解く全探索
## 入力
a = 8
c = 6
m = 14
## 手続き
for i in range(0,m):
    if (a*i - c ) % m == 0:
        print(i)

これをjupyterに計算していただくことにより，検算をしました．ちゃんと動いて嬉しいです．

でも，解がないときに「解がありません」と答えるようにした方が良かったかもしれません．それをするには，Forループを回しながらif文が真になった回数を数えて，その回数がゼロだったら「解はありません」と返すようにすればいいですね．