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