# Homework Help: If a and b are both quadratic residues/nonresidues mod p & q

Tags:
1. May 13, 2015

### sunnyceej

1. The problem statement, all variables and given/known data
If a and b are both quadratic residues/nonresidues mod p & q where p and q are distinct odd primes and a and b are not divisible by p or q, Then x2 = ab (mod pq)

2. Relevant equations
Legendre symbols: (a/p) = (b/p) and (a/q) = (b/q)
quadratic residue means x2 = a (mod p)

3. The attempt at a solution
I know that since (a/p) = (b/p) and (a/q) = (b/q) that (ab/p) = 1 and (ab/q) = 1 (ab is a quadratic residue for both mod p and mod q). So I have x12=ab(mod p) and x22=ab(mod q).

The Chinese remainder theorem takes me in circles, and since I can't guarantee x12= x22, then I can't just multiply p and q and call it good. I've spent hours trying to find a counter example since I can't figure out how to combine p and q into the same mod. So I'm stuck. any hints on what to look at for either a proof or counterexample?

2. May 13, 2015

### Zondrina

Let $n = pq$ where $p$ and $q$ are odd primes. You wish to solve:

$$x^2 \equiv ab \space \text{mod n}$$

From the information given, the above equation takes the form:

$$x^2 - ab \equiv 0 \space \text{mod n}$$

$$\Rightarrow (x - ab)(x + ab) \equiv 0 \space \text{mod n}$$

So we know:

$$(x - ab) \equiv 0 \space \text{mod n}$$
$$(x + ab) \equiv 0 \space \text{mod n}$$

How many solutions can you see? Some of them will be relatively straightforward, then you need to do the old switcheroo.

Last edited: May 13, 2015
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted