МОШ 2025, 11 класс, задача 4
Существуют ли такие натуральные числа и и такой многочлен с целыми коэффициентами, что не делится на , но делится на для любого простого числа и любого натурального ?
(А. Волостнов, С. Гришин)
Ответ
Ответ: существует.
Решение. Приведём несколько примеров таких многочленов.
- Пусть , , . Проверим, что не делится на . Действительно, не делится на . Теперь проверим, что делится на для любого простого числа и любого натурального . Если или , то многочлен тождественно равен . Для , где , имеем
Наконец, если простое число нечётно (а значит, и нечётно), то делится на , так как при любом нечётном значение делится на , а значит, и на .
- Пусть , , . Сначала проверим, что делится на при всех простых и натуральных .
Начнём со случая . Заметим, что первое слагаемое делится на , а значит, и на . Остаётся проверить, что делится на для чисел вида , где . При и это проверяется непосредственно; при число также делится на .
Теперь проверим утверждение для простых чисел . В этом случае взаимно просто с , а значит, достаточно доказать утверждение « кратно при любом , взаимно простом с ». Для этого заметим, что при всех таких по теореме Эйлера выполняется соотношение , а тогда
Остаётся проверить, что не делится на . Для этого снова заметим, что число делится на , а число не делится на .
Другое решение. Пусть — простое, , , и пусть — все не кратные натуральные числа, меньшие . Положим
Действительно, тогда
не кратно . При число имеет остаток от деления на , не кратный , поэтому один из множителей в определении будет кратен при . При и уже число будет кратно . Наконец, при , значение делится на .
Замечание. Если добавить условие взаимной простоты чисел и , то ответ к задаче изменится на противоположный. Действительно, предположим, что такое нашлось. Нетрудно видеть, что в качестве всегда можно брать степень простого числа. Действительно, если не делится на , то оно не делится и на для некоторого простого , для которого . В то же время из равенства следует аналогичное равенство и для . Если существует простое число вида , то для него выполняются сравнения . Существование такого простого числа следует из известной в теории чисел теоремы Дирихле о простых числах в арифметической прогрессии. Она утверждает, что в любой арифметической прогрессии с первым членом и разностью , где натуральные числа и взаимно просты, найдётся бесконечно много простых чисел. Доказательство этой теоремы выходит далеко за рамки школьной программы.