Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
The term that you want (instead of square remainder) is quadratic residue. – Brian M. Scott Feb 1 '13 at 22:46
up vote 5 down vote accepted

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!

share|cite|improve this answer
so all I've done was wrong and the right answer is that the order is 1? – Rachel Bernoulli Feb 1 '13 at 22:58
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
Yup, thanks just went all dumb back there, thanks for the help I appreciate it! :D – Rachel Bernoulli Feb 1 '13 at 23:11
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.