2018年度 秋期 高度試験共通 午前I 問9

問題文の前提を再確認すると、全てのハッシュ値が衝突したということは、571, 1168, 1566をある数Xで割ったときの余りが全て同じになったということです。この「同じ余り」をmとすると、

571 = q1 * X + m

1168 = q2 * X + m

1566 = q3 * X + m

となります。ここでq1, q2, q3は商です。

この関係から、差をとると

1168 - 571 = (q2 - q1) * X => 597はXで割り切れる

1566 - 1168 = (q3 - q2) * X => 398はXで割り切れる

となります。つまり、Xは597と398の公約数です。

597 = 3 * 199

398 = 2 * 199

よって、597と398の公約数は1, 2, 199, 398です。

自然数を除数としているため、選択肢の中から199が該当します。

ア: 193は597の約数ですが、398の約数ではありません。

イ: 197は597, 398のどちらの約数でもありません。

エ: 211は597, 398のどちらの約数でもありません。