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.

Printable View

- May 11th 2009, 08:40 PMcathwelchQuadratic 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.

- May 13th 2009, 09:22 AMfardeen_gen
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. - May 13th 2009, 11:31 AMcathwelch
I understand how you showed it was multipicative, but does that mean the equations are solvable?

- May 13th 2009, 10:36 PMfardeen_gen
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!