Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question
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}$. –  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 –  moose Sep 1 '13 at 11:06
add comment

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

share|improve this answer
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
add comment
up vote 3 down vote accepted

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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