How many quadratic non-residues are there in the image of $f(a) = a^2 - x^2$?

Question

When reading about Cipolla's algorithm on Wikipedia, I found that the number of quadratic non-residues in the image of $f:\Bbb F \longrightarrow \Bbb F, f(a) = a^2 - x^2$ where $\Bbb F$ is a finite field of prime cardinality $p$ and $x \in \Bbb F$, is $\frac{p-1} 2$. Why?

---

I was thinking that there might be some sort of symmetry between the nonzero quadratic residues and the quadratic nonresidues, but I don't see it.

[edit]

Wherever I previously said quadratic residue, it nows says quadratic nonresidue.

Answer 1

This is not true in general. Let $p=7$ and $x=1$. Then $a^2-1^2$ takes on values $-1,0,3,1$ modulo $7$. There is only one QR in the bunch, and two NR.

What is true for odd primes $p$ is that $f(a)$ takes on exactly $\frac{p-1}{2}$ diferent non-zero values modulo $p$. But this is obvious, since $a^2$ takes on $\frac{p-1}{2}+1$ values.

Remark: The Wikipedia article does not count the number of non-residues in the image of $f$. For each $a$ it makes a tick if $a^2-x^2$ is a NR, and it counts the number of ticks.

Answer 2

$$f(a) = a^2 - x^2 = a^2\left(1 - \left( \frac x a \right)^2 \right)$$

Now $x/a$ can be anything, so we've got the $1 - $ an arbitrary quadratic residue. The problem becomes counting how many quadratic residues there are in the image of $f(x) = 1 - x^2$ (I found it distracting to make the constant in the function $x$).

So let's say we've got $$1 - x^2 = y^2 \iff 1 = x^2 + y^2$$ This looks like a circle. So we have to count the number of points on the unit circle, and then get rid of repeated values of $x$.

Maybe we can do that considering lines from $(-1,0)$ to the circle. Every point on the circle has such a line, and so we just have to show that for any slope we get two points only one of which is $(-1,0)$ (therefore making it one-to-one). The non-$(-1,0)$ solution to this is well known: $$(\frac{2t}{1 + t^2}, \frac{1-t^2} {1+t^2})$$ where $t$ is the slope of the line. So we have that every point yields a unique line and every line yields a point, so one-to-one as claimed.

Now divide the number of points on the circle (which is $p+1$, when counting every slope value and the vertical line) by $2$ and then add $1$ to get $\frac{p+1}{2} + 1 = \frac{p + 3} 2$