Results 1 to 6 of 6

Math Help - Computing Legendre Symbol

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Computing Legendre Symbol

    Use Gauss' Lemma to compute \left(\frac{22}{37}\right)

    I know how to start this question but just unsure how to finish it, my working is as follows:

    \left(\frac{22}{37}\right) = (-1)^{\mu} where \mu is the number of negative least residues of the integers \{22, 2 \times 22, 3 \times 22, \cdots, 18 \times 22\} \pmod{37}

    the set of least residues mod 37 is \{-18, -17, \cdots -1, 1, \cdots, 17, 18\}

    Does that mean I have to check through all of the integers in that set ( \{22, 2 \times 22, 3 \times 22, \cdots, 18 \times 22\}) to see if they have a negative least residue in the set \{-18, -17, \cdots -1, 1, \cdots, 17, 18\} ? Because that would take a VERY long time, is there a faster way?

    Cheers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by usagi_killer View Post
    Use Gauss' Lemma to compute \left(\frac{22}{37}\right)

    I know how to start this question but just unsure how to finish it, my working is as follows:

    \left(\frac{22}{37}\right) = (-1)^{\mu} where \mu is the number of negative least residues of the integers \{22, 2 \times 22, 3 \times 22, \cdots, 18 \times 22\} \pmod{37}

    the set of least residues mod 37 is \{-18, -17, \cdots -1, 1, \cdots, 17, 18\}

    Does that mean I have to check through all of the integers in that set ( \{22, 2 \times 22, 3 \times 22, \cdots, 18 \times 22\}) to see if they have a negative least residue in the set \{-18, -17, \cdots -1, 1, \cdots, 17, 18\} ? Because that would take a VERY long time, is there a faster way?

    Cheers


    \displaystyle{\left(\frac{22}{37}\right)=\left(\fr  ac{2}{37}\right)\left(\frac{11}{37}\right)=(-1)\left(\frac{37}{11}\right)=(-1)(4)=-1

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Well, yes it's slow, it'd take O(p) steps to do all this checking for a prime p.

    (To compute \left(\frac{r}{p}\right)_L you start off with r, you transform it into the corresponding least residue , then add r again and repeat..., counting the negative ones you find on your way )

    One can compute the Legendre Symbol however, in O\left(\log p\right) steps, by using Euler's Criterion and fast modulo exponentiation.

    ( I am considering multiplication and modulo operations as constant time, they are not though -but can still be done pretty fast, much better than linear time.)

    As to what Tonio did, he used that the legendre symbol is multiplicative, then the well known \left(\frac{2}{p}\right)_L  = (-1)^{\frac{p^2-1}{8}} (*), and the Quadratic reciprocity theorem (**) for the remaining factor.

    There's a typo there , it should be \left(\frac{37}{11}\right)_L = \left(\frac{4}{11}\right)_L = 1 since luckily 4 is a square.

    (*) The formula \left(\frac{2}{p}\right)_L  = (-1)^{\frac{p^2-1}{8}} can be proved using Gauss' Lemma.

    (**) If p and q are odd primes, then \left(\frac{p}{q}\right)_L\cdot \left(\frac{q}{p}\right)_L = (-1)^{\frac{(p-1)\cdot (q-1)}{4}} , for more details read here
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    Thanks for the help guys

    And also @PaulRS, I know how he got the first factor now, but I am still a bit unsure on how to apply the Quadratic reciprocity theorem on the second factor, ie, how does \left(\frac{11}{37}\right) become \left(\frac{37}{11}\right) and then to \left(\frac{4}{11}\right)?

    Cheers
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by usagi_killer View Post
    And also @PaulRS, I know how he got the first factor now, but I am still a bit unsure on how to apply the Quadratic reciprocity theorem on the second factor, ie, how does \left(\frac{11}{37}\right) become \left(\frac{37}{11}\right) and then to \left(\frac{4}{11}\right)?
    \left( \frac{11}{37} \right)_L \cdot \left( \frac{37}{11} \right)_L = (-1)^{\frac{(37-1)\cdot (11-1)}{4}}=1 now since the factors are either 1 or -1, it follows they are equal! \left( \frac{11}{37} \right)_L = \left( \frac{37}{11} \right)_L

    Now, 37\equiv 4 (\bmod.11)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    Ohhh I see, cheers thanks for that!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 11th 2011, 07:55 PM
  2. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 12th 2010, 05:57 PM
  3. Legendre Symbol (5/p)
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 11th 2009, 03:37 AM
  4. Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 02:56 PM
  5. the legendre symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 02:34 PM

Search Tags


/mathhelpforum @mathhelpforum