|
||||||||||||||||||
|
СодержаниеММ52Конкурсная задача ММ52 (11 баллов) Конечно ли множество натуральных чисел m таких, что количество обратимых элементов в кольце классов вычетов по модулю m равно количеству квадратов в том же кольце? Решение Широко известно (и несложно доказывается, что количество обратимых элементов кольца Zm равно ф(m), где ф - функция Эйлера.
Обозначим через s(m) количество квадратов в кольце Zm.
Рассмотрим функцию q(m) = s(m)/ф(m). Если показатель двойки в каноническом разложении m отличен от 1, то равенство q(m) = 1 возможно лишь в том случае, когда 1 равны все сомножители. Это дает нам 4 (если считать вырожденный случай m = 1) подходящих m: 1, 3, 4, 12.
Рассмотрим теперь случай, когда показатель двойки в разложении m равен 1. В этом случае произведение q для степеней нечетных простых, входящих в разложенеие m, должно быть равно 1/2. Ответ: количество обратимых элементов в кольце классов вычетов по модулю m равно количеству квадратов в том же кольце только для следующих m: 1, 3, 4, 12, 70, 90, 210. Oбсуждение Конечность множества рассматриваемых m не обусловлена тенденцией к опережающему (по отношению к конкуренту) росту s(m) или ф(m). Из приведенного решения видно, что существует бесконечно много m, для которых q(m) > 1, и бесконечно много m, для которых q(m) < 1. Макс Алексеев разместил соответствующие последовательности (A122903, A122904, A122905) в OEIS (почему-то без ссылки на ММ52). Награды За правильное решение этой задачи Виктор Филимоненков и Вдад Франк получают по 11 призовых баллов. Эстетическая оценка задачи - 4 балла.
|
|||||||||||||||||
|
||||||||||||||||||
|