Clearly, there is a function that maps from solution space uniquely to problem space: n=x2+y2, 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
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 i2+1 is known to divide by n, P(Y)=(i,kn) for some positive integer k. Because i<n, we know that i2+1<n2, so k<n. Note that i2=-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: