Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Hint, or at least a possible starting point: There are $\frac{p+1}{2}$ squares $\pmod{p}$. –  Dan Brumleve Dec 15 '12 at 8:54
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. –  joriki Dec 15 '12 at 9:52
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. –  Mario Carneiro Dec 15 '12 at 10:08
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. –  Greg Martin Dec 15 '12 at 10:31
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. –  Greg Martin Dec 15 '12 at 10:42

3 Answers 3

up vote 1 down vote accepted

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$

share|improve this answer
    
Thank you Mercio –  zacarias Dec 15 '12 at 14:24

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.

share|improve this answer
    
Thank you Andrea Mori. –  zacarias Dec 15 '12 at 14:23

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?

share|improve this answer
    
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. –  Marek Dec 15 '12 at 10:55
    
thank you Greg Mertin. –  zacarias Dec 15 '12 at 14:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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