Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Legendre Symbol (2/p)

  1. Mar 7, 2010 #1
    "Let p be an odd prime, then we proved that the Legendre symbol

    Note that this can be easily computed if p is reduced modulo 8.
    For example, if p=59, then p3 (mod 8) and [tex](-1)^{(p^2-1)/8}[/tex] = [tex](-1)^{(3^2-1)/8}[/tex]" (quote from my textbook)

    Now I don't exactly see WHY p can be reduced modulo 8 without changing the answer.
    Why can we be so sure that [tex](59^2-1)/8[/tex] and [tex](3^2-1)/8[/tex] will have the same parity? How can we prove this?

    Thanks for explaining!
  2. jcsd
  3. Mar 7, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Isn't parity just another word for looking at the number modulo 2?
  4. Mar 7, 2010 #3
    Yes, but my textbook says modulo 8 which I don't understand.

    59≡3 (mod 2)
    => 592≡32 (mod 2)
    => 592-1 ≡ 32-1 (mod 2)
    But the trouble here is that there is no rule saying that I can multiply both sides by 1/8 (since 1/8 is not an integer)
  5. Mar 7, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's right. But, still, there is a rule that deals with division....

    By the way, it's the parity of (p2-1)/8, not the parity of p, so maybe you should start with that?
  6. Mar 7, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Or, I suppose, you could start with p=q mod 8 and work from there.
  7. Mar 8, 2010 #6
    Sorry, I don't get it...

    How should I begin?
  8. Mar 8, 2010 #7
    I guess I should look at two cases...(p2-1)/8 is even and the other case (p2-1)/8 is odd.

    <=> (p2-1)/8 is even
    <=> (p2-1)/8 = 2k
    <=> p2= 16k + 1
    <=> p2 ≡ 1 (mod 16)

    <=> p ≡ ??? (mod 8) <-----------this is the step I'm stuck...

    Can someone help me, please?
    Thank you!
  9. Mar 8, 2010 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can't you just try everything?
  10. Mar 9, 2010 #9
    How??? Can someone show me an example?

    How do you go from mod 8 to mod 16??
  11. Mar 9, 2010 #10
    To get the conrguence on the right hand side (i.e. precisely when (-1/p)=1), I will use the formula in the middle
    (-1/p)=1 <=> (p-1)/2 is even <=> (p-1)/2 = 2k <=> p=1+4k <=> p≡1 (mod 4)

    Following the same trick as above, to determine when (2/p)=1,
    set [tex][(p^2 -1)/8][/tex] =2k
    <=> [tex]p^2[/tex] = 16k +1
    <=> [tex]p^2[/tex] ≡ 1 (mod 16)

    <=> p ≡ ??? (mod 8) <-----I'm stuck on this step. Can someone explain how to go from the previous step to this step?

    Thanks for any help!
    Last edited: Mar 9, 2010
  12. Mar 9, 2010 #11
    If we somehow already HAVE the answer on the right hand side, then it's easy to check that [tex]\frac{p^2-1}{8}[/tex] is odd for p = 3, 5 and it's even for p = 1, 7. But to do this, we actually need to know the correct answers in the first place.

    But like in my textbook, it only proved the formula in the middle, without showing the conditions on the right, and I'm looking for a way to systematically derive the conditions on the right using the formula in the middle.

    Also, why should the conditions be p≡ (mod 8)? Why not p≡ (mod 16)?? (as analogy, for (-1/p), the formula has 2 in the denominator of the exponent, and we get mod 4 on the right)
    Having ONLY the formula in the middle, how to figure out what "modulus" to work with when we're trying to derive the conditions on the right?

    Can someone explain this, please?
    Thank you!
  13. Mar 9, 2010 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why not p≡ (mod 16)?
    Do it for that then. What do you get?
  14. Mar 12, 2010 #13
    We know p is an odd prime so there are only four cases which can be placed in two catagories: [tex]\pm1+8k; \pm3+8k[/tex] Of course, in some cases k could be even and represent things like 1+32k, etc.

    In the first case, squaring, subtracting off 1, and dividing by 8: [tex]\frac{\pm16k +64k^2}{8}}[/tex]

    This gives an even result which goes for 8k+1 and 8k +7. The second situation is negative.

    The factor 8 is introduced by use of a way to get the result. It comes from the sum formula for a product series of powers of -1: 1+2++++(p-1)/2 =(p-1)/2*(p+1)/2*1/2 =(p^2-1)/8. http://www.mathreference.com/num-mod,qr12.html

    _In that case we arrive at 2^(p-1)/2 = (-1)^(p^2-1)/8. Since 2^(p-1)/2 can be only +/1, and all squares are +1--which is half the cases, we have our result.
    Last edited: Mar 12, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook