- #1

sunnyceej

- 15

- 0

## Homework Statement

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 x

^{2}= ab (mod pq)

## Homework Equations

Legendre symbols: (a/p) = (b/p) and (a/q) = (b/q)

quadratic residue means x

^{2}= a (mod p)

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

_{1}

^{2}=ab(mod p) and x

_{2}

^{2}=ab(mod q).

The Chinese remainder theorem takes me in circles, and since I can't guarantee x

_{1}

^{2}= x

_{2}

^{2}, 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?