Новогодняя задача-2022

[nnosipov]

Поскольку для олимпиадного раздела слишком мелко, помещаю сюда.

Решите сравнение $x^{2021}+111 \equiv 0 \pmod{2022}$.

Комментарий. Прикол в том, чтобы решить это в уме. Для этого дается подсказка (без нее, наверное, было бы трудновато и поэтому скучно; впрочем, энтузиасты могут попробовать и без): воспользоваться волшебным разложением $337=3^4+4^4$ для простого делителя $337$ числа $2022$.

[lel0lel]

$x^{5}+111 \equiv 0 \pmod{6}$, решение $x=3$. Остаётся решить $(6k+3)^{5}+111 \equiv 0 \pmod{337}$, при желании можно и в уме, $k=18$.

[nnosipov]

А вот эти $k$ как искать? И откуда вдруг взялось $x^5$?

[lel0lel]

nnosipov в сообщении #1544718 писал(а):

откуда вдруг взялось $x^5$?

$x^{2021} \equiv x^5 \pmod{2}$, $x^{2021} \equiv x^5 \pmod{3}$, $x^{2021} \equiv x^5 \pmod{337}$, числа $2$, $3$, $337$ взаимнопростые, поэтому можно перейти к степени $5$.

nnosipov в сообщении #1544718 писал(а):

вот эти $k$ как искать?

Полный перебор. Не так уж долго, если на листе бумаги.

[nnosipov]

lel0lel в сообщении #1544744 писал(а):

поэтому можно перейти к степени $5$

Да можно, конечно, но в уме делить $2021$ на $336$ с остатком как-то не очень. Впрочем, на вкус и цвет ... Принято.

lel0lel в сообщении #1544744 писал(а):

Полный перебор.

Не, ну это перебор. Не мог я такого предложить! Да еще под Новый год. Присмотритесь все же к волшебному равенству, там почти все сразу.

[Osmiy]

Ну нету здесь специалистов по аналитической теории чисел. Вы разделом ошиблись
Наверняка там используется какая-то теорема.

[nnosipov]

Да клянусь, что нет там никакой аналитической теории чисел, боже упаси

Osmiy в сообщении #1544777 писал(а):

Наверняка там используется какая-то теорема.

Нет там никакой теоремы, разве что алгоритм Евклида, да и то чисто виртуально, для обоснования корректности.

А почему никто не хочет всмотреться в волшебное равенство? Кстати, $3 \cdot 111=333$.

[lel0lel]

nnosipov в сообщении #1544779 писал(а):

Кстати, $3 \cdot 111=333$.

Понятно как проверить, что $x=111$ является решением, но почему единственным?

Проверим, что $111^{5}+111 \equiv 0 \pmod{337}$, можно записать $(-4/3)^{5}-4/3 \equiv 0 \pmod{337}$ или $-4 (4^{4}+3^4)\equiv 0 \pmod{337}$, используя

nnosipov в сообщении #1544713 писал(а):

$337=3^4+4^4$

убеждаемся, что это решение. По модулю $6$ проверяется легко. Но почему оно единственное? Разве как-то так записать $x^{5}-(-4/3)^5 \equiv 0 \pmod{337}$?

[nnosipov]

Да, все верно

lel0lel в сообщении #1544786 писал(а):

Но почему оно единственное?

Да, остался только этот момент. Но это уже мелочь, здесь общие соображения: сравнение-то, слава богу, двучленное. Рассмотрим отображение $x \mapsto x^5$. По отношению к мультипликативной группе поля классов вычетов по модулю $337$ оно есть ... кто?

(Ответ)

автоморфизм

[lel0lel]

Всё таки без маленькой теоремки не обошлось. Я так понимаю, тот факт, что это автоморфизм следует из того, что $5\nmid 336$.

[nnosipov]

lel0lel в сообщении #1544791 писал(а):

тот факт, что это автоморфизм следует из того, что $5\nmid 336$

Конечно, но лучше написать $\gcd{(5,336)}=1$. Хотя да, мелкая теорема типа малой теоремы Ферма здесь действительно потребуется. Каюсь, забыл, что малая теорема Ферма это теорема.

Всех с Новым годом!