1. Apr 1, 2012

### 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.

2. Apr 2, 2012

### 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.

3. Apr 2, 2012

### DonAntonio

"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