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

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