# Proving that if $a$ is a primitive root mod $p$, then $a$ or $a+p$ is a primitive root mod $p^2$

Let $a$ be a primitive root mod $p$. Prove that $a$ or $a+p$ is a primitive root mod $p^2$.

This is what I did so far:
$\phi(p^2)=p^2-p=p(p-1)$.

$(a+p)^{p-1}=a^{p-1} +(p-1)a^{p-2}p \pmod{p^2}$.

I'm stuck here...

Hint: A primitive root $g \pmod{p}$ is also a primitive root $\pmod{p^2}$ if and only if $g^{p-1} \not \equiv 1 \pmod{p^2}$. Can $a^{p-1}$ and $(a+p)^{p-1}$ both be congruent to $1 \pmod{p^2}$?