2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Теория чисел
Сообщение04.10.2021, 16:00 
Аватара пользователя


15/08/09
1458
МГУ
Найти все пары $(n;p)$ натуральных чисел такие, что $p$-простое , $n \leq 2p$ и $(p-1)^{n}+1$ делится на $n^{p-1}$

 Профиль  
                  
 
 Re: Теория чисел
Сообщение04.10.2021, 16:22 
Заслуженный участник


20/12/10
8858
Эта задача с 40-й IMO. Здесь можно убрать условие $n \leqslant 2p$, ответ не изменится.

 Профиль  
                  
 
 Re: Теория чисел
Сообщение04.10.2021, 16:45 
Аватара пользователя


15/08/09
1458
МГУ
nnosipov
да да с неё, просто задача понравилась, вот и решил поделиться, а про убирание условия не знал, спс

 Профиль  
                  
 
 Re: Теория чисел
Сообщение05.10.2021, 09:10 


02/04/18
240
Вроде можно и требование простоты $p$ убрать. Достаточно $p>1$.

 Профиль  
                  
 
 Re: Теория чисел
Сообщение05.10.2021, 11:41 
Аватара пользователя


15/08/09
1458
МГУ
Dendr
вот что то я не уверен..... вряд ли на межнар дали бы задачу с такими гибкими условиями

 Профиль  
                  
 
 Re: Теория чисел
Сообщение05.10.2021, 19:06 
Заслуженный участник


20/12/10
8858
Dendr в сообщении #1533995 писал(а):
Вроде можно и требование простоты $p$ убрать.
Как-то это неочевидно. У Вас есть доказательство?

 Профиль  
                  
 
 Re: Теория чисел
Сообщение05.10.2021, 21:00 
Аватара пользователя


15/08/09
1458
МГУ
я уверен что простоту p убирать не в кое случаи нельзя

 Профиль  
                  
 
 Re: Теория чисел
Сообщение06.10.2021, 12:42 


02/04/18
240
Действительно, нельзя. Помутнение нашло - решил, что в МТФ идет речь о взаимной простоте.

А в целом вот что: ясно, что есть тривиальные решения $(1, p), (n, 1)$. Пары $(2, 2), (3, 3)$ нетрудно найти даже руками.
Так же легко установить, что $n$ не может быть четным (кроме уже приведенных случаев) - случай $q=1$ дает $n=1, n=2$, в остальных случаях $q^n+1=(q^{n/2})^2+1$ должно делиться на 4, но это невозможно.

Далее можно заметить, что (обозначая $q=p-1$) либо $n^q-q^n=1$, либо $n^q<q^n$. Первое уравнение имеет только два решения, которые уже указаны выше. (надо ли здесь специально доказывать?)
Из второго неравенства следует, что $\frac{\ln n}{n}<\frac{\ln q}{q}$. Поскольку мы рассматриваем теперь только $n\ge3$, то получаем $q<n$. Или $p\le{n}$. Добавим также, что $n, q$ должны быть взаимно просты.

Вот здесь я и допустил ошибку: если бы МТФ была верна для таких случаев, то $q^n\equiv{q} \mod{n}$, то есть должно выполняться, по крайней мере, $n|q+1$, значит, единственная возможность - $q=n-1$. Но (помним про нечетность) $(n-1)^n+1=n^n-n\cdot n^{n-1}+... -\frac{n(n-1)}{2}n^2+n\cdot n-1+1$ - делится на $n^2$, но не на $n^3$. Поэтому $q\le2$, и мы приходим все к тем же решениям, а других решений больше нет.

На самом деле это, конечно, не так: например, уже $2^9\equiv8\neq2\mod{9}$, и "подходящих" значений $q$ может быть больше. Тогда нельзя из сравнительно простых соображений исключить, что еще решения есть.

Как применить ограничение на простоту $p$, пока не сообразил.

 Профиль  
                  
 
 Re: Теория чисел
Сообщение08.10.2021, 13:17 


02/04/18
240
А, ну конечно. Все гораздо проще. Рассматриваем только нечетные $n$, тогда, по условию, выполняется, крайней мере, $$n|(p-1)^n+1=p^n-np^{n-1}+\frac{n(n-1)}{2}p^{n-2}+...-\frac{n(n-1)}{2}p^2+np-1+1$$
Из этого следует, что $n|p^n$. Следовательно, $n$ - некоторая степень $p$. Пусть $n=p^k$.
Тогда получаем $$p^{k(p-1)}|(p-1)^{p^k}+1=p^{p^k}-p\cdot p^{p^k-1}+...-\frac{p^{k}\cdot \left(p^{p^k}-1\right)}{2}p^2+p^{k}\cdot p-1+1$$
Наименьшая степень $p$ справа - $k+1$, следовательно, $k(p-1)\le{k+1}, k(p-2)\le1$.
Отсюда, либо $k=0$ (тривиальное решение $n=1$), либо $p=2$ (это можно подставить непосредственно в условие и получить $n|2$, но новых решений это - пока - не даст), либо $p=3, k=1 \Rightarrow n=3$.

Если же $n$ - четное, то $(p-1)^n$ - нечетное. Следовательно, $p$ - четное, то есть $p=2$, и снова $n|2$, откуда получаем пару $(2, 2)$.

Ответ: $(1, p), (2, 2), (3, 3)$

 Профиль  
                  
 
 Re: Теория чисел
Сообщение08.10.2021, 13:26 
Заслуженный участник


20/12/10
8858
Dendr в сообщении #1534264 писал(а):
Из этого следует, что $n|p^n$.
Как именно следует?

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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