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, g^{2},... ,g^{f-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 x^{2}=c), the answer can be reformulated as follows: for an element c=g^{l}, is there an element x=g^{l/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 g^{2k+1}, so it is a quadratic non-residue, whereas if f=4k+1, then -1=g^{2k}, so it is a quadratic residue and has both g^{k} and g^{3k} as its square roots. Lastly, if f is even, x=1=-1 is the single solution to x^{2}=1=-1.
Let us define the function Χ(a) to be the number of distinct solutions to x^{2}=a minus one. x^{2}=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 g^{l}, one can easily prove the following claims:
Let us now define N(c) to be the number of distinct solutions to x^{2}+y^{2}=c. This is the function we are trying to calculate. For convenience, we will define a=x^{2} and b=y^{2}.
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.