# The smallest power e in Fermat's little theorem

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.

• What can you say about $a^r$? – Jaap Scherphuis Sep 3 '18 at 11:17
• I see that it's also is congruent to 1 modulo p. I mean that $a^r \equiv 1 \pmod{p}$ – E. Shcherbo Sep 3 '18 at 11:18
• Keep going. Use what you assume about $e$. – John Brevik Sep 3 '18 at 11:20
• $e$ is the smallest integer for which $a^e \equiv 1 \pmod{p}$ is truth. So, $r$ is either greater than $e$ (that is not impossible) or ... I don't know how to continue. – E. Shcherbo Sep 3 '18 at 11:27

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

• I'm sorry if it's stupid, but I can't understand why $r = 0$ is an answer. $0$ is also less than $e$ and $a^0$ is also congruent to $1$ modulo $p$: $a^0 = 1 \equiv 1 \pmod{p}$. – E. Shcherbo Sep 3 '18 at 11:34
• @E.Shcherbo Since any alternative for $r=0$ would contradict $e$ being the least positive $n$ satisfying $a^n\equiv 1$, we must have $r=0$. – J.G. Sep 3 '18 at 11:35
• Ok, I think I got you. The keyword is positive. $0$ is not positive, so, $r$ is either greater than $e$, that is not impossible, or $0$. Are these thoughts correct? – E. Shcherbo Sep 3 '18 at 11:39
• @E.Shcherbo Well, $r$ is already $<e$ because it's defined as a remainder, so you its being positive would yield a contradiction automatically. As soon as you've eliminated that option, $r=0$ is all that's left. – J.G. Sep 3 '18 at 11:48

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$

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$.