Order of numbers modulo $p^2$ Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that either $\,p+g\,$ or $\,g\,$ has order $\,p^2-p\,\pmod{p^2}$. 
Remark: We know $\,g^{\frac{p-1}{2}}=-1\,$.
 A: 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.
A: Let $$ord_{p^s}a=d\iff a^d\equiv 1\pmod {p^s}=1+p^sq$$ where $q$ is some integer,
and $ord_{p^{s+1}}(a)=D$
$\implies a^D\equiv 1\pmod{p^{s+1}}\equiv 1\pmod{p^s}\implies d\mid d$ i.e., $D=d\cdot k_1$(say) where $k_1$ is a positive integer.
Now, $a^{pd}=(a^d)^p=(1+p^sq)^p=1+\binom p 1 p^sr+\binom p 2 (p^sr)^2+\cdots+(p^sq)^p \equiv 1\pmod{p^{s+1}}$
So, $\implies D\mid p\cdot d,$ i.e., $p\cdot d=k_2\cdot D,$(say) where $k_1$ is a positive integer.
Mutiplying $p\cdot d\cdot D=k_2\cdot D\cdot d\cdot k_1\implies k_1\cdot k_2=p$
If $k_1=1,k_2=p,D=d\cdot k_1=d$ and if $k_2=1,k_1=p,D=d\cdot k_1=p\cdot d$
So, $ord_{p^s}a=d\implies ord_{p^{s+1}}a=d$ or $p\cdot d$.
Let us consider $a+p^sr$  where $0\le r<p$ is an integer
Now, $(a+p^sr)^d=a^d+\binom d 1a^{d-1}p^sr+\binom d 2a^{d-2}(p^sr)^2+\cdots$
$\equiv 1+p^sq+da^{d-1}p^sr\pmod {p^{s+1}}$ if $2s\ge s+1$ i.e., if $s\ge 1$
$$ord_{p^{s+1}}(a+p^sr)=d\iff p^{s+1}\mid\left(p^sq+da^{d-1}p^sr\right) $$ i.e., if  $p\mid \left(q+da^{d-1}r\right)$ or if  $p\mid \left(aq+dr\right)--->(1)$ as $(a,p)=1$
(1)If $p\mid q,p$ must divide $d\cdot r$
$\space\space$(a) if $p\mid r,r=0$ as $r<p\implies ord_{p^{s+1}}(a)=d$ and $ord_{p^{s+1}}(a+p^sr)=pd$ for $0<r<p$
$\space\space$(b) if $p\mid d, ord_{p^{s+1}}(a+p^sr)=d$ for $0\le r<p$
(2)If p$\not\mid q,$ i.e., if  $(p,q)=1,p$ can not divide $d\cdot r$ as $p\mid \left(aq+dr\right)$
So, $d\cdot r\equiv -aq\pmod p$ which clearly has a unique solution of $r\in [1,p)=R(say),$ then $ord_{p^{s+1}}(a+p^sR)=d$ and $ord_{p^{s+1}}(a+p^sr)=pd$ for $0\le r<p$ and $r\ne R$.
Here in this problem, $s=1,ord_pg=d=p-1$ so, $p\not\mid d$
So, Case $1(b)$ does not arise here.
From $1(a),$  if $ord_{p^{1+1}}g=d=p-1,  ord_{p^2}(g+pr)=pd=p(p-1)$ for $0<r<p$
From $(2),ord_{p^{1+1}}g\ne d\implies ord_{p^2}g=pd=p(p-1) $ and for exactly, one value of $r\in [1,p)=R($ which may be $1,also),ord_{p^{1+1}}(g+pR)=d$ and the rest will have of order $pd=p(p-1)$
