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

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