[Dr Sardonicus]

It occurred to me to wonder about using rotation matrices as an alternate approach to the well known - and long settled - question of counting solutions to a^2 + b^2 == k (mod p) where p is an odd prime.

A standard approach uses Gauss and Jacobi sums to count the number of solutions. It gives the exact answer in the quadratic case, and a good estimate for higher exponents. The rotation matrix method, alas, does not apply to higher exponents.

However, it actually does work in the quadratic case. It uses only very basic facts. One is that, if p is a prime number, the non-zero residues (mod p) form a multiplicative group which is cyclic of order p-1.

It follows that, if p is an odd prime, there is a multiplicative subgroup of order 4 when p == 1 (mod 4), but not if p == 3 (mod 4). That is, there are square roots of -1 (mod p) if p == 1 (mod 4) but not if p == 3 (mod 4).

A cyclic group of order g has cyclic subgroups of every order dividing g. In particular, when p is an odd prime, the multiplicative group of non-zero residues is cyclic of order p-1, so has a cyclic subgroup of order (p-1)/2. The elements of this subgroup are the non-zero quadratic residues (mod p), which we will denote by R. We have R == t^2 (mod p) for some non-zero t for each such R. The other (p-1)/2 non-zero residues (mod p) are the quadratic non-residues, which we will denote by N.

We now look at the equation a^2 + b^2 == k (mod p). Assuming there is a solution, we can multiply through by any quadratic residue R == t^2 (mod p), giving (a*t)^2 + (b*t)^2 == k*R (mod p).

So, the existence of solutions to a^2 + y^2 = k can depend at most on whether k is a quadratic residue. For k = 1, we have the solution 1^2 + 0 = 1, so there is a solution for k = R, R any quadratic residue.

Further, if R == t^2 (mod p), there is a solution for R + 1, namely t^2 + 1^2 == R + 1 (mod p).

Now R + 1 can't be a quadratic residue for every quadratic residue R, because if it were, every residue (mod p) would be a quadratic residue, and there are only (p-1)/2 quadratic residues.

Thus, there is at least one quadratic residue R (mod p) for which R + 1 = N, a quadratic non-residue (mod p), and for such an N, a^2 + b^2 = N has a solution (mod p). It follows that a^2 + b^2 = k (mod p) has a solution for every non-zero residue k (mod p).

This leaves the case of 0 (mod p). If p == 3 (mod 4) the only solution to a^2 + b^2 == 0 (mod p) is (a, b) = (0, 0). if p == 1 (mod 4), however, there are other solutions. There are two solutions to x^2 + 1 == 0 (mod p) [the two generators of the multiplicative subgroup of order 4]. Multiplying through by b^2 (mod p) for the p - 1 non-zero residues (mod p) then gives 2*p - 2 solutions to a^2 + b^2 == 0 (mod p) with (a,b) ≠ (0,0). So for p == 1 (mod 4) there are 2*p - 1 pairs (a, b) (mod p) for which a^2 + b^2 == 0 (mod p).

Now - finally! - here come the rotation matrices! From a previous post, we have a formula for a rotation matrix M = [x, -y;y, x] with det(M) = x^2 + y^2 = 1, that transforms

(a, b) with a^2 + b^2 = k (mod p) into

(c, d) with c^2 + d^2 = k (mod p)

by M[a;b] = [c;d]

We now show that if (a,b) ≠ (0, 0), the rotation matrix M is unique. Suppose that M and M' are rotation matrices for which M'[a;b] = M[a;b]. Then M^-1M'[a;b] = [a;b].

Now it is easily seen that the product of two rotation matrices is a rotation matrix (in fact, rotation matrices form a multiplicative group), so we can write

[x,-y;y;x][a;b] = [a;b] where x^2 + y^2 = 1 and [x,-y;y,x] = M^-1M'. We then have

[x-1,-y;y,x-1][a;b] = [0;0].

Since (a,b) ≠ (0, 0) this is only possible if the determinant of [x-1,-y;y,x-1] is 0. This determinant is (x-1)^2 + y^2 = x^2 + y^2 + 1 - 2*x = 2 - 2*x, since x^2 + y^2 = 1. Thus, x = 1 and y = 0, so M^-1M' is the 2x2 identity matrix; that is, M' = M. Thus, the rotation matrix M is unique.

It follows that the number of solutions to a^2 + b^2 == k (mod p) is the same for every non-zero residue k, and that this number (call it m) is equal to the number of solutions to x^2 + y^2 == 1 (mod p).

There are p^2 pairs of residues (a, b) (mod p). There are p-1 non-zero residues (mod p).

We showed earlier that if p == 3 (mod 4) there is one pair, (a, b) = (0,0) (mod p) for which a^2 + b^2 == 0 (mod p). In this case we have m*(p-1) + 1 = p^2, giving m = p+1.

If p == 1 (mod 4) we showed that there are 2*p - 1 pairs (a, b) (mod p) for which a^2 + b^2 == 0 (mod p). In this case we have m*(p-1) + 2*p - 1 = p^2, giving m = p-1.