# 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\,$.

-
This is a standard theorem which appears in almost all books on number theory. –  lhf Nov 2 '12 at 0:46
Could you recommend a book? I was asked to prove this in the exam today, it is not in our lecture notes. –  user31899 Nov 2 '12 at 0:50
See for instance LeVeque's Fundamentals of Number Theory. See also math.stackexchange.com/questions/42755/order-of-cyclic-groups/… for other references. –  lhf Nov 2 '12 at 0:51

Lets see if I remember it:

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

Since

$$g^{ord{g}}= 1 \mod p^2$$

you have

$$g^{ord{g}}= 1 \mod p$$

thus

$$p-1 | ord{g} | (p^2-p)$$

Similarly

$$p-1 | ord(g+p) | (p^2-p)$$

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

$$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} \mod p^2$$

thus

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

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

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

Thus

$$ord(g+p) \neq p-1$$

Combining this with $p-1 | ord(g+p) | (p^2-p)$ you are done.

-

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)$

-
Would anybody please verify this generalization? –  lab bhattacharjee Nov 5 '12 at 20:03
It's interesting and semms right. Will you make it more readable, e.g. putting your claim right head before proving it? –  puresky Dec 13 '12 at 7:44
While you are discussing whether $p\mid \left(aq+dr\right)$ or not, you might have missed one situation that $p\not\mid q$ but $p\mid d$? –  puresky Dec 13 '12 at 7:48
And will it be better to mention that, because $ord_{p^{s+1}}(a+p^sr+p^{s+1}k)=ord_{p^{s+1}}(a+p^sr)$, then we only need discuss $r\in [0,p)$. –  puresky Dec 13 '12 at 8:08
@puresky, we know congruent numbers are not different, hence they have same multiplicative order, here $a+p^sr+p^{s+1}k\equiv a+p^sr\pmod{p^{s+1}}.$ Btw, exactly, where do you want mention it? –  lab bhattacharjee Dec 13 '12 at 8:54