合同式の除算練習

合同式の除算の計算ドリルです。
うまく活用してください。

割り算の仕方ロードマップ

step1. 出てくる数を全部簡単にする

$37\equiv 14,\ 47\equiv 1$であるため、$14x\equiv1\ (\text{mod}\ 23)$となる。

step2. 割りたい数が法と互いに素か確認する

$14\bot23$だからOK(ここでだめだったらそもそも方程式は解けない。)

step3. 係数で割った余りを考えて右辺を調整する

右辺に$23$を何個か足し引きして$14$の倍数にしたい。

$14x\equiv1\ (\text{mod}\ 23)$だったから、$1$に$23k$を足してどうにか$14$の倍数にしたい。つまり$1+23k\equiv0\ (\text{mod}\ 14)$となる$k$を求める。

step4. $k$を求めるためにstep1〜3を繰り返す

$23k\equiv-1\ (\text{mod}\ 14)$
$9k\equiv-1\ (\text{mod}\ 14)$
ここで右辺に$28$を加えたらうまくいくけれども、それが思いつかなかったらまた$k_1$をおく。右辺に$14k_1$を加えて$9$の倍数にしたいから、$-1+14k_1\equiv0\ (\text{mod}\ 9)$
$5k_1\equiv1\ (\text{mod}\ 9)$
係数が$5$以下ぐらいになったらもう見えるのでは。右辺に$9$を足して$5k_1\equiv10$
$5$で割って$k_1\equiv2\ (\text{mod}\ 9)$
補助的な方程式は$k_1=2$と、いちばん簡単な値を適当に取ってきていい。
よって、$9k\equiv-1\ (\text{mod}\ 14)$の右辺には、$14$を$k_1(=2)$個加えればうまくでき、つまり右辺に$28$を足すと$9k\equiv27\ (\text{mod}\ 14)$
$9$で割って$k\equiv3\ (\text{mod}\ 14)$
これも補助的な方程式だから$k=3$とする。

step5 こんな感じで$x$を求める

$14x\equiv1\ (\text{mod}\ 23)$の右辺に$23$を$k(=3)$個加えると$14x\equiv70\ (\text{mod}\ 23)$
$14$で割って$x\equiv5\ (\text{mod}\ 23)$

解くときの書き方

では、もう一問だけやってみよう。

あ、これは互いに素じゃないのでだめですね。解けないです。別の問題にしましょう。

step1. 出てくる数を全部簡単にする

もう簡単になってる

step2. 割りたい数が法と互いに素か確認する

大丈夫

step3. 係数で割った余りを考えて右辺を調整する

$1(\equiv15)$に$3(\equiv17)$を何個足したらいいだろう..
とりあえず$2$個足したら$14$じゃないけど$7$で割れるな。
右辺に$17\cdot2$を足そう。
$14x\equiv15+34$
$2x\equiv7\ (\text{mod}\ 17)$
右辺にもう一回$17$足せば終わるな
$2x\equiv24$
$x\equiv12\ (\text{mod}\ 17)$

こんな感じで、$7$で割った後に$2$で割る、みたいなことをしてもよい。困難は分割せよ。

練習問題

てきとーな数値設定にしたら簡単になりすぎてしまった。

自主的にたくさん練習してみよう！