Order of $a+1$ if $a$ has order 3

Question

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.

Answer 1

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.

Answer 2

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