Quadratic Congruences

**cathwelch** · May 11th, 2009, 07:40 PM

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.

**fardeen_gen** · May 13th, 2009, 08:22 AM

Consider the Legendre Symbols $\left(\frac{a}{p}\right)$ and $\left(\frac{b}{p}\right)$ ;

The symbol is completely multiplicative so $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \cdot\left(\frac{b}{p}\right)$ .

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

If it is not, however, then one side of the previous equality will be $+1$ while the other side will be $-1$ ... contradiction. We can have e.g. $\left(\frac{a}{p}\right) = 1$ and $\left(\frac{b}{p}\right) = 1$ so $\left(\frac{ab}{p}\right)$ = 1, etc.

Why is the Legendre symbol multiplicative? This property follows from Euler's Criterion, which states that $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}$ . This is proven essentially by writing $a = g^k$ where $g$ is a primitive root $\pmod{p}$ and $k$ is even iff $k$ is a quadradic residue $\pmod{p}$ and using Fermat's little theorem.

**cathwelch** · May 13th, 2009, 10:31 AM

I understand how you showed it was multipicative, but does that mean the equations are solvable?

**fardeen_gen** · May 13th, 2009, 09:36 PM

Ah well, the Legendre symbol's definition is:

$\left(\frac{a}{p}\right) =\begin{cases}0 & a\equiv 0\pmod{p}\\ +1 & a\not\equiv 0\pmod p\mbox{ and }\exists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\\ -1 & a\not\equiv 0\pmod p\mbox{ and }\nexists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\end{cases}$

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!

Math Help Forum: Quadratic Congruences

LinkBack

Thread Tools

Display

Quadratic Congruences

Similar Math Help Forum Discussions

Quadratic Congruences...

solve quadratic congruences

[SOLVED] Quadratic Congruences

Congruences classes, Quadratic Field

quadratic congruences