How many zeros does $x^2 + y^2 \pmod d$ have on $[0, d-1]^2$?

Question

I have been doing some work on Pythagoras's Theorem with my Year 8 Maths class (7th Grade in US speak). I had them investigating what values were unobtainable for the square on the hypotenuse of right-angled triangles with integer lengths. In other words, the values that $x^2+y^2$ can take for integers $x,y$.

One student decided to start looking at the factors of $x^2+y^2$. They came up with the following question (in slightly less formal language):

Given a positive integer $d$, when is $x^2+y^2 \equiv 0\pmod d$, for integers $x$ and $y$?

I created this Geogebra resource to visualise where the zeros occur (unexpectedly creating some beautiful patterns).

Some values of $d$, like $d=17$ and $d=25$, give loads of zeros. Others, like $d=19$, give zeros only when $xy \equiv 0 \pmod {19}$.

The following table gives the number of zeros ($N$) of $x^2+y^2 \pmod d$ for integer $(x,y) \in [0,d-1]^2$, for $d=1,...,20$:

... and this scatter graph plots $N/d$ against $d$ for $d=1,...,40$:

I am now stuck with the following questions:

• Given $d$, is it possible to predict $N$? (The values of $N$ seem dependent upon whether $d$ is a square number and whether $d$ occurs in a Pythagorean Triple, but with some weird exceptions like $15$ and $25$.)
• Is there some intuitive explanation of the wavy patterns that are generated by plotting $x^2+y^2 \pmod d$, as in the Geogebra app?

Any guidance appreciated! Thank you.

$\small{\textrm{(Image: the contrast of each coordinate is proportional to $x^2+y^2 \pmod {40}$, with zeros highlighted pink.)}}$

Answer 1

Some information copied over from oeis.org/A086933, but in the OP's notation.

$N(d)$ is a multiplicative function. That is, if $c, d$ are relatively prime, then $N(cd) = N(c)N(d)$. Also

• $N(2^e) = 2^e$
• $N(p^e) = ((p-1)e+p)p^{e-1}$ for primes $p \equiv 1 \mod 4$
• $N(p^e) = p^{e-(e \bmod 2)}$ for primes $p \equiv 3 \mod 4$.

For example, $300 = 2^2\cdot3\cdot5^2$. Now, $3 \equiv 3\mod 4$ and $5\equiv 1 \mod 4$, so

• $N(2^2) = 2^2 = 4$,
• $N(3) = N(3^1) = 3^{1-(1\bmod 2)} = 3^{1 - 1} = 3^0= 1$,
• $N(5^2) = ((5-1)\cdot2 + 5)\cdot 5^{2-1} = 13\cdot 5 = 65$.

Therefore $N(300) = 4\cdot1\cdot 65 = 260$.

From this we can see that $N(d) = 1$ if and only if $d$ is a product of distinct primes congruent to $3\bmod 4$.

Another formula for $N(d)$ is: $$N(d) = \sum_{r|d, r \text{ odd}} (-1)^{(r-1)/2}{\phi(r)}\frac dr$$