My proof that there are primitive roots modulo $p^2$

Question

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument?

---

Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must be a primitive root modulo $p$ as well, since it must have powers congruent to $1, 2, 3, ... p$ modulo $p^2$ and therefore those powers will also be congruent to $1, 2, 3, ... p$ modulo $p$.

So, we restrict our search to primitive roots modulo $p$. Let $r$ be such a root, and let's look for one of order $\phi(p^2)=p(p-1)$. Let $n$ be the order of $r$ modulo $p^2$. $n$ must divide $\phi(p^2)=p(p-1)$. But it must also be a multiple of $\phi(p)=p-1$, since $r^n\equiv 1$ modulo $p^2$ and therefore also modulo $p$. This implies that $n/(p-1)$ divides $p$ and thus either $n=p(p-1)$ or $n=(p-1)$.

So we just need to find out if all values of $r$ are of order $p-1$. Well, if $n$ is the order of $r$, then $r+p$ is another primitive root modulo $p$ and thus another candidate in our search. But $(r+p)^n\equiv r^n + pr^{n-1}\equiv1 + pr^{n-1}$ modulo $p^2$. But the $pr^{n-1}$ can't be zero because $r^{n-1}$ is a unit modulo $p^2$. So $(r+p)^n\not\equiv 1$, and in particular $r$ and $r+n$ have different orders.

So, if there is even one value of $r$ of order $p-1$, then there is another that isn't (namely $r+p$), and is therefore of order $p(p-1)$, and therefore is a primitive root. Of course, if there aren't any values of $r$ of order $p-1$, then they're all of order $p(p-1)$, so we still reach the desired result.

Answer 1

There is actually a serious flaw in this proof which I didn't spot. In the second paragraph I want to show that $r$ and $r+p$ are always of different orders. I write:

$$(r+p)^n\equiv r^n+pr^{n-1} \text{ modulo $p^2$}$$

I got the binomial formula wrong - it should be

$$(r+p)^n\equiv r^n+npr^{n-1} \text{ modulo $p^2$}$$

Thus we also need $n$ to be coprime with $p$ in order to conclude. In our case we really just want this argument to work when $n=p-1$, so we're fine, although we can't show the more general statement (which might be false) that the orders of $r$ and $r+p$ are always different.

This flaw becomes apparent when we try to generalize this argument to show that if there are primitive roots modulo $p^n$, there are primitive roots modulo $p^{n+1}$, in which case the argument fails if $p=2$, basically because to go from $2^2$ to $2^3$ we need to take $n=\phi(4)$, which is not coprime to $2$ at all.