Physics Forums

## Quadratic Reciprocity

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.

PhysOrg.com  science news on PhysOrg.com  >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug

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.

Quote by 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.

"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

Tags
quadratic, reciprocity

Thread Tools

|                                            |                            |         |
|--------------------------------------------|----------------------------|---------|
| Similar Threads for: Quadratic Reciprocity |                            |         |
| Thread                                     | Forum                      | Replies |
|                                            | Calculus & Beyond Homework | 0       |
|                                            | Calculus & Beyond Homework | 2       |
|                                            | Calculus & Beyond Homework | 0       |
|                                            | Linear & Abstract Algebra  | 1       |
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.944190263748169, "perplexity_flag": "middle"}