ВсОШ 2021, 9 класс, задача 7
Натуральные числа и таковы, что делится на . Докажите, что найдутся натуральные числа и такие, что .
(А. Храбров)
Решение.
Заметим, что из равенства следует равенство . Поэтому для решения задачи достаточно найти такое натуральное , что число раскладывается в произведение двух натуральных чисел и , больших (тогда можно положить и ).
Согласно условию, для некоторых простого и натурального . Если , то в силу разложения в качестве можно взять число . Также, если число составное, то при ; тогда снова можно положить , так как .
В оставшемся случае имеем при некотором простом . Если , то при некотором положительном и натуральном . Тогда число
делится на , а частное от деления больше , поскольку . Поэтому можно положить . Наконец, если , то , причем по условию. Тогда , где обе скобки больше ; в этом случае работает .
Замечание.
Несложно показать, что в виде можно представить все натуральные числа , для которых число составное, - в частности, все нечетные числа, отличные от . С помощью этого наблюдения и калькулятора несложно найти первые чисел, не представимых в виде (все они меньше пятисот). В статье Борвейна и Чоя утверждается, что количество чисел, не представимых в виде , не более , и существование девятнадцатого такого числа противоречило бы обобщенной гипотезе Римана (которая в настоящий момент не является ни доказанной, ни опровергнутой).