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 and ;

The symbol is completely multiplicative so .

We want to prove that the number of Legendre symbols taking on value is odd.

If it is not, however, then one side of the previous equality will be while the other side will be ... contradiction. We can have e.g. and so = 1, etc.

Why is the Legendre symbol multiplicative? This property follows from Euler's Criterion, which states that . This is proven essentially by writing where is a primitive root and is even iff is a quadradic residue 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:



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!