2014 dxdy logo

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

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




 
 Уточнение малой теоремы Ферма
Сообщение09.01.2016, 13:41 
Известно, что если $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$.

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:30 
Ваше уточнение - это утверждение о том, что мультипликативная группа поля вычетов $\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}$.

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

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:36 
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-е условие в предикате?

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:44 
Сначала изучите первообразные корни, индексы.

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:48 
Sinoid в сообщении #1089274 писал(а):
Сначала изучите первообразные корни, индексы.

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:50 
Sinoid в сообщении #1089274 писал(а):
Сначала изучите первообразные корни, индексы.
Незачем: индексы нельзя выучить без первообразных, а первообразные ... - ТС же спрашивает об их существовании.

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:51 
Sonic86 в сообщении #1089271 писал(а):
Интересно, а зачем нужно 1-е условие в предикате?

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:51 
lantza в сообщении #1089268 писал(а):
А есть ли другое решение этого же утверждения без привлечения теории групп?

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 14:52 
Sonic86 в сообщении #1089279 писал(а):
Незачем: индексы нельзя выучить без первообразных, а первообразные ... - ТС же спрашивает об их существовании.

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 15:15 
Sonic86 в сообщении #1089279 писал(а):
Sinoid в сообщении #1089274

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

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение09.01.2016, 15:27 
Аватара пользователя
lantza в сообщении #1089246 писал(а):
Известно, что если $p$ - простое число, и $(a,n)=1$, то $a^{p-1} \equiv 1 \pmod p$.

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

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение10.01.2016, 05:45 
Аватара пользователя
Brukvalub, ну и глазаст! Берём $n=1$ ...

 
 
 
 Re: Уточнение малой теоремы Ферма
Сообщение10.01.2016, 10:36 
Аватара пользователя

(Оффтоп)

bot в сообщении #1089517 писал(а):
Brukvalub, ну и глазаст!

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

 
 
 [ Сообщений: 14 ] 


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