問27応用情報技術者 平成30年度 秋期

解説

正解は3。同じ数で割った余りが等しいなら、2つの値の差はその数で割り切れる。差をとると
1,168−571＝597＝3×199
1,566−1,168＝398＝2×199
となり、共通の約数は199（199は素数）。実際に割ると571＝2×199＋173、1,168＝5×199＋173、1,566＝7×199＋173で、余りはどれも173になる。

• 1の193で割ると、571の余りは185、1,168の余りは10で一致しない。
• 2の197で割ると、571の余りは177、1,168の余りは183で一致しない。
• 4の211で割ると、571の余りは149、1,168の余りは113で一致しない。

根拠：剰余（除算法）によるハッシュ関数と合同式の性質。