Следствие из теоремы Ферма

[ean]

Привет,

Я опять с очевидной, по всей видимости задачей.
Требуется доказать следующее утверждение: наименьшее число $e$, для которого $a^e\equiv 1(mod p)$, где $p$ - простое число, не делящее $a$, должно быть делителем $p-1$.
Рассуждения следующие:
Возьмём минимальное $e$ большее 0, для которого $a^e\equiv 1(mod p)$. Это $e$ меньше $p$. Разделим $p-1$ на $e$: $p-1=ke+r$, где $k$ - целое, а $r$ подчиняется следующему неравенству $0\leqslant r < e$.
$a^{p-1} \equiv 1 \equiv a^e \Rightarrow a^{p-1} \equiv a^e \Rightarrow a^{ke+r} \equiv a^e \Rightarrow a^{ke+r}-a^e \equiv 0 \Rightarrow a^e(a^{(k-1)e+r}-1) \equiv 0 \Rightarrow a^{(k-1)e+r}-1 \equiv 0 \Rightarrow a^{(k-1)e+r} \equiv 1$.
Предпоследнее преобразование делается исходя из того, что если ab \equiv 0$, то либо a \equiv 0$ либо b \equiv 0$. В нашем случае a^e \equiv 0$ - неверно по условию.
Проведём вышеописанную операцию k раз и получим $a^{(k-k)e+r} \equiv 1 \Rightarrow a^r \equiv 1$. Однако $e$ - наименьшее число, что $a^e\equiv 1$ и $r<e$. Следовательно $r=0$, то есть $p-1=ke$, что и требовалось доказать.
Скажите, верны ли мои рассуждения? Можно ли доказать это утверждение проще?

[Someone]

ean в сообщении #339575 писал(а):

Можно ли доказать это утверждение проще?

Так как $a^e\equiv 1\pmod{p}$, то $a^{ke+r}\equiv a^{ke}a^r\equiv (a^e)^ka^r\equiv 1^ka^r\equiv a^r\pmod{p}$.

[ean]

Спасибо.