Order of $a+1$ if $a$ has order 3 Suppose $a \in \mathbb{Z}$ has order $3$ modulo some prime $p$ with $\gcd(p,a)=1$. Why does it follow that $a+1$ has order $6$? I can show that $(a+1)^6 \equiv1 \pmod p$ because $3 \mid p-1$ and hence $p=6k$ for some $k \in \mathbb{Z}$. But why can't the order be smaller than $6$? I guess I have to find some contradiction to the order of $a$ being $3$ but I'm stuck on how to continue.
 A: As noted, since $p$ is prime, and $a$ has order $3$, mod $p$, it follows that $p\equiv 1\;(\text{mod}\;3)$.

In particular, $p > 2$, so $-1\not\equiv 1\;(\text{mod}\;p)$.

Also, since $a$ has order $3$, mod $p$, we get 
\begin{align*}
&\!\!
\begin{cases}
a^3\equiv 1\;(\text{mod}\;p)\\[4pt]
a\not\equiv 1\;(\text{mod}\;p)\\[4pt]
\end{cases}
\\[10pt]
\text{Then}\;\;&a^3\equiv 1\;(\text{mod}\;p)\\[4pt]
\implies\;&a^3-1\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&(a-1)(a^2+a+1)\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&a^2+a+1\equiv 0\;(\text{mod}\;p)\qquad\text{[since $a\not\equiv 1\;(\text{mod}\;p)$]}\\[10pt]
\text{Then}\;\;&(a+1)^3\equiv a^3+3a^2+3a+1\;(\text{mod}\;p)\\[4pt]
&\phantom{(a+1)^3}\equiv 3a^2+3a+2\;(\text{mod}\;p)\\[4pt]
&\phantom{(a+1)^3}\equiv 3(a^2+a+1)-1\;(\text{mod}\;p)\\[4pt]
&\phantom{(a+1)^3}\equiv -1\;(\text{mod}\;p)\\[10pt]
\implies\;&(a+1)^6\equiv 1\;(\text{mod}\;p)\\[4pt]
\end{align*}
so the order of $a+1$, mod $p$, divides $6$, and is not equal to $3$.

It remains to show that the order of $a+1$, mod $p$, is not equal to $1$ or $2$.

For this, it will suffice to show $(a+1)^2\not\equiv 1\;(\text{mod}\;p)$.
\begin{align*}
\text{Then}\;\;(a+1)^2&\equiv a^2+2a+1\;(\text{mod}\;p)\\[4pt]
&\equiv (a^2+a+1)+a\;(\text{mod}\;p)\\[4pt]
&\equiv a\;(\text{mod}\;p)\\[4pt]
&\not\equiv 1\;(\text{mod}\;p)\\[4pt]
\end{align*}
It follows that the order of $a+1$, mod $p$, is $6$, as was to be shown.
A: Since $a$ has order $3$ we know that $a\not\equiv -1, 0, 1\pmod p$.


*

*$a\not\equiv -1\implies a+1\not\equiv 0$,  therefore $a+1$ is still invertible modulo $p$ (so it does have an order in the multiplicative group).

*$a\not\equiv 0\implies a+1\not\equiv 1\pmod p$, so the order of $a+1$ is not $1$.

*$a\not\equiv 1\  \wedge (a-1)(a^2+a+1)\equiv 0\implies a^2+a+1\equiv 0$
Now from $a^2+a+1\equiv 0$ you can simplify $(a+1)^2$ into $a$, and you know that $a\not\equiv 1$ so the order is not $2$. 
You can also simplify $(a+1)^3$ into $-1$, which is not $1$ since there are no elements of order $3$ in $\Bbb Z/2\Bbb Z^\star.$
The order has to divide $6$ as you correctly observed, so it is equal to $6$.
