*x*and*y*are co-prime.*i**x*=*y*(mod*n*).*x*^{2}+*y*^{2}=*n*.

Clearly, there is a function that maps from solution space uniquely to problem
space: *n*=*x*^{2}+*y*^{2},
*i*=*y*/*x* (mod *n*). We want to prove that this mapping is
invertible. In other words, we want to show that it is 1-to-1 and over.

For reasons that will become clear later on, we will also add one artificial
"solution" and one corresponding artificial "problem" as follows:
(*x*,*y*)=(1,0) will be added to the list of solutions and
(*i*,*n*)=(0,1) will be added to the list of problems. This addition
does not disturb the invertibility of the function.

The trick to solving this riddle is by considering it as a problem on complex
integers (complex numbers that have integral real and imaginary parts). In what
follows, we will use capital letters to denote complex integers. In particular,
we will use the capital *I* to denote the square root of -1.

First, we will map each solution (*x*,*y*) to four complex integers:
*x*+*yI*, *y*-*xI*,-*x*-*yI* and
-*y*+*xI*. We will call the total set of complex integers mapped in
this way the "solution points". If *X* is a solution point, then it also
has an associated solution, denoted *S*(*X*), and an associated
problem,
denoted *P*(*X*). (Notably, in this context the switch from problem
space to solution space looks remarkably like a switch from polar coordinates
to Cartesian coordinates.)

The reason that this mapping to complex integers is helpful is because of certain good properties of complex division that can all be verified immediately by checking the formulae for multiplication and division. These properties are as follows:

If *Y* is a solution point with *P*(*Y*)=(*i*,*n*),
then

- If
*X*is a divisor of*Y*then*X*is a solution point. - If
*X*is a solution point then*X*is a divisor of*Y*iff*P*(*X*)=(*j*,*m*) where*m*is a divisor of*n*and*j*=*i*mod*m*. - If
*X*is a divisor of*Y*and*P*(*X*)=(*i*mod*m*,*m*) then*P*(*Y*/*X*)=(*i*mod (*n*/*m*),*n*/*m*).

First, we prove that for every "problem" there is a "solution". Let us assume
the opposite, namely that there are some problems without solutions. Then,
let (*i*,*n*) be a problem without a solution with *n* chosen
to be minimal.
Consider the solution point *Y*=1+*iI*. Because
*i*^{2}+1 is known to
divide by *n*, *P*(*Y*)=(*i*,*kn*) for some positive
integer *k*. Because
*i*<*n*, we know that
*i*^{2}+1<*n*^{2}, so *k*<*n*. Note
that *i*^{2}=-1 (mod *k*), so, by the
minimality assumption, there exists a solution point *X*, s.t.
*P*(*X*)=(*i* mod *k*,*k*).
Consider, now, *Z*=*Y*/*X*. Clearly,
*P*(*Z*)=(*i*,*n*), so *S*(*Z*) is a solution to
this problem - a contradiction.

Next, let us show that the solution is unique.
Suppose that for some problem (*i*,*n*) there are two
solutions. Each of these solutions can be represented by a respective solution
point. So, we have two solution points, *X* and *Y*, with
*P*(*X*)=*P*(*Y*). By property number 2 of division,
*X* is a divisor of *Y*. Consider, therefore,
*Z*=*Y*/*X*. The absolute value of *Z* is clearly 1, so
*Z* must be one of 1, *I*, -1 or -*I*. However, in all these
cases
*S*(*X*)=*S*(*ZX*)=*S*(*Y*), meaning that the two
solutions are not distinct.

Q.E.D.

The proof above uses nothing but basic algebra for simplicity, but
purists may find that the 4-to-1 correspondence between solution points and
solutions is less than aesthetic. This problem can be corrected at the price
of some abstraction, as follows: in this solution we referred to the ring of
complex integers, but, in fact, we never used addition, so we're really talking
about complex integers as though they were a monoid (a commutative monoid, to
be exact). Now, let's add to this monoid the (somewhat unexpected) equivalence
relation *I*=1. This equivalence relation folds the entire monoid into
the first quadrant, allowing the proof to proceed with a 1-to-1 relation,
instead of a 4-to-1 relation.

I am not aware of any studies that have been made regarding this particular commutative monoid (readers are welcomed to correct my ignorance), but it certainly seems like an interesting object for study.

Regarding the bonus questions:

- If
*a*^{2}+*m*=*b*^{2}then*m*=*b*^{2}-*a*^{2}= (*b*+*a*)(*b*-*a*). So, if*m*is represented as the product of two numbers,*m*=*cd*, with*c*>*d*and*c*=*d*(mod 2), then one can solve for*a*and*b*by*a*=(*c*-*d*)/2 and*b*=(*c*+*d*)/2. This means that the total number of solution pairs is zero if*m*is 2 (mod 4), is floor(d(*m*)/2) if*m*is odd, and is floor(d(*m*/4)/2) if*m*is divisible by four. d(*x*), in every case, is the divisor function, counting how many divisors*x*has. - In order to count the number of solutions to
*a*^{2}+*b*^{2}=*m*, we sum over the number of solutions to*i*^{2}=-1 (mod*m*) (in order to find the number of solutions where*a*and*b*are co-prime), then repeat for all*n*such that*m*/*n*is a perfect square. (If it is*x*^{2}, this will enumerate the (*a*,*b*) solutions where gcd(*a*,*b*)=*x*.) Summing up all these results gives us the desired formula. If we represent*m*as the product*m*=2^{k}*P*_{1}*P*_{3}, where*P*_{1}has only prime factors that are 1 (mod 4), whereas*P*_{3}has only prime factors that are 3 (mod 4), then the complete formula is this: The number of solutions is zero if*P*_{3}is not a perfect square. Otherwise, the number of (unordered pair) solutions is d(*P*_{1})/2, if*P*_{1}is not a perfect square and (d(*P*_{1})-(-1)^{k})/2 if it is.

- A number appears in exactly one Pythagorean triplet iff it is a prime that is 3 (mod 4) or twice such a prime.
- A number appears in the same number of Pythagorean triplets as a side and as the hypotenuse length iff all of its prime factors are 1 (mod 4) or if it is twice such a number.