Results 1 to 6 of 6

Math Help - Legendre Symbol (2/p)

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Arrow Legendre Symbol (2/p)

    "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 (-1)^{(p^2-1)/8} = (-1)^{(3^2-1)/8}." (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 (59^2-1)/8 and (3^2-1)/8 will have the same parity? How can we prove this?

    Thanks for explaining!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    "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 (-1)^{(p^2-1)/8} = (-1)^{(3^2-1)/8}." (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 (59^2-1)/8 and (3^2-1)/8 will have the same parity? How can we prove this?

    Thanks for explaining!
    because if p=8k + a, then \frac{p^2-1}{8}=\frac{64k^2+16ka+a^2-1}{8}=2b + \frac{a^2-1}{8}, where b=8k^2+2ka. so (-1)^{\frac{p^2-1}{8}}=(-1)^{2b} \times (-1)^{\frac{a^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Thank you!


    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 [(p^2 -1)/8] =2k
    <=> p^2 = 16k +1
    <=> p^2 ≡ 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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    Thank you!


    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 [(p^2 -1)/8] =2k
    <=> p^2 = 16k +1
    <=> p^2 ≡ 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!
    use what i already showed: if p=8k + a, then (-1)^{\frac{p^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}. now if p is an odd prime, then what are the possible values of a modulo 8? only 1, 3, 5 and 7.

    a simple calcultaion shows that \frac{a^2-1}{8} is odd for a = 3, 5 and it's even for a = 1, 7 and you're done.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by NonCommAlg View Post
    use what i already showed: if p=8k + a, then (-1)^{\frac{p^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}. now if p is an odd prime, then what are the possible values of a modulo 8? only 1, 3, 5 and 7.

    a simple calcultaion shows that \frac{a^2-1}{8} is odd for a = 3, 5 and it's even for a = 1, 7 and you're done.
    If we somehow already HAVE the answer on the right hand side, then it's easy to check that \frac{a^2-1}{8} is odd for a = 3, 5 and it's even for a = 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?

    Thanks for answering!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    If we somehow already HAVE the answer on the right hand side, then it's easy to check that \frac{a^2-1}{8} is odd for a = 3, 5 and it's even for a = 1, 7.


    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?

    Thanks for answering!
    well, you can consider p modulo 16 and the result would be the same but your job would be harder! the point here is that when you look at p modulo 8, say p \equiv a \mod 8, then

    p^2 \equiv a^2 \mod 16: if p = 8k + a, then p^2=64k^2 + 16ka + a^2=16(4k^2+ka)+a^2. so modulo 8 just makes things easier.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 1st 2011, 04:09 AM
  2. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 16th 2011, 07:55 PM
  3. [SOLVED] Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 31st 2010, 09:01 AM
  4. the legendre symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 02:34 PM
  5. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 7th 2008, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum