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

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$

-

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.

-
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