Results 1 to 6 of 6

Thread: Computing Legendre Symbol

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    310

    Computing Legendre Symbol

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

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

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

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

    Does that mean I have to check through all of the integers in that set ($\displaystyle \{22, 2 \times 22, 3 \times 22, \cdots, 18 \times 22\}$) to see if they have a negative least residue in the set $\displaystyle \{-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
    3
    Quote Originally Posted by usagi_killer View Post
    Use Gauss' Lemma to compute $\displaystyle \left(\frac{22}{37}\right)$

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

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

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

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

    Cheers


    $\displaystyle \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 $\displaystyle O(p)$ steps to do all this checking for a prime $\displaystyle p$.

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

    One can compute the Legendre Symbol however, in $\displaystyle 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 $\displaystyle \left(\frac{2}{p}\right)_L = (-1)^{\frac{p^2-1}{8}}$ $\displaystyle (*)$, and the Quadratic reciprocity theorem $\displaystyle (**)$ for the remaining factor.

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

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

    $\displaystyle (**)$ If $\displaystyle p$ and $\displaystyle q$ are odd primes, then $\displaystyle \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
    310
    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 $\displaystyle \left(\frac{11}{37}\right)$ become $\displaystyle \left(\frac{37}{11}\right)$ and then to $\displaystyle \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 $\displaystyle \left(\frac{11}{37}\right)$ become $\displaystyle \left(\frac{37}{11}\right)$ and then to $\displaystyle \left(\frac{4}{11}\right)$?
    $\displaystyle \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 $\displaystyle 1$ or $\displaystyle -1$, it follows they are equal! $\displaystyle \left( \frac{11}{37} \right)_L = \left( \frac{37}{11} \right)_L$

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

  6. #6
    Senior Member
    Joined
    Apr 2009
    Posts
    310
    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: Apr 11th 2011, 07:55 PM
  2. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 12th 2010, 05:57 PM
  3. Legendre Symbol (5/p)
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Dec 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: Nov 3rd 2008, 02:34 PM

Search Tags


/mathhelpforum @mathhelpforum