2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 19:47 
Аватара пользователя


12/01/11
1320
Москва
Здравствуйте, уважаемые друзья!

Пусть $n\geqslant 1$ и $S_n(p)=1^n+2^n+\dots+(p-1)^n+p^n$. Тогда $$S_n(p) =
\begin{cases}
0\pmod p, & \text{если } p-1\nmid n \\
-1\pmod p, & \text{если } p-1\mid n
\end{cases}$$Моя попытка доказательства: Случай когда $p-1\mid n$ выводится тривиально из МТФ. Перейдем к нетривиальному случаю, когда $p-1\nmid n$.
Будем рассуждать от противного. Пусть $p-1\nmid n$, но $p\nmid S_n(p)$. Пусть $n$ - такое минимальное число и запишем в таком виде: $n=(p-1)d+r,$ где $d\geqslant 0$ и $0<r<p-1$. МТФ гласит, что при $p\nmid a$ имеем $a^{p-1}\equiv 1 \pmod{p}$. Воспользовавшись МТФ получаем, что $S_n(p)\equiv S_r(p)\pmod{p}$. Так как $n$ -- минимальное, то $r=n$. Здесь воспользуемся тождеством Паскаля, которое доказывается довольно легко и имеет вид: $$(a+1)^{n+1}-1=\sum \limits_{k=0}^{n}C_{n+1}^{k}S_k(a).$$ Понятно, что $p\mid S_k(p)$ при $k<n$. Рассматривая тождество Паскаля по модулю $p$ при $a=p$ получаем, что: $p\mid C_{n+1}^{n}S_n(p)$ или $p\mid (n+1)S_n(p)$.
Возникает следующий вопрос: как тут получить противоречие?
П.С. Понимаю, что это легко выводится, если применить первообразные корни, но хотелось бы получить доказательство без них.

Помогите пожалуйста.

С уважением, Whitaker.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 19:57 
Заслуженный участник


20/12/10
8858
Whitaker в сообщении #897921 писал(а):
это легко выводится, если применить первообразные корни, но хотелось бы получить доказательство без них
Можно и без них: умножим сумму на подходящее $a^n$.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 19:57 
Заслуженный участник


08/04/08
8556
Ой, ужас какой.
Много букв, не читал, честно говоря, извините.
Сумма вычисляется в лоб. Начните для простоты с другого крайнего случая $p-1\perp n$. Вспомните про цикличность мультипликативной группы вычетов.

nnosipov в сообщении #897926 писал(а):
Можно и без них: умножим сумму на подходящее $a^n$.
Ага, или так. В книжках про характеры такой прием часто встречается.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:27 
Аватара пользователя


12/01/11
1320
Москва
nnosipov
Но что это за подходящее можете намекнуть? что-то пока не очевидно

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:29 
Заслуженный участник


20/12/10
8858
Ну, там не любое $a$ сгодится. Нужно хорошее $a$ подобрать. Точнее, доказать, что оно существует.

Имеется в виду сначала получить равенство $a^nS_n(p)=S_n(p)$, а потом его проанализировать.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:38 
Аватара пользователя


12/01/11
1320
Москва
Хочется умножить на $a^n,$ где $(a,p)=1$

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:40 
Заслуженный участник


20/12/10
8858
Ясное дело, на ноль умножать как-то незачем.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:45 
Аватара пользователя


12/01/11
1320
Москва
Да Вы правы :D
Получаем, что $S_n(p)(a^n-1)\equiv 0 \pmod{p}$
Здесь походу надо воспользоваться МТФ и рассмотреть какие-то случаи да?

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:49 
Заслуженный участник


20/12/10
8858
Типа того. Но сначала нужно чётко сформулировать, что мы хотим от $a$.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:51 
Аватара пользователя


12/01/11
1320
Москва
Наверное $a$ должно быть таким, чтобы $a^n-1$ были взаимно с $p$, тогда отсюда получаем, что $p\mid S_n(p)$

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 20:53 
Заслуженный участник


20/12/10
8858
Точно. Вот и докажите теперь, что такое $a$ обязательно найдётся.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 21:11 
Аватара пользователя


12/01/11
1320
Москва
nnosipov
Кстати походу тут случай $p=2$ не катит, т.к. иначе получается бред.
Дальше будем полагать, что $p>2$
Пусть для всех $a$ таких, что $(a,p)=1$ имеет $a^n\equiv 1 \pmod p$. Такие $a$ пробегают множество $\{1, 2, \dots, p-1\}$. Перемножая их мы получаем, что: $((p-1)!)^n\equiv 1 \pmod p$ и здесь пользуемся теоремой Вильсона и получаем, что $(-1)^n\equiv 1 \pmod{p}$.
При $n$ -- нечетном и учитывая, что $p>2$ получаем противоречие.
А теперь остается случай $n$ -- четное.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 21:32 
Заслуженный участник


20/12/10
8858
Whitaker в сообщении #897956 писал(а):
А теперь остается случай $n$ -- четное.
Лучше придумайте общее рассуждение, не делите на случаи.

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 21:53 
Аватара пользователя


12/01/11
1320
Москва
Согласен с Вами т.к. уже для случая четного числа не знаю как делать.
Но там наверняка нужно разобрать случаи какие нибудь ?!

 Профиль  
                  
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 22:25 
Заслуженный участник


20/12/10
8858
Нет, надо только воспользоваться тем, что $n$ не делится на $p-1$. И поделить.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

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



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

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


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

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