令和4年度 秋期 応用情報技術者 問5

正解 イ

a mod n＝b mod nとなるのは、aとbの差a−bがnで割り切れるとき、つまりnの倍数のときです。

衝突とは、異なるキーのハッシュ値が同じになることです。a＝qn＋r、b＝pn＋rのように余りrが等しいとき、h(a)＝h(b)になります。このときa−b＝(q−p)nとなり、a−bはnの倍数です。逆に、a−bがnの倍数なら、aとbをnで割った余りは等しくなります。例えばn＝5、a＝12、b＝7とすると、a−b＝5で、どちらも余りは2になります。

ア：和a＋bがnの倍数になるのは、余りの和が0またはnになるときです。余りが等しくなるとは限りません。例えばn＝5、a＝2、b＝3では、余りは2と3で異なります。

ウ：倍数の向きが逆です。例えばn＝6、a＝1、b＝2では、nはa＋b＝3の倍数ですが、余りは1と2で異なります。

エ：倍数の向きが逆です。nがa−bの倍数でも、a−bがnより小さければ余りは一致しません。例えばn＝4、a＝3、b＝1では、余りは3と1で異なります。

出典：令和4年度 秋期 応用情報技術者試験 問5