Results 1 to 13 of 13

Math Help - Jacobi Symbol

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Jacobi Symbol

    Evaluate the Jacobi symbol ((n−1)(n+1)/n) for any odd natural number n.

    Trying out some numbers, I THINK it alternates between 1 and -1, but how can we PROVE it formally?

    Any help is appreciated!


    [also under discussion in math link forum]
    Last edited by kingwinner; March 7th 2010 at 11:56 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     \left(\frac{(n-1)(n+1)}{n}\right) = \left(\frac{n-1}{n}\right)\left(\frac{n+1}{n}\right) = \left(\frac{-1}{n}\right)\left(\frac{1}{n}\right) = \left(\frac{-1}{n}\right)

    For  n odd,  \left(\frac{-1}{n}\right) = (-1)^\frac{n-1}{2} = \begin{cases} \;\;\,1 & \text{if }n \equiv 1 \pmod 4\\ -1 &\text{if }n \equiv 3 \pmod 4\end{cases} .

    For  n even, take  n=2k , then  \left(\frac{-1}{n}\right) = \left(\frac{-1}{2k}\right) = \left(\frac{-1}{2}\right)\left(\frac{-1}{k}\right) = \left(\frac{-1}{k}\right) = \begin{cases} \;\;\,1 & \text{if }k \equiv 1 \pmod 4\\ -1 &\text{if }k \equiv 3 \pmod 4\end{cases} .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
     \left(\frac{(n-1)(n+1)}{n}\right) = \left(\frac{n-1}{n}\right)\left(\frac{n+1}{n}\right) = \left(\frac{-1}{n}\right)\left(\frac{1}{n}\right) = \left(\frac{-1}{n}\right)

    For  n odd,  \left(\frac{-1}{n}\right) = (-1)^\frac{n-1}{2} = \begin{cases} \;\;\,1 & \text{if }n \equiv 1 \pmod 4\\ -1 &\text{if }n \equiv 3 \pmod 4\end{cases} .

    For  n even, take  n=2k , then  \left(\frac{-1}{n}\right) = \left(\frac{-1}{2k}\right) = \left(\frac{-1}{2}\right)\left(\frac{-1}{k}\right) = \left(\frac{-1}{k}\right) = \begin{cases} \;\;\,1 & \text{if }k \equiv 1 \pmod 4\\ -1 &\text{if }k \equiv 3 \pmod 4\end{cases} .
    Thank you!

    But I thought the Jacobi symbol is defined only for ODD positive integers at the bottom. In your proof, why is there a case where "n" is even??? How is this possible??
    Last edited by kingwinner; March 7th 2010 at 05:59 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    Thank you!

    But I thought the Jacobi symbol is defined only for ODD positive integers at the bottom. In your proof, why is there a case where "n" is even??? How is this possible??
    Oops! You're right!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    But I'm concerned with one special case. For the case n=1, ((n−1)(n+1)/n)=(0/1)

    Is (0/1)=1 or (0/1)=0 ?? Which one is the correct answer and why?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    But I'm concerned with one special case. For the case n=1, ((n−1)(n+1)/n)=(0/1)

    Is (0/1)=1 or (0/1)=0 ?? Which one is the correct answer and why?

    Thanks!
     \left(\frac{a}{n}\right) <br />
= \begin{cases}<br />
\;\;\,0\mbox{ if } \gcd(a,n) \ne 1<br /> <br />
\\\pm1\mbox{ if } \gcd(a,n) = 1\end{cases}

    So sub in  0 and  1 and see what you get.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
     \left(\frac{a}{n}\right) <br />
= \begin{cases}<br />
\;\;\,0\mbox{ if } \gcd(a,n) \ne 1<br /> <br />
\\\pm1\mbox{ if } \gcd(a,n) = 1\end{cases}

    So sub in  0 and  1 and see what you get.
    gcd(0,1)=1, so that rule says that (0/1)=+1 OR -1, but how do we know whether it is +1 or -1?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Jacobi symbol

    Apparently the answer is  0 . I haven't had too much exposure to the Jacobi symbol so I can't really tell you why. Check out the site for yourself though.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    \left( \frac{0}{1} \right)=1 because the set of prime factors of 1 is empty. if n > 1 is an odd integer, then \left( \frac{0}{n} \right)=0.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by NonCommAlg View Post
    \left( \frac{0}{1} \right)=1 because the set of prime factors of 1 is empty. if n > 1 is an odd integer, then \left( \frac{0}{n} \right)=0.
    Is there any reason why (0/1)=1?? Is this simply becuase by convention, we define it to be that way?
    1 has no prime factorization, so the product is empty. Is it conventional to define the "empty" product to be equal to +1??


    Also, is it true that, by definition, (a/1)=1 for any integer a?

    Can someone clarify this? Thank you!
    Last edited by kingwinner; March 8th 2010 at 02:37 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    Is there any reason why (0/1)=1?? Is this simply becuase by convention, we define it to be that way?
    1 has no prime factorization, so the product is empty. Is it conventional to define the "empty" product to be equal to +1??


    Also, is it true that, by definition, (a/1)=1 for any integer a?

    Can someone clarify this? Thank you!
    the answer is "yes" to both your questions.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by NonCommAlg View Post
    the answer is "yes" to both your questions.
    Is there any real reason why we define (a/1)=1 for any integer a?

    Why not define it to be 0? why not -1?

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

  13. #13
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by kingwinner View Post
    Is there any real reason why we define (a/1)=1 for any integer a?

    Why not define it to be 0? why not -1?

    Thanks for answering!
    It could perhaps be to avoid making annoying "special cases" in theorems.

    Example (which is not linked to your question, but just to show you) :

    Why do we define 1 as not being prime ?

    If we defined 1 as being prime, we would have to reformulate the Fundamental Theorem of Arithmetic in a rather heavy way, stating that "apart from adding 1's, the prime decomposition of a number is unique without taking into account the order" ...

    And since there is no particular reason to define 1 as a prime, we just prefer to say it isn't one
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Jacobi Symbol Properties
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 15th 2010, 06:08 PM
  2. Jacobi identity
    Posted in the Math Challenge Problems Forum
    Replies: 11
    Last Post: October 8th 2009, 12:20 AM
  3. [SOLVED] Jacobi Symbol
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 07:52 PM
  4. Jacobi Symbol
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 1st 2008, 07:04 PM
  5. Jacobi identity
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: August 6th 2006, 08:08 PM

Search Tags


/mathhelpforum @mathhelpforum