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

正解：イ

AI解説

正解はイ。ハッシュ値が衝突するのはh(a)=h(b)、すなわちaをnで割った余りとbをnで割った余りが等しいときである。余りが等しいことは差a−bがnで割り切れること(a−bがnの倍数)と同値である。合同式でa≡b (mod n)と表される関係である。 ア: a+bがnの倍数でも余りが等しいとは限らない。例えばn=5でa=2,b=3ならa+b=5は倍数だがh(a)=2,h(b)=3で衝突しない。 イ: 正解。a mod n=b mod n ⇔ a−bがnの倍数、という剰余の基本性質そのものである。 ウ: nがa+bの倍数という条件は余りの一致と無関係である。 エ: nがa−bの倍数の場合、a−bがn未満なら成立するのはa=bのときだけであり、一般の衝突条件ではない。 💡 「余りが等しい⇔差が割り切れる」は合同式の基本。迷ったら小さな具体数(n=5など)を各肢に代入して反例を探すと確実に絞り込める。