Thread: Quadratic Congruences

Question:

Let p be an odd prime and gcd(a,p) = gcd(b,p) =1. Prove that either all three of the quadratic congruences
x^2= a(mod p), x^2= b(mod p), and x^2= ab(mod p)
are solvable or exactly one of them admits a solution.

Consider the Legendre Symbols $\displaystyle \left(\frac{a}{p}\right)$ and $\displaystyle \left(\frac{b}{p}\right)$;

The symbol is completely multiplicative so $\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \cdot\left(\frac{b}{p}\right)$.

We want to prove that the number of Legendre symbols taking on value $\displaystyle +1$ is odd.

If it is not, however, then one side of the previous equality will be $\displaystyle +1$ while the other side will be $\displaystyle -1$... contradiction. We can have e.g. $\displaystyle \left(\frac{a}{p}\right) = 1$ and $\displaystyle \left(\frac{b}{p}\right) = 1$ so $\displaystyle \left(\frac{ab}{p}\right)$ = 1, etc.

Why is the Legendre symbol multiplicative? This property follows from Euler's Criterion, which states that $\displaystyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}$. This is proven essentially by writing $\displaystyle a = g^k$ where $\displaystyle g$ is a primitive root $\displaystyle \pmod{p}$ and $\displaystyle k$ is even iff $\displaystyle k$ is a quadradic residue $\displaystyle \pmod{p}$ and using Fermat's little theorem.

I understand how you showed it was multipicative, but does that mean the equations are solvable?

Ah well, the Legendre symbol's definition is:

$\displaystyle \left(\frac{a}{p}\right) =\begin{cases}0 & a\equiv 0\pmod{p}\\ +1 & a\not\equiv 0\pmod p\mbox{ and }\exists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\\ -1 & a\not\equiv 0\pmod p\mbox{ and }\nexists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\end{cases}$

By the given condition, the first case is not true.

If you think about it, Euler's Criterion is pretty interesting. Quadratic reciprocity is nice as well!