平成25年度秋期 応用情報技術者試験 午前 問7

正解：イ

AI解説

正解はイ。ハッシュ値の衝突とは、異なるキーaとbが同じハッシュ値をもつこと、すなわち 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のとき和は5の倍数だが余りは2と3で異なる。 イ: 正しい。余りが等しい⇔差がnで割り切れる、という合同式の基本性質である。 ウ: nがa+bの倍数という条件は衝突とは無関係である。 エ: nがa−bの倍数では向きが逆である。a−bがnの倍数でなければならない。 💡 「余りが等しい⇔差が割り切れる」は合同式(a≡b mod n)の定義そのもの。具体的な数(n=5、a=7、b=12など)を代入して確認すると確実である。