Legendre symbol

**fir2011** · September 29th 2011, 05:01 PM

Hey guys, I need a bit of help here.

1. Show that the equation $x^2-71y^2=19$ has no integer solution using Legendre symbol.

So $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \pmod{p}$

$\left(\frac{71}{19}\right) \equiv 71^{(19-1)/2}\ \pmod{19}$

$71^9\ \pmod{19} = 18 = -1$

So because it equals $-1$ , $71$ is a quadratic non-residue modulo $19$ and so there is no integer solution to $x^2-71y^2=19$ .

Is this enough to show no integer solutions?

2. Evaluate the Legendre symbol $\left(\frac{p^2-1}{p}\right)$ for odd prime $p$ .

So $\left(\frac{p^2-1}{p}\right) \equiv (p^2-1)^{(p-1)/2}\ \pmod{p}$

What is the formal way to go from here?
I have evaluated this for several cases of odd prime p and kind of see a pattern.

Also, this value alternates between -1 and 1 for odd numbers.

Any help guys?

Thanks for your help.

**alexmahone** · October 1st 2011, 04:04 AM

1. $x^2-71y^2=19 \implies x^2\equiv 19 \pmod{71}$

$\left(\frac{19}{71}\right)=$ $\left(\frac{71}{19}\right)=-1$

So, 19 is a quadratic non-residue modulo 71 and therefore the equation has no integer solutions.

2. $\left(\frac{p^2-1}{p}\right)=\left(\frac{(p+1)(p-1)}{p}\right)$

$=\left(\frac{1}{p}\right)\left(\frac{-1}{p}\right)$

$=(-1)^{(p-1)/2}$

**fir2011** · October 1st 2011, 04:09 AM

Oh cool, thanks alex, I understand it!

Thread: Legendre symbol

LinkBack

Thread Tools

Display

Legendre symbol

Re: Legendre symbol

Re: Legendre symbol

Similar Math Help Forum Discussions

Legendre symbol

[SOLVED] Legendre Symbol

Legendre Symbol (2/p)

the legendre symbol

Legendre symbol

Search Tags