# $x^2 \equiv a \mod p$, $\ x^2 \equiv b \mod p$, and $x^2 \equiv ab \mod p$, prove either all three are solvable or exactly one

Let $p$ be an odd prime and $a, b \in \Bbb Z$ with $p$ doesn't divide $a$ and $a$ doesn't divide $b$. Prove that among the congruence's $x^2 \equiv a \mod p$, $\ x^2 \equiv b \mod p$, and $x^2 \equiv ab \mod p$, either all three are solvable or exactly one.

Please help I'm trying to study for final in number theory and I can't figure out this proof.

• Hint: Product of quadratic residues is a quadratic residue and product of non-residues is still a quadratic residue. – Anurag A May 4 '15 at 4:11
• @elenor I saw that you tried to accept both answers; that's not necessary (or indeed possible), you do have enough reputation that you can upvote both, but still only one gets the check mark. – Joffan May 5 '15 at 15:09

What you should prove directly is the following:

A counting argument then yields additionally:

These facts combined yield the desired answer, by breaking into cases as to whether or not $a,b$ are quadratic residues.
Since $p$ is a prime, it has at least one primitive root $g$.
• Every quadratic residue $q$ (coprime to $p$) can be expressed as $g^{2k}\equiv q \bmod p$.
• Every quadratic non-residue $n$ can be expressed as $g^{2k+1}\equiv n \bmod p$.
Therefore your assertion is equivalent to the parity of the exponent of a chosen primitive root. Odd exponents give quadratic non-residues, even exponents give quadratic residues, and multiplying the numbers $a$ and $b$ together leads to adding the exponents.
You can Euler's criterion. Let $$A=a^{\frac{p-1}{2}} \bmod p, \quad B=b^{\frac{p-1}{2}} \bmod p, \quad C=(ab)^{\frac{p-1}{2}} \bmod p$$ Then $C=AB$. This implies that if two of the equations are solvable, then so is the third.