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

Question

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

Answer 1

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!

Answer 2

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