アルゴリズム論特論（塩田）第6回 (1) 法演算における除算とは？
割り算と除算の違い
何を今更、と思うかもしれませんが
問 11÷3 って何だ？？
解釈１ 3つに均等に割る
- 長さ 11cm の羊羹なら 11/3 cm に切り分ければ良し
- でも、11個の飴だと、そうはいかないよね
解釈２ 3人に分ける
- 11個の飴を、
- 3人にまず1個ずつ配る → まだ8個ある
- もう1個ずつ配る → まだ5個ある
- もう1個ずつ配る → まだ2個ある
- 2個余ったけど仕方ない
解釈１は均等に「割る」ので「割り算」、
解釈２は３個ずつ「除いてゆく」ので「除算」という感じがしませんか？
法演算で行うべきは割り算か除算か？
問 mod で 11 \div 3 って何だ？？
解釈１かな？
- 11 \equiv 4 \equiv -10 \pmod 7 なので、法演算では「大きさ」の概念がありません。
大きさの無いものを均等に割れ、と言われても困りますね。
解釈２かな？
- 11個の飴を、
- 3人にまず1個ずつ配る → まだ8個ある
- もう1個ずつ配る → まだ5個ある
- もう1個ずつ配る → まだ2個ある
- 2 \equiv 9 \pmod 7 なのでもう1個ずつ配れる → まだ6個ある
- もう1個ずつ配る → まだ3個ある
- もう1個ずつ配る → 丁度無くなった
結局 6個ずつ配ったので
11 \div 3 \equiv 6 \pmod 7
なのかな？
最後の式を見れば、確かに
6 \times 3 = 18 \equiv 11 \pmod 7
なので、正しいような気もします。ということは
x \times b \equiv a \pmod n
が成り立つときに
a \div b \equiv x \pmod n
ということにすればいいのでしょうか？