Order of numbers modulo $p^2$

Solution 1:

Let's see if I remember it:

Assume that $\text{ord}(g) \neq p^2-p$. We will prove $\text{ord}(g+p) =p^2-p$.

Since

$$g^{\text{ord}(g)}\equiv 1 \pmod {p^2}, $$

you have

$$g^{\text{ord}(g)}\equiv 1 \pmod p.$$

Thus,

$$p-1 \mid \text{ord}(g),\,\text{ord}(g) \mid p^2-p.$$

Similarly

$$p-1 \mid \text{ord}(g+p),\,\text{ord}(g+p) \mid p^2-p.$$

Now, since $\text{ord}(g) \neq p^2-p$ and $p-1 \mid\text{ord}(g)$, using the fact that $p$ is prime, it follows that

$$\text{ord}(g)=p-1.$$

Then,

$$(g+p)^{p-1}=\sum_{k=0}^{p-1} \binom{p-1}{k} p^k g^{p-1-k} \equiv\binom{p-1}{1} p g^{p-2}+g^{p-1} \pmod {p^2}.$$

Thus,

$$(g+p)^{p-1} \equiv (p-1)pg^{p-1}+1 \pmod {p^2}.$$

Since $(p-1)pg^{p-1}$ is not divisible by $p^2$, it follows that

$$(g+p)^{p-1} \neq 1 \pmod{ p^2}.$$

Thus,

$$\text{ord}(g+p) \neq p-1.$$

Combining this with $\text{ord}(g+p) \mid p^2-p$, you are done.