# find the order of $a \pmod p$ when we know that $p$ is prime and $p\not=2$ and $p\mid a^3+1$ but $p\nmid a+1$

I'm asked to find the order of $a \pmod p$ when we know that $p$ is prime and $p\not=2$ and $p\mid a^3+1$ but $p\nmid a+1$

my work so far: $p\mid a^3+1=(a+1)(a^2-a+1)\;\rightarrow\; p\mid a^2-a+1$ so $a^2\equiv a-1 \pmod p$ and so $a-1$ is a quadratic residue and we get $\left(\frac{a-1}p\right)$ which is the Legendre symbol and thus $a^{(p-1)/2}\equiv 1 \pmod p$ and we get $a^{(p-1)/2}=a^{2(p-1)/2}=a^{p-1}\equiv 1 \pmod p$

and I have no idea how to go from here, I mean i need to prove that $p-1$ is the order, right?

-
The term that you want (instead of square remainder) is quadratic residue. – Brian M. Scott Feb 1 '13 at 22:46

Hint: We have $a^3\equiv -1\pmod{p}$, so $a^6\equiv 1\pmod{p}$. So the order of $a$ divides $6$. Not too many candidates!
What you did happened not to lead to a solution, you reached $a^{p-1}\equiv 1\pmod{p}$, which is immediate (Fermat). No, the order is not $1$. It is $6$. For your solution, after writing what I did, you need to explain how you know that order is not $1$, not $2$, not $3$. I could write out why it is not $1$, not $2$, not $3$. But it's really quite easy, you should give it a try. – André Nicolas Feb 1 '13 at 23:06
Since $a^3+1$ can be factored, you factored it. But it looks nicer just as it is. – André Nicolas Feb 1 '13 at 23:14