Закл 2024

Все сравнения в этом решении производятся по модулю Если и — целые числа, причём не делится на то через мы обозначаем тот единственный остаток по модулю для которого

Пусть числа

дают ровно различных остатков при делении на Обозначим Тогда выражения вида

при дают максимум различных остатков.

Назовём пару натуральных чисел таких, что исключительной, если Покажем, что для каждого существует не более одной исключительной пары в которой Действительно, если — такая пара, то из

вытекает, что

откуда

или Такой остаток не более чем единственен (поскольку ), а по нему восстанавливается

Итого, существует не более чем исключительная пара; обозначим их количество через Пусть числа дают ровно различных остатков по модулю встречающихся раз соответственно. Тогда

Верна следующая цепочка неравенств:

откуда

Вспоминая, что получаем оценку

Таким образом, в качестве искомой константы можно взять, например, число для простых неравенство тривиально, а для следует из неравенства при