Задание №180891: Командная олимпиада 2021

Ответ: Да, верно.
Решение. Лемма Для простого нечетного 𝑞 и положительных 𝑘 > 𝑚 выполнено равен-
ство
(𝑞2𝑘 + 1,𝑞2𝑚 + 1) = 2.
Доказательство: Заметим (применив формулу разности квадратов 𝑘 − 𝑚 раз), что
𝑞2𝑘 − 1 ⋮ 𝑞2𝑚 + 1.
Тогда понятно, что выполнена следующая цепочка равенств:
(𝑞2𝑘 + 1,𝑞2𝑚 + 1) = ((𝑞2𝑘 − 1) + 2,𝑞2𝑚 + 1) = (2,𝑞2𝑘 + 1) = 2.
Лемма доказана.
Теперь заметим, что, согласно лемме, найдется такое 𝑟, что у 𝑞2𝑟 + 1 есть делитель, боль-
ший 𝑞 (иная ситуация быстро начинает противоречить тому, что попарные НОДы таких
4

чисел равны 2). Возьмем для данного простого нечетного 𝑞 минимальное такое 𝑟 и дока-
жем, что
𝑝(𝑞2𝑟 − 1) < 𝑝(𝑞2𝑟) < 𝑝(𝑞2𝑟 + 1).
𝑝(𝑞2𝑟 + 1) по построению больше 𝑞, 𝑝(𝑞2𝑟), очевидно, равно 𝑞, осталось доказать, что
𝑝(𝑞2𝑟 − 1) меньше, чем 𝑞.
𝑞2𝑟 − 1 с помощью 𝑟 раз примененной формулы разности квадратов, раскладывается в
произведение скобок, все, кроме двух из которых имеют вид 𝑞2𝑠 − 1, 𝑠 < 𝑟 и по выбору
𝑟 не могут иметь простых делителей, больших 𝑞, а две являются 𝑞 + 1 и 𝑞 − 1, у которых
простыхделителей,больших𝑞неможетбытьпоочевиднымсоображениям.Получается,
для данного 𝑞 мы нашли 𝑟, т.ч.
𝑝(𝑞2𝑟 − 1) < 𝑝(𝑞2𝑟) < 𝑝(𝑞2𝑟 + 1).
Осталосьзаметить,чтомыможемнайтитакое𝑟исоответствующуютройку(которые,оче-
видно, не будут совпадать), для каждого из бесконечного множества нечетных простых
чисел, что и доказывает ответ.