Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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… for other references. – lhf Nov 2 '12 at 0:51
up vote 6 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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