Show that if $a$ has order $3\bmod p$ then $a+1$ has order $6\bmod p$.

Solution 1:

Note that if $a=1$, $a$ has order $1$. Thus, we can assume $a\ne1$. Furthermore, $p\ne2$ since no element mod $2$ has order $3$. Therefore, $-1\ne1\pmod{p}$. $$ \begin{align} (a+1)^3 &=a^3+3a^2+3a+1\\ &=1+3a^2+3a+1\\ &=-1+3(1+a+a^2)\\ &=-1+3\frac{a^3-1}{a-1}\\ &=-1 \end{align} $$ Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn). $$ \begin{align} (a+1)^2 &=a^2+2a+1\\ &=a+(a^2+a+1)\\ &=a+\frac{a^3-1}{a-1}\\ &=a\\ &\ne1 \end{align} $$ Therefore, $(a+1)^2\ne1$.

Thus, $(a+1)$ has order $6$.

Solution 2:

ord_$pa=3\iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$

But $p\not\mid (a-1)$ as ord_$pa=3 $

$\displaystyle\implies a^2+a+1\equiv0\pmod p$ $\displaystyle\iff a(a+1)\equiv-1\pmod p$

Method $1:$

$\implies a^3(a+1)^3\equiv-1\pmod p\implies (a+1)^3\equiv-1$ and $(a+1)^6\equiv1$

$\implies $ord_$p(a+1)\mid 6$ but does not divide $3$

If ord_$p(a+1)\mid 2, (a+1)^2\equiv1\pmod p$ and $a^2(a+1)^2\equiv1\pmod p\implies a^2\equiv1$ which is impossible as ord$_pa=3$

$\implies $ord$_p(a+1)=6$

Method $2:$

$\displaystyle a(a+1)\equiv-1\pmod p\iff a+1\equiv (-a)^{-1}\pmod p$

Again as $a^3\equiv1\pmod p, (-a)^3=-a^3\equiv-1\pmod p\implies (-a)^6\equiv1\implies $ord$_p(-a)=6$

Using this, ord$_p\{(-a)^{-1}\})=$ord$_p(-a)=6$