0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hint: Product of quadratic residues is a quadratic residue and product of non-residues is still a quadratic residue. $\endgroup$ – Anurag A May 4 '15 at 4:11
  • $\begingroup$ @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. $\endgroup$ – Joffan May 5 '15 at 15:09
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.