令和4年度 高度共通 午前I（PM試験） 問3

正解：イ

AI解説

ハッシュ値の衝突とは、異なるキーa,bに対してh(a)＝h(b)となることである。h(x)＝x mod nなので、a mod n＝b mod n、すなわちaとbをnで割った余りが等しいことが条件となる。これは(a−b) mod n＝0、つまりa−bがnの倍数であることと同値である。したがってイが正しい。 ア: a＋bがnの倍数でも余りが等しいとは限らない。例えばn＝5でa＝2,b＝3ならa＋b＝5は5の倍数だが、余りは2と3で衝突しない。 イ: 正しい。余りが等しい⇔差がnで割り切れる(合同式 a≡b (mod n) の定義)である。 ウ: nがa＋bの倍数という条件は余りの一致と無関係である。 エ: nがa−bの倍数の場合(例:n＝6,a−b＝3)、a−bがnで割り切れるとは限らず、余りが一致するとは言えない。 💡 「mod nで衝突=差がnの倍数」は合同式の基本。具体的な小さい数(n=5など)を代入して選択肢を検証すると確実である。