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