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

If $p$ is prime, $a \in \Bbb Z$, $ord^a_p=3$. Then how to find $ord^{a+1}_p=?$

about $ord_n^a$ we know that is $(a,n)=1$ and smallest integer number as $d$ such that $a^d \equiv 1$ so $d=ord_n^a$

also we have: if $(a,n)=1 $, $a\equiv b \pmod n$then $gcd(b,n)=1$, $ord_n^b=ord_n^a$

if $k \in \Bbb N$ , $a^k \equiv 1 \pmod n$ iff $ord_n^a|k$

$a^{k_1} \equiv a^{k_2} \pmod n$ iff $k_1 \equiv k_2 \pmod { ord_n^a}$

$ord_n^a| \phi(n)$ it's my trying :

$a^3\equiv 1 \pmod p$ so $(a-1)(a^2 +a+1) \equiv 0 \pmod p$ so $a \equiv1 \pmod p$ that is impossible. so $a^2+a+1 \equiv 0 \pmod p$ so $a+1 \equiv -a^2 \pmod p$ how to find smallest $d$ such that $gcd(p,a+1)=1$ and $(a+1)^d \equiv 1 \pmod p$

also we have: $(-(a+1))^d \equiv (a^2)^d \equiv 1 $ also $ord^a_p=ord^{a^2}_p$so $d=3$, $(a+1)^3 \equiv -1 $ so $(a+1)^6 \equiv 1$ the problem is : Is $6$ smallest?

how to prove for $2,4,5$ that is not ? in fact how to prove :

$(a+1)^i \not \equiv 0 \pmod p$, $i=2,4,5$

share|cite|improve this question
up vote 0 down vote accepted

Hint: Note that since $(a+1)^6\equiv 1\pmod{p}$, the order of $a+1$ divides $6$. It follows that the only candidates to be eliminated are $1$, $2$, and $3$. The numbers $4$ and $5$ are not in the game.

Added: The fact that the order of $a+1$ is not $1$ is easy to prove, but should be proved. It comes down to the fact that the order of $a$ is $\ne 2$.

To show $a+1$ does not have order $2$, suppose that it does. Then from $(a+1)^2\equiv 1\pmod{p}$ we get that $a(a+2)\equiv 0\pmod{p}$. Now show that we cannot have $a\equiv -2\pmod{p}$.

To show that the order of $a+1$ is not $3$, suppose it is. Then from $(a+1)^3\equiv 1\pmod{p}$ we obtain $3a^2+3a+1\equiv 0\pmod{p}$. But $p^2+p+1\equiv 0\pmod{p}$. From this one can quickly obtain a contradiction.

share|cite|improve this answer
case$3$ is impossible by attention to question.but why $4,5$ is impossible? also if $a \equiv -2$ then $-8 \equiv 1$ that is true for $p=3$ – elham Mar 22 '13 at 19:57
Of course Case $3$ is impossible, but the proof is not built into the wording of the question. The answer said why $4$ and $5$ are impossible. Suppose say that the order is $4$. You showed that $(a+1)^6\equiv 1\pmod{p}$. In general, if $b^k\equiv 1\pmod{p}$, then the order of $b$ divides $k$. But $4$ does not divide $6$. Same argument works for $5$. To show that the order $b$ divides $k$, use a general argument from group theory. Or let $e$ be the order, and let $k=qe+r$, $0\le r\lt e$. Since $b^k\equiv 1$ and $b^e\equiv 1$, we get $b^r\equiv 1$. Unless $r=0$, we get contradiction. – André Nicolas Mar 22 '13 at 20:06

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.