The smallest power e in Fermat's little theorem

Question

I have an exercise that is connected to Fermat's little theorem. I should prove that the smallest positive integer $e$ for which $a^e \equiv {1} \pmod{p}$ must be a divisor of $p - 1$. Also, there are some hints: Divide $p - 1$ by $e$, obtaining $p - 1 = ke + r$, where $0 \le r \lt e$, and use the fact that $a^{p-1} \equiv a^e \equiv 1 \pmod{p}$.

I have no ideas except $a^{ke + r} \equiv a^e \equiv 1$.

I will be appreciated for any help and hints.

Answer 1

You want to prove $r=0$, so assume otherwise. Then $a^r\equiv a^{ke+r}\equiv 1$, contradicting the definition of $e$.

Answer 2

A variant approach:

We may suppose $a\not\equiv 0\mod p$. Consider the homomorphism \begin{align} f:(\mathbf Z, +)&\longrightarrow (\mathbf Z/p\mathbf Z)^\times, \\ n & \longmapsto f(n)=a^n. \end{align} $e$ is the positive generator of the subgroup $\ker f$.

Answer 3

Note that $$r=(p-1)-ke$$

$$a^{p-1} \equiv a^e \equiv 1 \pmod{p}$$

Thus $$a^r= a^{p-1}a^{-ke}\equiv 1 \pmod{p}$$

Since $0\le r<e$ and $e$ is the smallest positive integer satisfying $a^e \equiv 1 \pmod{p}$ we have $r=0$ and $(p-1)=ke$