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

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.)}}$$

• It's oeis.org/A086933, maybe some referrences there can help – Sil Nov 28 '20 at 14:41
• From the OEIS link in @Sil's comment we have $N\sim\frac{(2d+1)\pi}{8G}$. So for large $d$ the ratio $\frac Nd$ tends to $\frac\pi{4G}$. – TheSimpliFire Nov 28 '20 at 15:32
• @TheSimpliFire It is a multiplicative function, it doesn't have an asymptotic, in contrary to its summatory function – reuns Nov 28 '20 at 18:54
• I made the exact same picture some time ago, but for larger $d$ (and a bit more artistic freedom of the coloring): imgur.com/L9wLHrI . To get you a bit more started, the fact that $N(d)$ is multiplicative follows from the Chinese Remainder Theorem. – Kenneth Goodenough Nov 28 '20 at 23:34

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$$

• Thank you! And to @Sil for the original link to the OEIS. I'll have a play with the Chinese Remainder Theorem to figure out why the function is multiplicative. It might also give some insight into the patterns. – Malkin Nov 29 '20 at 13:24
• You should look at the problem using Gaussian Integers. When $d, x, y$ are relatively prime, since $d \mid (x +iy)(x-iy)$, every gaussian prime divisor of $d$ must also divide only one of $x + iy$ or $x - iy$. – Paul Sinclair Nov 29 '20 at 16:14
• I've never come across the concept of a Gaussian prime; they seem very relevant to my problem. Thanks a lot! – Malkin Nov 29 '20 at 19:44
• I think I've gotten my head around $N(d)$ being multiplicative. Sketching out the beginnings of a proof: for primes $p_1$, $p_2$ and integers $n_1,n_2$, choose $0\leq x_i,y_i \leq p_i^{n_i}$ such that $x_i^2+y_i^2 \equiv 0 \pmod{p_i^{n_i}}$ for $i=1,2$. Then by the CRT, $\exists ! x,y$ with $0\leq x,y \leq p_1^{n_1} p_2^{n_2}$ such that $x \equiv x_i \pmod{p_i^{n_i}}$ and $y \equiv y_i \pmod{p_i^{n_i}}$. It follows that $x^2+y^2 \equiv 0 \pmod{p_1^{n_1}p_2^{n_2}}$. The uniqueness of these $x,y$ leads to $N(p_1^{n_1}p_2^{n_2})=N(p_1^{n_1})N(p_2^{n_2})$. – Malkin Nov 29 '20 at 20:04