# Legendre symbol

• Sep 29th 2011, 05:01 PM
fir2011
Legendre symbol
Hey guys, I need a bit of help here.

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

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

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

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

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

Is this enough to show no integer solutions?

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

So $\displaystyle \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?

• Oct 1st 2011, 04:04 AM
alexmahone
Re: Legendre symbol
1. $\displaystyle x^2-71y^2=19 \implies x^2\equiv 19 \pmod{71}$

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

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

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

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

$\displaystyle =(-1)^{(p-1)/2}$
• Oct 1st 2011, 04:09 AM
fir2011
Re: Legendre symbol
Oh cool, thanks alex, I understand it!