Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$.

I know the answer is $1$. For some reason every way I compute this legendre symbol I get $-1$:

$\left(\frac{150}{1009}\right) = -\left(\frac{75}{1009}\right)$ since we take an odd power of $2$ out

$ = -\left(\frac{25}{1009}\right)\cdot\left(\frac{3}{1009}\right)$ by multiplicativity

$= -\left(\frac{3}{1009}\right)$ since $25$ is a perfect square

$= -1$ since $1009 \mod 12$ is $1$ Theorem.

Using a Computer (Maple) I found that $\left(\frac{75}{1009}\right) = 1$. So my mistake must be in the first step.

  1. What is the formal rule for factoring out powers of $2$?
share|cite|improve this question
You gave it. An even number of $2$'s makes no difference, perfect square rule. So only issue is one $2$. Then $(2/p)=1$ if $p\equiv \pm 1\pmod{8}$, $-1$ if $p\equiv \pm 3\pmod{8}$. – André Nicolas Oct 26 '12 at 0:43
Just in case you're interested in a general rule how to calculate the Legendre symbol: – Martin Thoma Sep 1 '13 at 11:06
up vote 4 down vote accepted

The legendre symbol $(\frac{2}{p}) = 1$ when $p \equiv \pm1 \mod 8$. So compute $1009 \mod 8 = 1$ and then we see that there should not be a negative sign when factoring out the odd power of $2$ in the first step.

The rest is correct!

share|cite|improve this answer

Why not directly using what you mention in your answer $\,+\,$ quadratic reciprocity?

$$\left(\frac{150}{1009}\right)=\left(\frac{2}{1009}\right)\left(\frac{3}{1009}\right)\left(\frac{25}{1009}\right)=1\cdot 1\cdot\left(\frac{1009}{3}\right)= \left(\frac{1}{3}\right)=1$$

share|cite|improve this answer
Don, did you notice that answer is from OP? – Gerry Myerson Oct 26 '12 at 3:27
Hmmm...not quite, @GerryMyerson: first, I "take no powers of 2" out, and I use directly quadratic reciprocity for the one before the last equality, which the OP seems to evaluate somehow without this. – DonAntonio Oct 26 '12 at 3:30
Don, I mean when you write "what CodeKing told you," the "you" refers to ... CodeKing! – Gerry Myerson Oct 26 '12 at 3:40
Oh...hehe. No, I didnt notice. I'll edit my answer, thanks. – DonAntonio Oct 26 '12 at 3:42

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.