アルゴリズム論特論(塩田)第6回 (1) 法演算における除算とは?

割り算と除算の違い

 何を今更、と思うかもしれませんが
 $11 \div 3$ って何だ??
解釈1 3つに均等に割る
  • 長さ 11cm の羊羹なら 11/3 cm に切り分ければ良し
  • でも、11個の飴だと、そうはいかないよね
解釈2 3人に分ける
  • 11個の飴を、
  • 3人にまず1個ずつ配る → まだ8個ある
  • もう1個ずつ配る → まだ5個ある
  • もう1個ずつ配る → まだ2個ある
  • 2個余ったけど仕方ない
 解釈1は均等に「割る」ので「割り算」、 解釈2は3個ずつ「除いてゆく」ので「除算」という感じがしませんか?

法演算で行うべきは割り算か除算か?

 $\bmod 7$ で $11 \div 3$ って何だ??
解釈1かな?
  • $11 \equiv 4 \equiv -10 \pmod 7$ なので、法演算では「大きさ」の概念がありません。 大きさの無いものを均等に割れ、と言われても困りますね。
解釈2かな? 
  • 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$
ということにすればいいのでしょうか?