Среди любых n+1 натуральных чисел найдутся два числа, которые при делении на n дают одинаковые остатки.

Легко доказать по остаткам.
Любые n чисел при делении на n могут дать n разных остатков, от 0 до (n-1).
(n+1)-ое число тоже даст какой-то из этих остатков.
И он совпадет с одним из тех n.
Разность двух чисел с одинаковыми остатками кратна n.