Quadratic Reciprocity

joeblow

If a is a quadratic nonresidue of the odd primes p and q, then is the congruence [itex] x^2 \equiv a (\text{mod } pq) [/itex] solvable?

Obviously, we want to evaluate [itex] \left( \frac{a}{pq} \right) [/itex]. I factored a into its prime factors and used the law of QR and Euler's Criterion to get rid of the legendre symbols needed to evaluate [itex]\left( \frac{a}{pq}\right)[/itex]. I don't believe that this helped, though, because I get that it is conditionally solvable, which I don't think is possible from the way the question is worded. (To be exact, I concluded that if a has only one prime factor, then it is unsolvable unless it is 2. It is solvable for every other case.)

Any help is appreciated.

dodo

Hi, Joe,
I'd go straight at the definition: if there is a solution x to the congruence modulo pq, then [itex]x^2 - a = kpq[/itex] for some integer k; but then the same x would solve the congruences mod p or mod q.

DonAntonio

"a is not a quadratic residue modulo p" means "there don't exist integers x,k s.t. [itex]x^2=a+pk[/itex].

From here it follows that if a is not a quad. res. modulo p, q then it can't be a quad. res. modulo pq, since then [itex]x^2=a+rpq = a+(rp)q\Longrightarrow [/itex] a is a quad. res. mod q, against the given data.

DonAntonio