2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Новогодняя задача-2022
Сообщение30.12.2021, 20:38 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение30.12.2021, 21:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение30.12.2021, 21:55 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 10:24 
Заслуженный участник


20/04/10
1973
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$ как искать?
Полный перебор. Не так уж долго, если на листе бумаги.

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 10:56 
Заслуженный участник


20/12/10
9179
lel0lel в сообщении #1544744 писал(а):
поэтому можно перейти к степени $5$
Да можно, конечно, но в уме делить $2021$ на $336$ с остатком как-то не очень. Впрочем, на вкус и цвет ... Принято.
lel0lel в сообщении #1544744 писал(а):
Полный перебор.
:shock: Не, ну это перебор. Не мог я такого предложить! Да еще под Новый год. Присмотритесь все же к волшебному равенству, там почти все сразу.

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 15:25 


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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 15:36 
Заслуженный участник


20/12/10
9179
Да клянусь, что нет там никакой аналитической теории чисел, боже упаси :D
Osmiy в сообщении #1544777 писал(а):
Наверняка там используется какая-то теорема.
Нет там никакой теоремы, разве что алгоритм Евклида, да и то чисто виртуально, для обоснования корректности.

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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 17:57 
Заслуженный участник


20/04/10
1973
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}$?

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 18:18 
Заслуженный участник


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

(Ответ)

автоморфизм

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 18:32 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Новогодняя задача-2022
Сообщение31.12.2021, 19:16 
Заслуженный участник


20/12/10
9179
lel0lel в сообщении #1544791 писал(а):
тот факт, что это автоморфизм следует из того, что $5\nmid 336$
Конечно, но лучше написать $\gcd{(5,336)}=1$. Хотя да, мелкая теорема типа малой теоремы Ферма здесь действительно потребуется. Каюсь, забыл, что малая теорема Ферма это теорема.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group