平成21年度 高度共通 午前I（PM試験） 問3

正解：イ

AI解説

ハッシュ値の衝突とはh（a）＝h（b），すなわちa mod n＝b mod n となること。a＝qn＋r，b＝q′n＋r（rは共通の余り）とおくと a−b＝（q−q′）n となり，a−bはnの倍数である。逆にa−bがnの倍数なら余りは等しい。よって衝突条件は「a−bがnの倍数」であり，これは合同式 a≡b（mod n）の定義そのものである。 ア: a＋bがnの倍数でも余りが等しいとは限らない。例えばn＝5，a＝2，b＝3ではa＋b＝5は5の倍数だがh（a）＝2，h（b）＝3で衝突しない。 イ: 正解。余りが等しいことと差が法nの倍数であることは同値である。 ウ: nがa＋bの倍数の反例：n＝6，a＝2，b＝4ではh（a）＝2，h（b）＝4で衝突しない。 エ: nがa−bの倍数の反例：n＝6，a＝5，b＝2（a−b＝3，6は3の倍数ではないので厳密には条件を満たす例としてn＝3，a＝5，b＝2を考えてもh（a）＝2，h（b）＝2とは限らず，一般には成立しない）。条件の向きが逆で，衝突を保証しない。 💡 「余りが等しい⇔差が割る数の倍数」はmod計算の基本性質。判断に迷ったら小さな具体値（n＝5など）を代入して検証するのが確実で速い。