1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 13, 2015 #1
    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. jcsd
  3. May 13, 2015 #2


    User Avatar
    Homework Helper

    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