Number of solutions to $x^2−y^2=a$ over a finite field.

Question

Consider F is a finite field with $ q$ elements, where $q=p^n$, p prime, and n is an integer. Give the number of solutions of pairs (x,y) for the equation $$ x^2-y^2=a $$ according to the value of $ q $ and $ a $ in F.

I have resolved the case where $p=2$ and $p≠2$ with $a=0$. However, I encountered an issue in the case where $p≠2$ and $a≠0$. My initial idea was to find all possible differences between square numbers and then look for cases with equal differences. However, I quickly realized that I couldn't solve the problem $ a^2+b^2=c^2+d^2 $ in a finite field.

Later, I changed my strategy and found that all solutions satisfy the form $$ \left(\frac{b^{-1}+ab}{2},\frac{b^{-1}-ab}{2}\right) $$ However, I am unable to determine the total number of solutions of this form.

Please provide me with some ideas or help me solve this problem. Thanks!

Answer 1

I know no theory of finite fields, but taking the question from what you achieved, we have to count the size of the set $$S=\left\{\left(\frac{b^{-1}+ab}{2},\frac{b^{-1}-ab}{2}\right):b\in F^*\right\}.$$

1. Breaking the problem in smaller parts, I'd count the left $L=\left\{\frac 1 2(b^{-1}+ab):b\in F^*\right\}$ and right $R=\left\{\frac 1 2(b^{-1}-ab):b\in F^*\right\}$ pieces separately.

2. Now to count the size of $L$, I'd note that purely syntactically it's defined as the image of a function $f_L:F^*\to F^*$ $$f_L(b)=\frac 1 2(b^{-1}+ab).$$ If the function were an injection, we'd know the answer because $L=f_L(F^*)$ would be the whole $F^*$ (because it's finite), so next I'd try to "measure the non-injectivity" of $f_L$.

3. To this goal, take $f_L(b)=f_L(b')$ and see that (if I computed right) $b'$ is either $b$ or $1/ab$, and conversely.$$\forall b,b'\in F^*:f_L(b)=f_L(b')\Leftrightarrow (b=b' \textrm{ or } bb'=1/a)$$ That is, for each $b\in F^*$, $f_L$ produces either a unique result, or is the same as $f_L(1/ab)$. The former happens only if $b=1/ab$, that is, if $b^2=1/a$.

4. Therefore, the total number of different outputs of $f_L$ is the number of square roots of $1/a$ plus half of the rest of $F^*$: $$|L|=|f_L(F^*)| = \left|\sqrt{\{1/a\}}\right| + \frac 1 2\left|F^*\setminus\sqrt{\{1/a\}}\right|$$ where I lazily denoted $\sqrt{\{1/a\}}=\{b\in F^*:b^2=1/a\}$.
   Similarly, $|R|= \left|\sqrt{\{-1/a\}}\right| + \frac 1 2\left|F^*\setminus\sqrt{\{-1/a\}}\right|$.

If what I read here (http://cap-lore.com/MathPhys/Field/finite/sqrt.html) is true, then $|\sqrt{\pm\{1/a\}}|$ is either 0 or 2, but I don't know why. You can substitute in the formulas to get a further evaluated answer. Anyway, we're back in finite fields theory land so I hope you can take it from here :)

Answer 2

Consider the equation

$$xy=a \tag1$$

over $\Bbb F_q$ and with $a\neq0$. This equation has obviously $q-1$ different solutions: For any $x\neq0$, the pair $(x,a/x)$ is a solution. And $x=0$ is not a solution.

Then consider the mapping $$\begin{align} \Bbb F_q^2 &\quad\to\quad \Bbb F_q^2 \\ (x,y) &\quad\mapsto\quad (x-y, x+y) \end{align}\tag2$$ which is a bijection if $2\nmid q$ because its discriminant is a unit in $\Bbb F_q$.

Because $(2)$ is a bijection, it does not change the number of solutions when we apply it to $(1)$, and the result of the transformation applied to $(1)$ is:

$$(x-y)(x+y) = x^2-y^2 = a \tag3$$

Hence $(3)$ has also $q-1$ solutions provided $a\neq0$ and $2\nmid q$.

If $a=0$, then $(1)$ has obviously $2q-1$ solutions, namely $\{(x,0)\}\cup\{(0,x)\}$: The cardinality of the union is the sum of the cardinalities of the two sets, which is $2q$ but subtracted by the cardinality of the intersection, which is $\#\{(0,0)\}=1$.

Characteristic 2

Remaining is the case where $q=2^n$. Now every element $a\in\Bbb F_{2^n}$ is a square so you can write $a=r^2$ and hence $(3)$ can be written as:

$$ x^2=a+y^2 = r^2+y^2 = (r+y)^2 \tag 4 $$ Also because every element is a square (and as $\Bbb F_q$ is finite), $x\mapsto x^2$ is injective, and therefore taking square roots on both sides of $(4)$ yields: $$ x=r+y\tag 5 $$ which has $q$ different solutions for each $r$, and thus also $q$ different solutions for each $a$ (again because squaring is injective).

Conclusion

$$ \text{Number of solutions} = \begin{cases} q-1, &\text{ if } 2\nmid q \text{ and } a\neq0\\ 2q-1, &\text{ if } 2\nmid q \text{ and } a=0\\ q, &\text{ if } 2\mid q\\ \end {cases}$$