Show that if a has order 3 (mod p), then a + 1 has order 6 (mod p).
$\displaystyle (a+1)^6=[(a+1)^3]^2=[a^3+3a^2+3a+1]^2=(2+3a(a+1))^2=$ $\displaystyle 4+12a(a+1)+9a^2(a+1)^2=$ $\displaystyle 4+12a^2+12a+9a^4+18a^3+9a^2=$ $\displaystyle 9a+18+21a^2+12a+4=21a^2+21a+22=
21(a^2+a+1)+1=0+1=1$ .
Now check that $\displaystyle (a+1)^3=-1$ and deduce what you want (remember that $\displaystyle a^3-1=(a-1)(a^2+a+1)$ ... )
Tonio
Ps. The proof that $\displaystyle (a+1)^k\neq 1\,\,\forall\, 1\leq k\leq 5$ is pretty interesting in itself.