2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 23:11 
Аватара пользователя
Понятно, что случай $p-1\mid n$ не подходит нам. Рассматриваем случай $p-1\nmid n$ и получаем, что $n=(p-1)d+r,$ где $d\in \mathbb{Z}$ и $0<r<p-1$. Задача сводится к следующей:
Пусть $0<r<p-1$. Доказать, что существует $a$ такой, что $(a,p)=1$ и $a^r\not\equiv 1 \pmod{p}$.
Рассуждение от противного ни к чему не приводит пока что

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 23:16 
Whitaker в сообщении #897985 писал(а):
Рассуждение от противного ни к чему не приводит пока что
Должны приводить. Давайте вместо $a$ напишем $x$: пусть $x^r \equiv 1 \pmod{p}$ для всех $x$. Ну как, видно противоречие?

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 23:42 
Аватара пользователя
Может ночью я настолько не соображаю, что не вижу противоречия. Но я еще подумаю :-(

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение20.08.2014, 23:46 
Давайте до утра отложим. Такие вещи хорошо додумывать во сне.

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 00:04 
Аватара пользователя
nnosipov
$x^{r}-1\equiv 0 \pmod{p}$ по теореме Лагранжа имеет не более $r$ корней, но у нас $0<r<p-1$.
Противоречие!

(Оффтоп)

Лег спать. Пришла такая идея. Встал. Включил комп и написал :-)

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 00:14 
Всё верно.

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 00:16 
Аватара пользователя
Умножение на $a^n$ проходит когда $p-1\nmid n$.
А в случае $p-1\mid n$ пользуемся МТФ. Верно?

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 09:21 
Да, именно так.

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 11:35 
Whitaker в сообщении #897994 писал(а):
$x^{r}-1\equiv 0 \pmod{p}$ по теореме Лагранжа имеет не более $r$ корней, но у нас $0<r<p-1$.
Противоречие!
После решения я добавлю групповые соображения как более общие:
Мультипликативная группа вычетов циклична. А если $a^r=1, b^r=1$, то $(ab)^r=1$, т.е. множество корней $r$-й степени из единицы - это подгруппа, да еще и цикличная как подгруппа циклической группы. Значит ее мощность равна $r$, а $r<p$.
А исходная сумма попросту $\equiv\frac{p-1}{d}\sum\limits_{k=0}^{d-1}g^{k\frac{p-1}{d}}, d=\gcd(n,p-1)$.

(Оффтоп)

в частности, не нужно знать какую-то неведомую теорему Лагранжа

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 11:45 

(Оффтоп)

Теорема Лагранжа --- так, вероятно, называется этот простой факт то ли у Виноградова, то ли у Бухштаба. Понятно, что это частный случай почти очевидной теоремы о том, что у многочлена над полем корней не более, чем его степень.

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 14:42 
Аватара пользователя
nnosipov
Спасибо Вам большое за помощь в решении задачи! Узнал пару новых трюков :-)
П.С. Также благодарю Sonic86 за предоставленное "групповое" доказательство.

 
 
 
 Re: Сумма степеней по простому модулю [Теория чисел]
Сообщение21.08.2014, 15:03 
Не за что. Будем любить алгебру и абстрактные конструкции, ибо они облегчают жизнь.

 
 
 [ Сообщений: 27 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group