The table below gives the full numeric solution to the riddle.
| c=0 | c≠0 | |
| f mod 4=0 or 2 | f | f |
| f mod 4=1 | 2f-1 | f-1 |
| f mod 4=3 | 1 | f+1 |
I originally intended to publish a proof that uses only elementary arithmetic on fields, but, instead, here is a much more elegant solution, for which I thank Albert Stadler.
The solution is based on the well-known fact that the multiplicative group of any field is cyclic. In other words, there is an element g in F such that {1, g, g2,... ,gf-2} is the set of all non-zero elements in F. Such an element is called a "generator" of F.
Given this fact, there are many observations regarding fields that become trivial. For example, when we ask ourselves whether a certain c in F is a quadratic residue (whether there is an x such that x2=c), the answer can be reformulated as follows: for an element c=gl, is there an element x=gl/2? So, the question is whether one can divide l by two modulo f-1. When f is odd, this boils down to whether l is even. When f is even, 2 is invertible and therefore every element is a quadratic residue.
Furthermore, if f=4k+3, then -1 (where 1 is the unity element of the field and -1 is its additive inverse) equals g2k+1, so it is a quadratic non-residue, whereas if f=4k+1, then -1=g2k, so it is a quadratic residue and has both gk and g3k as its square roots. Lastly, if f is even, x=1=-1 is the single solution to x2=1=-1.
Let us define the function Χ(a) to be the number of distinct solutions to x2=a minus one. x2=a is a quadratic equation, so it can have between zero and two solutions, so Χ(a) is one of -1, 0 and 1. Considering the representation of a as gl, one can easily prove the following claims:
Let us now define N(c) to be the number of distinct solutions to x2+y2=c. This is the function we are trying to calculate. For convenience, we will define a=x2 and b=y2.
To calculate N(c), we will represent it in terms of Χ:
N(c) = Σa+b=c(Χ(a)+1)(Χ(b)+1) = Σa+b=cΧ(ab) + ΣaΧ(a) + ΣbΧ(b) + f = Σa+b=cΧ(ab) + f = ΣbΧ((c-b)b) + f = Σb≠0Χ((c-b)b) + f = Σb≠0Χ((c-b)/b) + f = Σb≠0Χ(c/b-1) + f
If c=0, this expression simply becomes
N(c) = Σb≠0Χ(-1) + f = f+(f-1)Χ(-1)
On the other hand, if c≠0 then the function m(b)=c/b is one-to-one over the non-zero elements of F, so the solution is
N(c) = Σd≠0Χ(d-1) + f = Σd≠-1Χ(d) + f = f-Χ(-1)
Knowing f (mod 4), we can plug in to the equation the previously calculated value of Χ(-1) in the field, and the result is the table given above.
Q.E.D.
As a side-note, the good properties of the function Χ allow it to be useful in many contexts other than in this riddle. Look up "Dirichlet Character" for more details.