Два различных простых числа p и q отличаются менее чем в два раза. Докажите, что существуют такие два последовательных натуральных числа, что у одного из них наибольший простой делитель равен p, а у другого — q.
(А. Голованов)
Решение 1 (полная система вычетов). Пусть 
Рассмотрим целые числа 
Это p последовательных чисел, поэтому все они дают различные остатки при делении на p. Умножим теперь эти p чисел на q. Покажем, что числа в новом наборе также будут давать различные остатки при делении на p. Если qa и qb (при 
дают одинаковые остатки при делении на p, то натуральное число 
делится на p, а значит, и 
делится на p, что невозможно, ибо положительно и меньше p. Итак, числа в новом наборе дают различные остатки при делении на 
Но поскольку их всего p, среди них найдется число, дающее остаток 
Следовательно, мы доказали, что существует такое число k, что 
делится на p и 
Тогда
Поэтому число не может иметь простых делителей, больших p, ибо произведение такого делителя с p уже больше, чем 
и тем более больше, чем 
Если 
то нам подойдут числа 
и В противном случае нам подойдут числа 
и 
Решение 2 (китайская теорема об остатках). Пусть p — меньшее из простых чисел. По китайской теореме об остатках найдется такое число a, которое делится на q и дает при делении на p остаток 1. Заметим, что любое число вида 
при целом k также удовлетворяет этому условию. Подберем k так, что 
Тогда число 
делится на q и результат деления меньше p, поэтому наибольший простой делитель q равен Кроме того, 
делится на p, поэтому если 
то наибольший простой делитель равен p и мы напыли требуемые числа. Пусть 
Тогда рассмотрим натуральное число 
Оно делится на q и результат деления меньше p, поэтому набольший простой делитель c равен q. Кроме того
число 
делится на p и частное не превосходит 
Поэтому наибольший простой делитель равен p и мы нашли требуемые числа.
Решение 3 (линейное представление наибольшего общего делителя). Пусть 
Но тогда
при любом целом k. Подберем k так, что 
Тогда число 
делится на q и меньше 
Поэтому у него нет простых делителей, больших 
Если 
не имеет простых делителей, больших p, то мы нашли требуемую пару чисел: и 
В противном случае заметим, что 
и
Тогда число 
делится на q и не превосходит pq. Поэтому у него нет простых делителей, больших q. Если 
не имеет простых делителей, больших p, то мы нашли требуемую пару чисел: 
и 
Если же требуемая пара чисел еще не найдена, то числа и имеют простые делители, большие p, а, значит,
Противоречие.