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

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


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

you have

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


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


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



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


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


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

  • 1
    $\begingroup$ Would anybody please verify this generalization? $\endgroup$ – lab bhattacharjee Nov 5 '12 at 20:03
  • $\begingroup$ It's interesting and semms right. Will you make it more readable, e.g. putting your claim right head before proving it? $\endgroup$ – puresky Dec 13 '12 at 7:44
  • $\begingroup$ 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$? $\endgroup$ – puresky Dec 13 '12 at 7:48
  • $\begingroup$ 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)$. $\endgroup$ – puresky Dec 13 '12 at 8:08
  • $\begingroup$ @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? $\endgroup$ – lab bhattacharjee Dec 13 '12 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.