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

table of values

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

scatter plot

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

  • 3
    $\begingroup$ It's oeis.org/A086933, maybe some referrences there can help $\endgroup$ – Sil Nov 28 '20 at 14:41
  • $\begingroup$ 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}$. $\endgroup$ – TheSimpliFire Nov 28 '20 at 15:32
  • $\begingroup$ @TheSimpliFire It is a multiplicative function, it doesn't have an asymptotic, in contrary to its summatory function $\endgroup$ – reuns Nov 28 '20 at 18:54
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$$

  • $\begingroup$ 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. $\endgroup$ – Malkin Nov 29 '20 at 13:24
  • 1
    $\begingroup$ 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$. $\endgroup$ – Paul Sinclair Nov 29 '20 at 16:14
  • $\begingroup$ I've never come across the concept of a Gaussian prime; they seem very relevant to my problem. Thanks a lot! $\endgroup$ – Malkin Nov 29 '20 at 19:44
  • $\begingroup$ 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})$. $\endgroup$ – Malkin Nov 29 '20 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.