Уточнение малой теоремы Ферма

[lantza]

Известно, что если $p$ - простое число, и $(a,n)=1$, то $a^{p-1} \equiv 1 \pmod p$.

Имеется следующее утверждение (уточнение малой теоремы Ферма):

$\forall p > 2 \quad \forall k \in \{1,2,...,p-2\} \quad \exists a \in \mathbb N \colon \quad a^{k} \not\equiv 0 \pmod p \; $и$ \; a^{k}\not\equiv 1 \pmod p$

Другими словами, наименьшее такое число $k$, что $a^{k} \equiv 1 \pmod p$ для любого $a$ (не делящего на $p$), есть $p-1$.

Как именно можно доказать это утверждение? Совершенно нет идей, как можно доказать такое утверждение, поскольку совершенно не ясно, как построить такое число $a$. Рассмотр всех вычетов по модулю $p$ мне мало что помогает: в общем случае совершенно все что угодно может произойти при возведении произвольного числа из системы вычетов в степень $k$.

[Sonic86]

Ваше уточнение - это утверждение о том, что мультипликативная группа поля вычетов $\mathbb{Z}_p^\times$ по простому модулю $p$ циклична. Это стандартный факт, его можно найти во многих учебниках по теории чисел (Виноградов, Бухштаб, Нестеренко, даже Нидеррайтер и т.п.)
ЕМНИП, одно из доказательств строится так:
1) доказывается, что в $\mathbb{Z}_p^\times$ число элементов порядка $a:a^d\equiv 1\pmod p$ не более $d$ (здесь используется простота $p$).
2) Для каждого $d$ через функцию Эйлера вычисляется число элементов порядка $d$, оно равно $\varphi(d)$. Для $d=p-1$ имеем $\varphi (\varphi(p))$ образующих по модулю $p$.
(это типа без теории групп)
Из ГР или какого-то ее обобщения следует, что на отрезке $[1;C\ln ^2p]$ всегда имеется образующая, $C=\operatorname{const}$.

[lantza]

Sonic86 в сообщении #1089267 писал(а):

Ваше уточнение - это утверждение о том, что мультипликативная группа поля вычетов $\mathbb{Z}_p^\times$ по простому модулю $p$ циклична. Это стандартный факт, его можно найти во многих учебниках по теории чисел (Виноградов, Бухштаб, Нестеренко, даже Нидеррайтер и т.п.)

А есть ли другое решение этого же утверждения без привлечения теории групп?

[Sonic86]

lantza в сообщении #1089268 писал(а):

А есть ли другое решение этого же утверждения без привлечения теории групп?

Бухштаба смотрите

(Оффтоп)

нафига людям это без теории групп - вообще непонятно.

lantza в сообщении #1089246 писал(а):

Имеется следующее утверждение (уточнение малой теоремы Ферма):

$\forall p > 2 \quad \forall k \in \{1,2,...,p-2\} \quad \exists a \in \mathbb N \colon \quad a^{k} \not\equiv 0 \pmod p \; $и$ \; a^{k}\not\equiv 1 \pmod p$

Интересно, а зачем нужно 1-е условие в предикате?

[Sinoid]

Сначала изучите первообразные корни, индексы.

[lantza]

Sinoid в сообщении #1089274 писал(а):

Сначала изучите первообразные корни, индексы.

Изучил.
Нужно, чисто найдя все первообразные корни по модулю $p$, вытащить из системы вычетов остальные числа (кроме $0$ и $1$) и получить требуемое утверждение, присвоив случайно числом $a$ одно из этих чисел?

[Sonic86]

Sinoid в сообщении #1089274 писал(а):

Сначала изучите первообразные корни, индексы.

Незачем: индексы нельзя выучить без первообразных, а первообразные ... - ТС же спрашивает об их существовании.

[lantza]

Sonic86 в сообщении #1089271 писал(а):

Интересно, а зачем нужно 1-е условие в предикате?

Ну, чтобы $a$ не делилось на $p$.

[Sinoid]

lantza в сообщении #1089268 писал(а):

А есть ли другое решение этого же утверждения без привлечения теории групп?

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

[lantza]

Sonic86 в сообщении #1089279 писал(а):

Незачем: индексы нельзя выучить без первообразных, а первообразные ... - ТС же спрашивает об их существовании.

Про существование обычных первообразных корней я в курсе, до меня что-то не дошло о них вспомнить (поскольку по курсу они дальше идут после этого утверждения, поэтому и не доходило еще).

[Sinoid]

Sonic86 в сообщении #1089279 писал(а):

Sinoid в сообщении #1089274

писал(а):
Сначала изучите первообразные корни, индексы. Незачем: индексы нельзя выучить без первообразных, а первообразные ... - ТС же спрашивает об их существовании.

Я имел в виду, что эти вопросы крутятся вокруг этих тем, ведь в первом посте ТС упоминания про первообразные корни нет.

[Brukvalub]

lantza в сообщении #1089246 писал(а):

Известно, что если $p$ - простое число, и $(a,n)=1$, то $a^{p-1} \equiv 1 \pmod p$.

Надо же, как наука продвинулась!

[bot]

Brukvalub, ну и глазаст! Берём $n=1$ ...

[Brukvalub]

(Оффтоп)

bot в сообщении #1089517 писал(а):

Brukvalub, ну и глазаст!

С детства знаю, что "у меня четыре глаза, я похож на водолаза!"