Pell's equation and representation elements of $\mathbb Z_p$.

Question

We defined the function $f:\mathbb Z_p \times \mathbb Z_p \rightarrow \mathbb Z_p$ such that $f(x,y)=x^2-cy^2$ and $c\not\equiv 0\pmod{p}$. Is it true that $f$ is onto?

Answer 1

The case $p=2$ can be dealt with separately, so let $p$ be odd.

We suppose that $c\not\equiv 0\pmod{p}$. Let $0\le t\le p-1$. We will show that there exist $x, y$ such that $x^2-cy^2\equiv t\pmod{p}$.

Let $S$ be the set of all $x^2$ modulo $p$, where $x$ ranges over the interval $[0,p-1]$. Then $S$ has $\frac{p-1}{2}+1=\frac{p+1}{2}$ incongruent elements modulo $p$.

Let $T$ be the set of all $cy^2+t$, where again $y$ ranges over the interval $[0,p-1]$. Again, because $c\not\equiv 0\pmod{p}$, $T$ has $\frac{p+1}{2}$ incongruent elements modulo $p$.

Since $\frac{p+1}{2}+\frac{p+1}{2}\gt p$, by the Pigeonhole Principle there exists a pair $u\in S$, $v\in T$ such that $u\equiv v\pmod{p}$.

It follows that there exist $x$ and $y$ such that $x^2\equiv cy^2+t\pmod{p}$.