Is a Quadratic Nonresidue of Odd Primes p and q Also a Nonresidue Modulo pq?

[joeblow]

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

Obviously, we want to evaluate \left( \frac{a}{pq} \right). 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 \left( \frac{a}{pq}\right). 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 x^2 - a = kpq for some integer k; but then the same x would solve the congruences mod p or mod q.

 

[DonAntonio]

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

Obviously, we want to evaluate \left( \frac{a}{pq} \right). 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 \left( \frac{a}{pq}\right). 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.

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

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 x^2=a+rpq = a+(rp)q\Longrightarrow a is a quad. res. mod q, against the given data.

DonAntonio