Сумма степеней по простому модулю [Теория чисел]

[Whitaker]

Понятно, что случай $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}$.
Рассуждение от противного ни к чему не приводит пока что

[nnosipov]

Whitaker в сообщении #897985 писал(а):

Рассуждение от противного ни к чему не приводит пока что

Должны приводить. Давайте вместо $a$ напишем $x$: пусть $x^r \equiv 1 \pmod{p}$ для всех $x$. Ну как, видно противоречие?

[Whitaker]

Может ночью я настолько не соображаю, что не вижу противоречия. Но я еще подумаю

[nnosipov]

Давайте до утра отложим. Такие вещи хорошо додумывать во сне.

[Whitaker]

nnosipov
$x^{r}-1\equiv 0 \pmod{p}$ по теореме Лагранжа имеет не более $r$ корней, но у нас $0<r<p-1$.
Противоречие!

(Оффтоп)

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

[nnosipov]

Всё верно.

[Whitaker]

Умножение на $a^n$ проходит когда $p-1\nmid n$.
А в случае $p-1\mid n$ пользуемся МТФ. Верно?

[nnosipov]

Да, именно так.

[Sonic86]

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)$.

(Оффтоп)

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

[nnosipov]

(Оффтоп)

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

[Whitaker]

nnosipov
Спасибо Вам большое за помощь в решении задачи! Узнал пару новых трюков
П.С. Также благодарю Sonic86 за предоставленное "групповое" доказательство.

[nnosipov]

Не за что. Будем любить алгебру и абстрактные конструкции, ибо они облегчают жизнь.