I want to find all the lattice points on a sphere with integer radius, or equivalently all solutions to the diophantine equation $x^2+y^2+z^2=r^2$. We can see from oeis that the number of solutions, including redundant solutions that are permutations or reflections of other solutions, is $6a(r)$ where $a$ is a multiplicative function with $a(2^e)=1$, $a(p^e)=p^e$ for $p\equiv 1\mod 4$, and $a(p^e)=(p^e+2\frac{p^e-1}{p-1})$ otherwise. This is encouraging because it suggests the approach of finding solutions modulo some primes and then reconstructing solutions over the integers might be a good approach.
Consider $r=15$. By an exhaustive search, we can find all the lattice points (up to reflection/permutation) are $(15,0,0),(14,5,2),(12,9,0),(11,10,2),(10,10,5)$. However, if we consider the equation $x^2+y^2+z^2=15^2$ modulo $3$ and $5$, we get $9$ solutions modulo $3$ and $25$ modulo $5$. In particular, $(0,0,0)$ and all reflections of $(1,1,1)$ (remember $2\equiv-1\mod 3$) are the solutions modulo 3 and $(0,0,0)$ and all reflections and permutations of $(2,1,0)$ are the solutions modulo $5$.
Now we can try to lift the solutions modulo $3$ and $5$ to get integer solutions. First, notice that we can ignore permutations of the solutions modulo $5$. This is because if we are lifting solutions modulo a bunch of primes, we only care about getting one permutation of each solution over the integers, so only the permutation of the modulo solutions relative to each other matter, so we can choose only one permutation for each modulo solution for the prime with the most solutions to reduce work.
When we lift the modulo solutions, we have $5$ solutions modulo $5$ due to ignoring permutations but not reflections. We have $9$ solutions modulo $3$ due to considering both permutations and reflections. So we have $45$ potential solutions, and obviously these will not all be solutions because we know there are only $150$ lattice points on the whole sphere meaning in the nonnegative domain there are about $25$. In fact, we get $7$ solutions, which include all solutions, sometimes with several permutations.
For the solution $(0,0,0)$ modulo $5$, we get $(15,0,0)$ with the solution $(0,0,0)$ mod $3$, $(10,10,5)$ and its permutations for $(1,1,2)$ and its permutations, and the other solutions mod $3$ do not lead to a solution over the integers.
For $(2,1,0)$ mod $5$, we only get $(2,11,10)$ for $(2,2,1)$ and no solution over the integers for other solutions mod $3$.
For $(2,4,0)$ mod $5$, we get $(12,9,0)$ for $(0,0,0)$, $(2,14,5)$ for $(2,2,2)$, and no solution over the integers for other solutions mod $3$.
For other solutions mod $5$, we do not get any solutions over the integers for any solution mod $3$.
So working modulo $3$ and $5$ worked in that we were able to recover all the integer solutions up to permutation and reflection. However, only $7$ out of $45$ pairs of modulo solutions lead to integer solutions, and I don't see much of a pattern to it. If we included all permutations of the solutions modulo $5$, it would be $15$ out of $225$, an even worse ratio, albeit one with more suggestive numbers.
Some patterns do suggest themselves, for instance $(3,1,0)$ and $(3,4,0)$ mod $5$ both lead to no solutions over the integers, as does $(1,1,1)$, $(2,1,2)$, and $(1,2,2)$. This seems useful, and it seems like perhaps we could cull solutions based on sign similar to what we did for permutations, but of course which of these solutions leads to solutions over the integers or not depends on which permutation of the solution modulo $5$ we chose to actually work with.
Aside from working modulo small primes and recovering proper integer solutions, I have also considered thinking about the lattice points on the sphere as a group under the cross product (plus reflection into the canonical region where $0 \le z \le y \le x$), but I have not investigated that much yet.
Is there a good way to generate all lattice points on a sphere? If lifting solutions modulo prime divisors of the radius, is there a better way to cull which pairs will lead to a solution over the integers?