Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ52

Конкурсная задача ММ52 (11 баллов)

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

Решение

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

Обозначим через s(m) количество квадратов в кольце Zm.
Если p - нечетное простое, то s(p) очевидно (поскольку a2 = (-a)2) равно (p + 1)/2. Для степени нечетного простого s(pk) = [pk+1/(2p + 2)] + 1, где [m] - целая часть числа m. Для доказательства достаточно рассмотреть s(pk) как сумму квадратов: взаимно простых с p; кратных p2, но не кратных p4
Для степеней двойки ситуация немного отличается: s(2k) = [2k-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(pk) = [pk+1/(2p + 2)]/(p - 1)(pk-1 - 1) + 1/(p - 1)(pk-1 - 1). Из этой формулы видно, что q(pk) уменьшается с ростом как p, так и k, оставаясь при этом больше 1/2.
Наибольшие из значений q(pk): 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(pk) < 1/✔2. Поэтому одним из сомножителей m обязана быть пятерка (наличие тройки ничего не меняет) в первой степени. Тогда q от другого сомножителя должно быть равно 2/3. Это расссуждение дает нам еще 3 подходящих m: 70, 90, 210.

Ответ: количество обратимых элементов в кольце классов вычетов по модулю 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 балла.


 

 


Страница: [[marathon:problem_52]]

marathon/problem_52.txt · Последние изменения: 2016/03/27 12:00 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006