Prove that $ax^2 + by^2 \equiv c \pmod{p}$ has integer solutions

Solution 1:

First off, the answer is clear when $p=2$: $(0,0)$ is a solution when $c\equiv 0 \pmod 2$ and $(1,0)$ is a solution when $c\equiv 1 \pmod 2$.

Now assume $p\neq 2$. Consider the group morphism $$f:\left(\frac{\mathbb{Z}}{p\mathbb{Z}}\right)^{\times}\rightarrow \left(\frac{\mathbb{Z}}{p\mathbb{Z}}\right)^{\times}: x\mapsto x^{2}.$$ Its kernel is $\{x\in \left(\frac{\mathbb{Z}}{p\mathbb{Z}}\right)^{\times}: x^{2}=1\}$, which has order $2$ since $1\not\equiv -1 \ mod \ p$ (as $p\neq 2$). It follows that the order of the image of $f$ is $$\frac{\left|\left(\frac{\mathbb{Z}}{p\mathbb{Z}}\right)^{\times}\right|}{2}=\frac{p-1}{2}.$$

Along with $0$, we get that the number of squares modulo $p$ is $$\left|\left\{x^{2} : x\in\frac{\mathbb{Z}}{p\mathbb{Z}}\right\}\right|=\frac{p+1}{2}.$$

It follows that $$\left|\left\{a^{-1}(c-by^{2})\pmod p: y\in\mathbb{Z}\right\}\right|=\frac{p+1}{2}.$$

As there are only $p-\frac{p+1}{2}=\frac{p-1}{2}$ not-squares modulo $p$, the set $\{a^{-1}(c-by^{2})\pmod p: y\in\mathbb{Z}\}$ must contain a square modulo $p$. That is, there exist $x,y\in\mathbb{Z}$ such that $$x^{2}\equiv a^{-1}(c-by^{2})\pmod p,$$ or $$ax^{2}+by^{2}\equiv c\pmod p.$$