Proving that order of primitive root is in either $p-1$ either $p(p-1)$

Question

So let r be primitive root of an odd prime p.

I have to prove:

$$o_{p^2}(r) \in \{ p-1, p (p-1) \}$$

So I know:

$$o_{p^2}(r)= x , r^x\equiv 1 (mod \ p^2)$$ where x is the smallest such.

But I don't know how to prove this.

Any help would be appreciated.

Answer 1

For $r^x\equiv1\pmod {p^2}$, it is necessary that $r^x\equiv1\pmod p$, so that $(p-1)\mid x$. The order of $r$ modulo $p^2$ must be a multiple of $p-1$.

By Euler's generalisation of Fermat's theorem, $r^{p(p-1)}\equiv1 \pmod{p^2}$. The order of $r$ modulo $p^2$ must be a divisor of $p(p-1)$.