$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

Question

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.

Answer 1

What you should prove directly is the following:

• The product of two quadratic residues is a quadratic residue.
• The product of a quadratic residue and a quadratic non-residue is a quadratic non-residue.

A counting argument then yields additionally:

• The product of two quadratic non-residues is a quadratic residue.

These facts combined yield the desired answer, by breaking into cases as to whether or not $a,b$ are quadratic residues.

Answer 2

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.

Answer 3

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.