# Legendre Symbol

• May 11th 2009, 01:44 PM
cathwelch
Legendre Symbol
Question:
If p is an odd prime and gcd (ab, p)=1, prove that at least one of a, b, or ab is a quadratic residue of p.
• May 11th 2009, 02:56 PM
PaulRS
Prove it by contradiction, assume none of them were a quadratic residue, then $
\left( {\tfrac{a}
{p}} \right) = \left( {\tfrac{b}
{p}} \right) = \left( {\tfrac{{ab}}
{p}} \right) = - 1
$
however remember that $
\left( {\tfrac{a}
{p}} \right) \cdot \left( {\tfrac{b}
{p}} \right) = \left( {\tfrac{{ab}}
{p}} \right)
$
(Wink)