Конечно ли множество натуpальных чисел m таких, что количество обpатимых элементов в кольце классов вычетов по модулю m pавно количеству квадpатов в том же кольце?

Решение

Широко известно (и несложно доказывается, что количество обратимых элементов кольца Z_m равно ф(m), где ф - функция Эйлера.

Обозначим через s(m) количество квадратов в кольце Z_m.
Если p - нечетное простое, то s(p) очевидно (поскольку a² = (-a)²) равно (p + 1)/2. Для степени нечетного простого s(p^k) = [p^k+1/(2p + 2)] + 1, где [m] - целая часть числа m. Для доказательства достаточно рассмотреть s(p^k) как сумму квадратов: взаимно простых с p; кратных p², но кратных p⁴...
Для степеней двойки ситуация немного отличается: s(2^k) = [2^k-1/3] + 2. Заметим также, что в силу китайской теоремы об остатках, функция s(m) мультипликативна.

Рассмотрим функцию q(m) = s(m)/ф(m).
Нас интересуют такие m, для которых q(m) = 1.
Поскольку и числитель и знаменатель мультипликативные функции, этим же свойством будет обладать и q(m). Поэтому достаточно рассмотреть поведение q на степенях простых чисел.
Для степеней двойки имеем q(2) = 2, q(4) = 1. Для остальных степеней двойки значение функции менньше 1.
Для нечетных простых q(p^k) = [p^k+1/(2p + 2)]/(p - 1)(p^k-1 - 1) + 1/(p - 1)(p^k-1 - 1). Из этой формулы видно, что q(p^k) уменьшается с ростом как p, так и k, оставаясь при этом больше 1/2.
Наибольшие из значений q(p^k): q(3) = 1; q(5) = 3/4, q(7) = q(9) = 2/3. Все остальные меньше 2/3.

Если показатель двойки в каноническом разложении m отличен от 1, то равенство q(m) = 1 возможно лишь в том случае, когда 1 равны все сомножители. Это дает нам 4 (если считать вырожденный случай m = 1) подходящих m: 1, 3, 4, 12.

Рассмотрим теперь случай, когда показатель двойки в разложении m равен 1. В этом случае произведение q для степеней нечетных простых, входящих в разложенеие m, должно быть равно 1/2.
Поскольку каждое такое q больше 1/2, то нечетных простых сомножителей в разложении m должно быть не меньше двух.
С другой стороны, за исключением q(3) и q(5), q(p^k) < 1/Ö2. Поэтому одним из сомножителей m обязана быть пятерка (наличие тройки ничего не меняет) в первой степени. Тогда q от другого сомножителя должно быть равно 2/3. Это расссуждение дает нам еще 3 подходящих m: 70, 90, 210.

Ответ: количество обpатимых элементов в кольце классов вычетов по модулю m pавно количеству квадpатов в том же кольце только для следующих m: 1, 3, 4, 12, 70, 90, 210.

Oбсуждение

Конечность множества рассматриваемых m не обусловлена тенденцией к опережающему (по отношению к конкуренту) росту s(m) или ф(m). Из приведенного решения видно, что существует бесконечно много m, для которых q(m) > 1, и бесконечно много m, для которых q(m) < 1.

Награды

За правильное решение этой задачи Виктор Филимоненков и Вдад Франк получают по 11 призовых баллов.

Эстетическая оценка задачи - 4 балла.