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

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$?
-
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.com/calculate-legendre-symbol – Martin Thoma Sep 1 '13 at 11:06

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$$

-
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

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!

-