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

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