Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

Question

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?

Answer 1

This is Problem 7 in Section 4.5, "Combinatorial Number Theory," of I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991. I will assume that you are familiar with the material in the book that precedes that problem, namely,

• For all $a$ such that $(a, p) = 1$, $a$ is called a quadratic residue modulo $p$ if the congruence $x^2 \equiv a \pmod p$ has a solution. If it has no solution, then $a$ is called a quadratic nonresidue modulo $p$.

• For an odd prime $p$, among the $p$ integers modulo $p$, there are $(p - 1)/2$ quadratic residues, $(p - 1)/2$ quadratic nonresidues; the remaining integer is $0 \pmod p$, which makes the congruence solvable but is not called a quadratic residue because $(0, p) = p \not\equiv 1 \pmod p$.

Try to solve the problem yourself reading just enough of this answer to get started. Maybe the two items above suffice.

In the following, we assume congruences and $a, b, c, x, y$ to be modulo $p$.

If $c \equiv 0$, then $(x, y) = (0, 0)$ is a solution. So assume $c \not\equiv 0$ for the remainder of this answer.

If $p = 2$, then $a$, $b$, and $c$ are each congruent to $1$, and $(x, y) = (0, 1)$ is a solution. So assume $p$ is odd for the remainder of this answer.

Rewrite the congruence as $x^2 \equiv \bar{a}c - \bar{a}by^2$ where $\bar{a}a \equiv 1$. If $\bar{a}c$ is a quadratic residue, then put $y = 0$ so that $x^2 \equiv \bar{a}c$ has a solution.

If $\bar{a}c$ is a quadratic nonresidue, then let $y$ run through the $p - 1$ nonzero integers modulo $p$ so that $y^2$ runs through the $(p - 1)/2$ quadratic residues, and, in turn, $\bar{a}c - \bar{a}by^2$ takes on $(p - 1)/2$ distinct values. Because $\bar{a}by^2 \not\equiv 0$, $\bar{a}c - \bar{a}by^2$ is not congruent to the quadratic nonresidue $\bar{a}c$, so the $(p - 1)/2$ values of $\bar{a}c - \bar{a}by^2$ can take on at most $(p - 1)/2 - 1$ quadratic nonresidues; hence at least one value of $\bar{a}c - \bar{a}by^2$ must be congruent to a quadratic residue or $0$, which makes the congruence solvable.

Thus, for all cases, $ax^2 + by^2 \equiv c$ is solvable.