Computing Legendre Symbol

**usagi_killer** · March 22nd 2011, 05:15 AM

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

**tonio** · March 22nd 2011, 08:04 AM

Originally Posted by usagi_killer

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

**PaulRS** · March 22nd 2011, 08:39 AM

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

**usagi_killer** · March 22nd 2011, 09:59 PM

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

**PaulRS** · March 23rd 2011, 02:27 AM

Originally Posted by usagi_killer

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)$

**usagi_killer** · March 23rd 2011, 08:46 PM

Ohhh I see, cheers thanks for that!

Thread: Computing Legendre Symbol

LinkBack

Thread Tools

Display

Computing Legendre Symbol

Similar Math Help Forum Discussions

Computing Legendre Symbol

Legendre symbol

Legendre Symbol (5/p)

Legendre Symbol

the legendre symbol

Search Tags