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$?
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Oct 26 '12 at 0:43
  • $\begingroup$ Just in case you're interested in a general rule how to calculate the Legendre symbol: martin-thoma.com/calculate-legendre-symbol $\endgroup$ – 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.

The rest is correct!


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

  • 1
    $\begingroup$ Don, did you notice that answer is from OP? $\endgroup$ – Gerry Myerson Oct 26 '12 at 3:27
  • $\begingroup$ 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. $\endgroup$ – DonAntonio Oct 26 '12 at 3:30
  • $\begingroup$ Don, I mean when you write "what CodeKing told you," the "you" refers to ... CodeKing! $\endgroup$ – Gerry Myerson Oct 26 '12 at 3:40
  • $\begingroup$ Oh...hehe. No, I didnt notice. I'll edit my answer, thanks. $\endgroup$ – DonAntonio Oct 26 '12 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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