\[2 \le a \lt p\]
has order 3 modulo \[p\]
then \[a^3 \equiv 1 \; (mod \; p) \rightarrow a^3 -1 \equiv 0 \; (mod \; p)\]
. \[a^3-1\]
factorises as \[a^3-1=(a-1)(a^2+a+1)\]
so \[a^3 -1 =(a-1)(a^2+a+1) \equiv 0 \; (mod \; p)\]
. \[gcd(a-1,p)=1\]
so we can cancel the factor \[a-1\]
and get \[(a^2+a+1) \equiv 0 \; (mod \; p)\]
.Then
\[-a^2 \equiv a+1 \; (mod \; p)\]
. We have to raise the left hand side of this congruence to the power of 6 to obtain 1 modulo \[p\]
, so \[a+1\]
has order 6 modulo \[p\]
.