The problem is
If $a$ has order $3\pmod{p}$ where $p$ is an odd prime, show that $(a+1)$ has order $6\pmod{p}$.
My solution: $$a^3-1\equiv 0\pmod{p}$$ $$(a-1)(a^2+a+1)\equiv 0 \pmod{p}$$ $(a-1)$ cannot be divisible by $p$ because the order of $a$ is $3$, so, $$a^2+a+1\equiv 0\pmod{p}$$ $$(1)\qquad -a(a+1)\equiv 1\pmod{p}$$ Raising both sides to $6$, we get $$a^6(a+1)^6\equiv 1\pmod{p}\qquad (a+1)^6\equiv 1\pmod{p}$$ To show that $6$ is the smallest integer $s$ such that $$(2)\quad (a+1)^s\equiv 1\pmod{p}$$ we use contradiciton.
From $(1)$, $(a+1)^3\equiv -1\pmod{p}$ so $s=3$ doesn't satisfy $(2)$. If $s\in\{1,2,4\}$ and $s$ satisfies $(2)$, then that would imply $a^2\equiv 1\pmod{p}$ but that is a contradiction. If $s=5$, then $$(a+1)^6\equiv a+1\equiv 1\pmod{p}$$ but this is impossible since $a$ is a least residue.
Is my solution correct? If so, is there a better way of solving this problem ?
I'll take all congruences modulo $p$.
As you say, $a^2\equiv -a-1$. Therefore $(a+1)^2\equiv -a-1+2a+1\equiv a$ and $(a+1)^3\equiv a^2+a\equiv-1$. From this, we have $(a+1)^6\equiv1$, $(a+1)^2\not\equiv1$ and $(a+1)^3\not\equiv1$. Thus $a+1$ must have order $6$.