整数論： 合同式パズル

合同式を使えばパズルのように解ける問題。

問題：

 を正の整数とし、  を集合の相異なる元とする。 に対し、 は で割り切れるとする。このとき、 は で割り切れないことを示せ。

（出典：　国際数学オリンピック　2009年 第一問）

解答：
 を法とすると、条件式から に対し、

が成り立つ (条件式①)。

一方で、  は集合の相異なる元なので、

となる （条件式②）。

ところで、求めるべきは、

である （式③）。ここで左辺は条件式①を使い、次のように変換できる。

更に条件式①を使って変形する。

よって条件式②から、

となり、求めるべき式③が証明できた。