分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

aをnで割ったときの商をk、bをnで割ったときの商をl、余りがどちらもxとなる場合を式で表すと、

　a＝kn＋x
　b＝ln＋x

となります。これをxについて解くと、

　x＝a－kn
　x＝b－ln

と変換できます。余りであるxが等しくなるとき a－kn と b－ln は等しいので、方程式で関係を導きます。

　a－kn＝b－ln
　a－b＝kn－ln
　a－b＝n(k－l)

ここで、aとb及びnが自然数であることから商であるkとlも自然数となります。よって n(k－l) はnの倍数です。

∴余りxが同じとき、a－bはnの倍数
　
以上より、キーの衝突には「a－bがnの倍数」という条件があるとわかります。したがって「イ」が正解です。

ここまでが論理的に解を導く方法ですが、計算結果が同じになるa・b・nを用意して選択肢の記述の正誤を判断することもできます。例えば、a＝51、b＝27、n＝12（どちらも余りが3）で試してみると、

• a＋b＝78なので、12の倍数ではありません(×)。
• a－b＝24なので、12の倍数になっています(〇)。
• a＋b＝78なので、12は78の倍数ではありません(×)。
• a－b＝24なので、12は24の倍数ではありません(×)。