# Prove that this equation is solvable

• Aug 22nd 2011, 02: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.
• Aug 24th 2011, 02: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.