4
$\begingroup$

How many solutions has the equation

$$x^2+y^2+z^2=0,$$

in the finite field $\mathbb Z_p$, where $p$ is a prime number?

  • 1
    Hint, or at least a possible starting point: There are $\frac{p+1}{2}$ squares $\pmod{p}$.2012-12-15
  • 0
    are those all squares2012-12-15
  • 0
    ... also known as quadratic residues.2012-12-15
  • 0
    @DanBrumleve How do you prove that?2012-12-15
  • 1
    @Mario: The comments are for clarifying or otherwise discussing the question, not for questions of your own about established facts mentioned in other comments, the answer to which would require another lengthy comment. You can post that question as a question of your own.2012-12-15
  • 1
    @DanBrumleve I was just looking for a reference. It's not really big enough for a question IMO. Also, it's not like it's off-topic, since it is evidently an important part of the proof, in your mind.2012-12-15
  • 0
    See [here](http://en.wikipedia.org/wiki/Quadratic_residue#Prime_modulus). My idea is that if we choose $x$ and $y$ freely, then there is about a 50% chance that a $z$ can be found to satisfy the equation. So the answer should be about $\frac{p^2}{2}$.2012-12-15
  • 1
    @DanBrumleve: if such a $z$ can be found, then $-z$ also works. So the answer should be about $p^2$ - which is the same prediction as just saying the left-hand side takes all $p$ possible values about equally often.2012-12-15
  • 0
    @Dan: that's not true at all. If you take the sum of two squares, then the probability of their being a square again is surely much lower than 50%. What you wrote would be true if the equation stood as $x + y + z^2 = 0$ or something like that.2012-12-15
  • 1
    @Marek: you're thinking of squares in the integers, which are very rare. But squares in finite fields are plentiful: (slightly) over half the elements are squares.2012-12-15
  • 0
    @Greg: no, I am not thinking of that. My point was that if you choose both $x$ and $y$ randomly, then squares of both of them only cover half of the elements and I thought that their sum will not be uniform over the elements, preferring non-squares. But this is not true.2012-12-15
  • 0
    See the following more general discussion: http://math.stackexchange.com/questions/183097/number-of-solutions-of-x2-1-dotsx2-n-0-x-i-in-bbbf-q/2012-12-15

3 Answers 3

0

Here's a way to calculate the exact answer when $p\equiv1\pmod4$: choose $s$ to satisfy $s^2\equiv-1\pmod p$, and write the desired congruence as $(x+sy)(x-sy) \equiv -z^2 \pmod p$. The matrix $\begin{pmatrix}1&s\\1&-s\end{pmatrix}$ has determinant $-2s$, which is invertible modulo $p$; therefore the pair $u=x+sy,v=x-sy$ runs through every pair of residues modulo $p$ exactly once each as the pair $x,y$ does. Also, $w=sz$ runs through all residues modulo $p$ as $z$ does. So we just need to count the solutions of $$ uv\equiv w^2\pmod p, $$ since $w^2=(sz)^2 \equiv -1\cdot z^2\pmod p$. There are $2p-1$ solutions with $uv\equiv0\pmod p$, and $2$ solutions for each of the $(\frac{p-1}2)^2$ pairs $u,v$ of quadratic residues, and $2$ solutions for each of the $(\frac{p-1}2)^2$ pairs $u,v$ of quadratic nonresidues, for a total of exactly $p^2$ solutions.

Some quick computation indicates that the answer is always exactly $p^2$. Any ideas?

  • 0
    For the other case, can't you just adjoin the root of $x^2 + 1$ and work in that field? And in the end use the fact that solutions lying in the original field will be invariant under conjugation.2012-12-15
1

When $p$ is odd the equation $x^2+y^2+z^2=0$ describes a non-singular conic $\cal C$ in the projective plane $\Bbb P^2(\Bbb F_q)$ where $\Bbb F_q$ is the finite field with $q=p^f$ elements.

Also $\cal C(\Bbb F_q)$, the set of points in $\cal C$ with coordinates in $\Bbb F_q$, is non-empty: indeed either $p$ or $2p$ is $\not\equiv7\bmod 8$, so by a theorem of Gauss either $p$ or $2p$ is the sum of three squares, providing a point $P\in\cal C(\Bbb F_p)$.

Now, considering the chords (and the tangent) through P, the second intersection sets up a bijection $$ \cal C(\Bbb F_q)\longleftrightarrow\Bbb P^1(\Bbb F_q). $$ Thus $|\cal C(\Bbb F_q)|=|\Bbb P^1(\Bbb F_q)|=q+1$.

We conclude recalling that $\Bbb P^2(\Bbb F_q)=(\Bbb F_q^3-\{(0,0,0)\})/\Bbb F_q^\times$ so that the total number of solutions in $\Bbb F_q^3$ is $$ |\cal C(\Bbb F_q)|(q-1)+1=(q+1)(q-1)+1=q^2. $$

Finally, when $p=2$ there is an identity $$ x^2+y^2+z^2=(x+y+z)^2 $$ so we are actually computing the number of points in an hyperplane in $\Bbb F_q^3$ which is again $q^2$ by a dimension argument.

1

If $p=1 \pmod 4$ then there is some $i \in \Bbb F_p$ such that $i^2+1=0$, and after doing a bijective change of variable, $x^2+y^2 = (x+iy)(x-iy) = uv$. Now, $uv$ has the value $0$ when either $u$ or $v$ are $0$, i.e. $2p-1$ times. Moreover it takes any other value in $\Bbb F_p$ exactly $p-1$ times. Using this, there are $(2p-1)+(p-1)(p-1) = p^2$ solutions to $x^2+y^2 = -z^2$

If $p=3 \pmod 4$, then there is only one solution to $x^2+y^2=0$. For nonzero $z$, after adjoining a square root of $-1$ and doing a change of variable in $\Bbb F_{p^2}$ we need to describe the distribution of $(x+iy)(x-iy) = u \overline{u}$ for $u \in \Bbb F_{p^2}^*$. Let $f : u \in \Bbb F_{p^2} \mapsto u \overline{u} \in \Bbb F_p^*$. $f$ is a group morphism, and $\overline{u}=u^p$ thus $f(u) = u^{p+1}$. Therefore, $\ker f$ is the subgroup of $(p+1)$th roots of unity in $\Bbb F_{p^2}^*$, which is of size $p+1$. Then, the image of $f$ has to contain $(p^2-1)/(p+1) = p-1$ elements, hence it is surjective : for every nonzero $z$ there are exactly $p+1$ solutions to $x^2+y^2=z$.
Using this we can count the number of solutions to $x^2+y^2= -z^2$, which is $1+(p+1)(p-1)=p^2$