# Probability that $x^2+y^2+z^2=0$ mod $p$

This question on MSE asked the following:

"Given $x,y,z \in \mathbb{N},$ find probability that $x^2+y^2+z^2$ is divisible by $7.$"

The OP did not declare the assumed probability model, and was duly criticised for that. On the other hand, it is only natural to assume that $x$, $y$, $z$ are independently uniformly distributed mod $7$.

A case analysis then shows that that the probability in question is ${1\over7}$. This simple result led me to solve the same problem for the primes $p=3$, $5$, $11$, and $13$. In each case I obtained ${1\over p}$ as result. Further experiments showed that the remainder of $s=x^2+y^2+z^2$ mod $p$ is not uniformly distributed mod $p$, but that in any case the probability of $s=0$ mod $p$ is equal to ${1\over p}$ for all $p\leq107$. This leads to the following

Conjecture. Let the integeres $x$, $y$, $z$ be independently uniformly distributed modulo the prime $p$. Then the probability that $s:=x^2+y^2+z^2$ is divisible by $p$ is equal to ${1\over p}$.

Maybe this well known. Otherwise I'd like to see a proof.

• If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $\Bbb N$. Feb 27, 2017 at 20:38
• so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation.... Feb 27, 2017 at 20:47

Found it. Given odd dimension $$n$$ and quadratic form $$f = a_1 x_1^2 + a_2 x_2^2 + \cdots + a_n x_n^2,$$ everything in a finite field with odd number of elements $$q,$$ the count $$\#\left(f = b\right) \; = \; q^{n-1} + q^{(n-1)/2} \; \; \chi \left( \; (-1)^{(n-1)/2} \; b a_1 a_2 \ldots a_n\right).$$ At the bottom of page 91 Small points out that $$\#\left(f = 0\right) \; = \; q^{n-1} .$$ When $$b \neq 0$$ we need to know what $$\chi$$ means.

Aah. Page 86, very simple. We have finite field $$F$$ and element $$a.$$ First $$\chi(0) = 0.$$ If $$a$$ is a nonzero square, $$\chi(a)=1.$$ If $$a$$ is nonzero and not a square, $$\chi(a)=-1.$$

Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,

For the equation $$x^2 + y^2 + z^2 \equiv 0 \pmod{p}$$, where $$p$$ is a prime number, we want to find the probability that this congruence holds for randomly chosen integers $$x$$, $$y$$, and $$z$$ modulo $$p$$.

Let's consider two cases:

1. If $$p = 2$$, then any integer squared modulo 2 is either 0 or 1. Therefore, for $$x^2 + y^2 + z^2 \equiv 0 \pmod{2}$$ to hold, all three variables ($$x$$, $$y$$, and $$z$$) must be congruent to 0 modulo 2. In other words, they must be even. The probability of a randomly chosen integer being even is $$\frac{1}{2}$$.

2. If $$p$$ is an odd prime, we can use the Three Squares Theorem. This theorem states that for an odd prime $$p$$, the equation $$x^2 + y^2 + z^2 \equiv 0 \pmod{p}$$ has solutions if and only if $$p \equiv 1 \pmod{4}$$ or $$p = 2$$. If $$p \equiv 3 \pmod{4}$$, the equation has no solutions.

So, for odd primes $$p$$ where $$p \equiv 1 \pmod{4}$$ or $$p = 2$$, there are solutions to the equation, and for primes $$p$$ where $$p \equiv 3 \pmod{4}$$, there are no solutions.

To calculate the probability, we need to consider the distribution of primes. The density of primes congruent to $$1 \pmod{4}$$ versus congruent to $$3 \pmod{4}$$ is roughly equal, and the density of primes is inversely proportional to their size. Therefore, you can approximate the probability as:

• For $$p = 2$$: Probability is $$\frac{1}{2}$$.
• For odd primes $$p$$ where $$p \equiv 1 \pmod{4}$$: Probability is close to $$\frac{1}{2}$$ because roughly half of the primes fall into this category.
• For odd primes $$p$$ where $$p \equiv 3 \pmod{4}$$: Probability is close to 0 because roughly half of the primes fall into this category.

This is a probabilistic analysis based on the distribution of primes, and it provides a general idea of what to expect when considering random primes.

• I'm not familiar with the three squares theorem, but $5^2+7^2+11^2 \equiv 0 \bmod 3$, seemingly contradicting "if $p\equiv 3 \bmod 4$ the equation has no solutions." 21 hours ago
• The case for $p=2$ gets the right answer in the wrong way. The variables $x,y,z$ can all be even (probability $1/8$) or two odd and one even (probability $3/8$). An example of this second type is $1^2+2^2+3^2$. 19 hours ago