# Prove that this equation is solvable

Printable View

• August 22nd 2011, 01:23 PM
alexmahone
Prove that this equation is solvable
Given any integers a, b, c and any prime p not a divisor of ab, prove that $ax^2+by^2\equiv c\ (mod\ p)$ is solvable.
• August 24th 2011, 01:04 AM
Opalg
Re: Prove that this equation is solvable
Quote:

Originally Posted by alexmahone
Given any integers a, b, c and any prime p not a divisor of ab, prove that $ax^2+by^2\equiv c\ (mod\ p)$ is solvable.

I can only prove this by quoting a theorem from a recent research paper. However, the theorem is not that hard. Essentially the same result seems to have been proved a long time ago, in this 1893 article by J C Fields (after whom the Fields Medal is named).

If c is a multiple of p then we can take x = y = 0. So we can assume that $c\in\mathbb{Z}_p^*$ (the multiplicative group of nonzero residues mod p). Also, the result is easy to prove in the case p=2. So assume that p is an odd prime.

Let R be the set of quadratic residues mod p, and let N be the set of quadratic non-residues. According to Theorem 2.1 in this paper (pdf file), every element of $\mathbb{Z}_p^*$ belongs to each of the three sets R+R, R+N and N+N. But R is a subgroup of $\mathbb{Z}_p^*$. Its cosets are R and N. The sets $\{ax^2:x\in\mathbb{Z}_p^*\}$ and $\{by^2:y\in\mathbb{Z}_p^*\}$ are also cosets of R. Thus the set $\{ax^2 +by^2:x,y\in\mathbb{Z}_p^*\}$ is equal to one of the sets R+R, R+N or N+N, and therefore contains c.
All times are GMT -8. The time now is 10:45 AM.
{"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": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 8, "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": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9367042779922485, "perplexity_flag": "head"}