2
$\begingroup$

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
    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}$.2012-10-26
  • 0
    Just in case you're interested in a general rule how to calculate the Legendre symbol: http://martin-thoma.com/calculate-legendre-symbol/2013-09-01

2 Answers 2

4

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!

0

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
    Don, did you notice that answer is from OP?2012-10-26
  • 0
    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.2012-10-26
  • 0
    Don, I mean when you write "what CodeKing told you," the "you" refers to ... CodeKing!2012-10-26
  • 0
    Oh...hehe. No, I didnt notice. I'll edit my answer, thanks.2012-10-26