Originally Posted by

**glman74** Hello,

I am learning some elementary number theory by myself, and am trying to solve the following:

Prove that the smallest $\displaystyle e$ such that $\displaystyle a^e \equiv 1 \ mod(p)$ must be a divisor of $\displaystyle p-1$

This what I have so far:

Let $\displaystyle e \equiv k \ mod(p-1)$.

$\displaystyle \Rightarrow \ e = k + r(p-1)$

$\displaystyle \Rightarrow \ a^{k + r(p-1)} \equiv 1 \ mod(p)$

From this we can show that $\displaystyle a^{k}\ mod(p) \equiv 1 \mod(p)$

$\displaystyle \Rightarrow \ k = 0 $

But it's not clear to me how to show that $\displaystyle e$ should be the **smallest** such integer.

I'd appreciate any help in understanding the above.

Regards

M