Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quadratic Reciprocity

  1. Apr 1, 2012 #1
    If a is a quadratic nonresidue of the odd primes p and q, then is the congruence [itex] x^2 \equiv a (\text{mod } pq) [/itex] solvable?

    Obviously, we want to evaluate [itex] \left( \frac{a}{pq} \right) [/itex]. 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 [itex]\left( \frac{a}{pq}\right)[/itex]. 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. jcsd
  3. Apr 2, 2012 #2
    Hi, Joe,
    I'd go straight at the definition: if there is a solution x to the congruence modulo pq, then [itex]x^2 - a = kpq[/itex] for some integer k; but then the same x would solve the congruences mod p or mod q.
  4. Apr 2, 2012 #3

    "a is not a quadratic residue modulo p" means "there don't exist integers x,k s.t. [itex]x^2=a+pk[/itex].

    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 [itex]x^2=a+rpq = a+(rp)q\Longrightarrow [/itex] a is a quad. res. mod q, against the given data.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook