Feb 2017
Nowhere
6509_{10} Posts

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 nonzero residues (mod p) form a multiplicative group which is cyclic of order p1.
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 nonzero residues is cyclic of order p1, so has a cyclic subgroup of order (p1)/2. The elements of this subgroup are the nonzero quadratic residues (mod p), which we will denote by R. We have R == t^2 (mod p) for some nonzero t for each such R. The other (p1)/2 nonzero residues (mod p) are the quadratic nonresidues, 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 (p1)/2 quadratic residues.
Thus, there is at least one quadratic residue R (mod p) for which R + 1 = N, a quadratic nonresidue (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 nonzero 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 nonzero 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^{1}M'[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^{1}M'. We then have
[x1,y;y,x1][a;b] = [0;0].
Since (a,b) ≠ (0, 0) this is only possible if the determinant of [x1,y;y,x1] is 0. This determinant is (x1)^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^{1}M' 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 nonzero 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 p1 nonzero 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*(p1) + 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*(p1) + 2*p  1 = p^2, giving m = p1.
Last fiddled with by Dr Sardonicus on 20220729 at 13:52
Reason: fignix topsy
