Принцип Дирихле

Положим для краткости На доске выписаны натуральные числа от до . Рассмотрим выписанные числа, взаимно простые с 6. Таких чисел ровно поскольку среди любых шести подряд идущих чисел ровно два числа взаимно просты с (это числа, дающие остатки и при делении на ). Выпишем делители, которые мы выбрали у этих чисел. Эти делители по крайней мере в раз меньше исходного числа, значит, все они меньше . Кроме того, они взаимно просты с значит, их всего не более Таким образом, мы сопоставили каждому из чисел делитель, причем всего делителей Следовательно, какие-то два делителя совпадают.