5 ÷ 3 × 6 を求める
こんにちは、かくまいです。
突然ですが、あなたは5 ÷ 3 × 6 が計算できますか…?
…
…
はい、10です。
簡単でしたね。
しかし電卓でこの問題を解くのは少し厄介です。
性能が低い場合
5 ÷ 3 = 1.66666666....
1.66666666... × 6 = 9.99999999......
となり誤差が発生するからです。(*1)
今回は分数、小数、並び替えを使わずこれを計算したいと思います
具体的には
5 ÷ 3 × 6の代わりに 5 ÷ 3 × 6を 17で割った余りを計算する事にします
元の答えは17未満なので、どちらも同じ値になるはずです
ここで5を3で割った余りと 2を3で割った余りは等しいというのを
5 ≡ 2 (mod 3)
のように書きます
5 ÷ 3 × 6 ≡ X (mod 17)
を満たす最小のXが求めたい答えです
ところで、実はmod 17上で「÷3」は「×6」と同じ意味になります
これは3の逆元（掛けると1になる物）が6であるという事です
実際、式に起こしてみると
1/3 ≡ 6 (mod 17)
となりますが、両辺に3を掛けると
1 ≡ 3 × 6 (mod 17)
となるため、正しそうです
上の結果を利用して計算してみると
5 ÷ 3 × 6 ≡ X (mod 17)
⇔ 5 × 6 × 6 ≡ X (mod 17)
⇔ 180 ≡ X (mod 17)
より180を17で割った余りは10なので 5 ÷ 3 × 6 = 10と一致していることが分かります
------------------------------------------------------------
*1
2進数では表現できない小数があるため、限りなく近い数は扱えても数が大きいときは誤差が出る
