Упражнение на малую теорему Ферма

[lim(f(x))]

При $p\not{\mid}\ a\quad a^{p-1} \equiv 1\ (mod\ p)$
Докажите общую теорему: наименьшее число $e$, для которого $a^e\equiv 1\ (mod\ p)$, должно быть делителем $p - 1$. [Указание: произведите деление $p − 1$ на $e$, получая $p - 1 = ke + r$, где $0 \leq r < e$, и дальше воспользуйтесь тем обстоятельством, что $ a^{p-1} \equiv a^e \equiv 1\ (mod\ p) $. ]


Я не понимаю, зачем делить $p$ на $e$.
Умножая $a$ само на себя до $a^e$, мы должны встретить $e-1$ различных остатков. Полагаю, что эти остатки повторяются каждые $e$ умножений $a$ само на себя, то есть $a^{e+x} \equiv a^{2e+x}\equiv a^{3e+x}\ (mod\ e)$ и т.д., но не знаю, как это доказать. Если это доказано, то только степени $a^x$, c $x$, кратным $e$, дают в остатке 1, и $p-1$ тоже делится на $e$.

[xmaister]

Положим, что $\gcd (a,p)=1$. Пусть $a$ принадлежит показателю $\delta$ по модулю $p$. Тогда $a^n\equiv 1\pmod{p}\Leftrightarrow \delta |n$. Действительно, если $\delta |n$, то всё ясно. Разделим $n$ на $\delta$ с остатком, будем иметь $n=q\delta +r,r<\delta$, далее получите противоречие с минимальностью $\delta$.

[lim(f(x))]

Спасибо, я забыл, что $a^{e+x}=a^e a^x$ и $ab\equiv 1$ только когда $a\equiv 1$ и $b\equiv 1$

[xmaister]

lim(f(x)) в сообщении #607150 писал(а):

$ab\equiv 1$ только когда $a\equiv 1$ и $b\equiv 1$

Это не верно. $a\equiv 3\pmod 7,b\equiv 5\pmod 7$

[xmaister]

Если Вам не нравятся рассуждения, которые я изложил выше, то можно их немного видоизменить. Рассмотрим группу $\mathbb{Z}_p^{\times}$ и $a\in \mathbb{Z}_p^{\times}$. Тогда, в силу теоремы Лагранжа $\mathrm{ord}(a)|p-1$.