2014 dxdy logo

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

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




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


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

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

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

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


20/04/10
1776
$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
8858
А вот эти $k$ как искать? И откуда вдруг взялось $x^5$?

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


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

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


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

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


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

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

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


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

(Ответ)

автоморфизм

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


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

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


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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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