Как принцип Дирихле может применяться при решении задач делимости?

Принцип Дирихле может применяться при решении задач делимости, позволяя утверждать, что среди нескольких целых чисел найдутся два, дающие при делении на определённое число один и тот же остаток. infourok.ru

Пример: нужно доказать, что среди любых шести целых чисел найдутся два, разность которых кратна 5. foxford.ru Решение: при делении целого числа на 5 возможны пять различных остатков: 0, 1, 2, 3 или 4. foxford.ru Но в условии шесть чисел, значит, среди них обязательно найдутся два с одинаковыми остатками. foxford.ru Если рассмотреть их разность, то она будет давать при делении на 5 остаток 0, то есть будет делиться на 5. foxford.ru

Ещё один пример: нужно доказать, что из любых семи натуральных чисел можно выбрать три числа, сумма которых делится на 3. foxford.ru Решение: по принципу Дирихле из семи чисел можно выбрать три, дающие одинаковые остатки при делении на 3 (так как имеется лишь три различных остатка — 0, 1 и 2). foxford.ru Их сумма, очевидно, делится на 3. foxford.ru