ВсОШ 2024, 11 класс, задача 8
Докажите, что существует такое , что для любого нечётного простого числа , , , , дают хотя бы различных остатков при делении на . (М. Туревский, И. Богданов)
Решение. Все сравнения в этом решении производятся по модулю . Если и - целые числа, причём не делится на , то через мы обозначаем тот единственный остаток по модулю , для которого .
Пусть числа , , , , дают ровно различных остатков при делении на . Обозначим . Тогда выражения вида
при дают максимум различных остатков.
Назовём пару натуральных чисел таких, что , исключительной, если . Покажем, что для каждого существует не более одной исключительной пары , в которой . Действительно, если - такая пара, то из вытекает, что , откуда , или . Такой остаток не более чем единственен (поскольку ), а по нему восстанавливается .
Итого, существует не более чем исключительная пара; обозначим их количество через . Пусть числа , , , дают ровно различных остатков по модулю , встречающихся раз соответственно. Тогда и . Верна следующая цепочка неравенств:
,
откуда . Вспоминая, что , получаем оценку
.
Таким образом, в качестве искомой константы можно взять, например, число : для простых неравенство тривиально, а для следует из неравенства при .