2
$\begingroup$

It is easy to prove that for prime $p$ every element of $\mathbb{Z} / p \mathbb{Z}$ can be written as the sum of two squares. An elementary proof is given here: Sum of two squares modulo p

How can we show that, provided further $p \geq 7$, any nonzero element of $\mathbb{Z}/ p \mathbb{Z}$ is the sum of two nonzero squares? I don't see how we could extend the counting argument used in the linked post to this case. Thanks

$\endgroup$
3
  • $\begingroup$ Are you sure that this should be true? That is, is it an exercise from a book or something? $\endgroup$ – ajotatxe Aug 30 '17 at 11:38
  • $\begingroup$ It's an exercise from a course I'm taking, so it should be true. Do you have a counterexample? $\endgroup$ – Rafa Aug 30 '17 at 11:47
  • $\begingroup$ No, I don't. Just making sure of not trying to prove a false statement. $\endgroup$ – ajotatxe Aug 30 '17 at 11:48
2
$\begingroup$

Adapting Mikhail Ivanov's argument to a slightly different but AFAICT equivalent question to fit here. Some of the elements appeared also in my answer to that question.


Every non-zero element of $\Bbb{Z}/p\Bbb{Z}$ is either a square or a non-square If $a=b^2$ is a non-zero square, then, as $p>5$ we have $$ a=b^2=(3b/5)^2+(4b/5)^2 $$ as a sum of two non-zero squares.

On the other hand, if $a$ is a non-zero non-square then $ab^2$ is a non-zero non-square for any $b\neq0$. Furthermore, we get all the non-squares in this way. If $a=x^2+y^2$ with $xy\neq0$, then $ab^2=(bx)^2+(by)^2$, so it suffices to show that we can write at least one of the non-squares as a sum of two non-zero squares. Let's pretend for one time's sake that $\Bbb{Z}/p\Bbb{Z}$ has an "order", so $0<1<2<\ldots<p-1$. Let $a$ be the smallest non-square in this order. Clearly $a>1$. It follows that $a-1=b^2$ is a square, where $b\neq0$. This implies that $a=1+b^2$ is a sum of two non-zero squares. Therefore so are all the other non-squares.

$\endgroup$
3
  • $\begingroup$ Thanks, that's great $\endgroup$ – Rafa Aug 31 '17 at 7:48
  • $\begingroup$ How can we guarantee that division by 5 holds? For example, let p = 7, b = 2. Then there is no number n such that 5n = 6. $\endgroup$ – Samuel Barkes May 17 '20 at 20:18
  • 1
    $\begingroup$ @SamuelBarkes In $\Bbb{Z}/7\Bbb{Z}$ we have $5\cdot4=6$. Because $5\cdot3=1$ in that field, we have $x/5=3x$ for all $x$. In your example case $6/5=3\cdot6=4$. $\endgroup$ – Jyrki Lahtonen May 17 '20 at 20:59
1
$\begingroup$

Let's prove that $1$ is the sum of two nonzero squares.

Think about the geometry of the plane. Any non-vertical line through $(1,0)$ will meet the unit circle in another point. This argument works over $k=\Bbb Z/p\Bbb Z$ too. The "non-vertical" lines through $(1,0)$ are $y=m(x-1)$, and each meets the unit circle in the further point $((m^2-1)/(m^2+1),2m/(m^2+1))$, as long as $m^2\ne-1$. These coordinates are nonzero iff $m\notin\{0,1,-1\}$. There are at most five "bad" values of $m$, so if $p>5$, then $1$ is the sum of two non-zero squares in $k$.

By scaling, each non-zero square is the sum of two non-zero squares in $k$. Of course, if $b$ is not a square, it is still the sum of two squares, and they are both nonzero.

$\endgroup$
3
  • $\begingroup$ "This argument works over $k=\Bbb Z/p\Bbb Z$ too". Why? If fact, we have $3^2+3^2\equiv 4^2+6^2\equiv 1\pmod{17}$. That is, for $p=17$, the line intersects the circle at three points. $\endgroup$ – ajotatxe Aug 30 '17 at 13:52
  • $\begingroup$ @Lord Shark the Unknown , I have been used your answer to complete my proof. $\endgroup$ – Davood KHAJEHPOUR Aug 30 '17 at 14:06
  • $\begingroup$ @ajotatxe Really, there is no line in the affine plane $k^2$ that meets the circle $x^2+y^2=1$ in three distinct points. $\endgroup$ – Angina Seng Aug 30 '17 at 14:32
1
$\begingroup$

This is not a complete answer, since a crucial part is not proved.

Conjecture: Given an odd prime $p$, the cardinal of the set $$A_p=\{(x,y):0\le x\le(p-1)/2,\, 0\le y\le(p-1)/2,\, x^2+y^2\equiv 1\!\!\!\!\!\mod p\}$$ is $$\begin{cases}(p+3)/4\text{ if } p\equiv 1\pmod 4\\(p+5)/4\text{ if }p\equiv 3\pmod 4\end{cases}$$

This conjecture is based in evidence for odd primes less than $2000$, that I have tried using a program.

Now, assuming this conjecture, let's prove the statement. Take $a\in\Bbb Z_p^\times$ and suppose that $a$ is not the sum of two nonzero squares. Since $a$ is the sum of two squares, we see that $a$ must be a square itself, say $a=b^2$.

The conjecture implies that the number of elements in $A_p$ is at least $3$ for $p\ge 7$. Then, $A_p$ contains an element other than $(1,0)$ and $(0,1)$. This shows that $1$ is the sum of two nonzero squares. That is, $$x^2+y^2\equiv 1\pmod p$$ And, now, multiplying by $b^2$ (which is not $0$), we get $$(bx)^2+(by)^2\equiv a\pmod p$$

$\endgroup$
1
  • 3
    $\begingroup$ I'm fairly sure that in Ireland & Rosen the formula for the solutions of $x^2+y^2=1$ is proven. It gives $|A_p'|=p-\left(\dfrac{-1}p\right)$, where $A_p'$ is the set of solutions $(x,y)$ with the bounds $0\le x,y\le p-1$. I think that this suffices for your argument. I did something similar here. $\endgroup$ – Jyrki Lahtonen Aug 30 '17 at 15:28
0
$\begingroup$

Lemma: Let $7 \leq p$ be a prime number; then $1$ can be written as the sum of two non-zero squares.
Proof: See the answer of Lord Shark the Unknown to this question.



Let $a \in \left(\dfrac{\mathbb{Z}}{\mathbb{pZ}}\right)^*$ be arbitrary; let's define the sets $A_a$ and $B$ as follows:

$$ B:= \Bigg{\{} x^2 : x \in \dfrac{\mathbb{Z}}{\mathbb{pZ}} \Bigg{\}} ; \\ A_a:= a-B= \Bigg{\{} a-x^2 : x \in \dfrac{\mathbb{Z}}{\mathbb{pZ}} \Bigg{\}} ; $$

notice that, each of the above sets has exactly $\dfrac{p+1}{2}$ elements.


Claim: $B \cap A_a \neq \phi$, in other words there is $t \in \dfrac{\mathbb{Z}}{\mathbb{pZ}} $ such that $t^2 \in B$ and $t^2 \in A_a$.
Prood: Suppose on contrary $B \cap A_a = \phi$; so we can conclude that: $\Big{|}B \cup A_a \Big{|} = \Big{|} B \Big{|} + \Big{|} A_a \Big{|}$;
on the other hand we know $B \cup A_a \subseteq \dfrac{\mathbb{Z}}{\mathbb{pZ}}$, so we can conclude that:

$$ p+1 = \dfrac{p+1}{2} + \dfrac{p+1}{2} = \Big{|} B \Big{|} + \Big{|} A_a \Big{|} = \Big{|} B \cup A_a \Big{|} \leq \Big{|} \dfrac{\mathbb{Z}}{\mathbb{pZ}} \Big{|} = p ; $$

which is an obvious contradiction.



Remark : Let $7 \leq p$ be a prime number, then every nonzero element $a \in \left(\dfrac{\mathbb{Z}}{\mathbb{pZ}}\right)^*$ can be written as the sum of two non-zero squares.
Proof : By the above claim, there is $x \in \dfrac{\mathbb{Z}}{\mathbb{pZ}} $ such that $x^2 \in A_a$,
so there is $y \in \dfrac{\mathbb{Z}}{\mathbb{pZ}} $ such that $x^2=a-y^2$; which proves the remark.


Proof of the original problem:

By the previous remark every $a \in \left(\dfrac{\mathbb{Z}}{\mathbb{pZ}}\right)^*$ can be written in the form $x^2+y^2$; notice that $(x,y)\neq (0,0)$, so we have the following cases:

  • $x \neq 0$ and $y \neq 0$; in this case there is nothing left to prove. $\checkmark$

  • $x \neq 0$ and $y = 0$ . By the lemma, $1$ can be written in the form $a^2+b^2$; where both of $c, d$ are non-zero, only notice that: $$ a \overset{p}{\equiv} 1 \cdot a \overset{p}{\equiv} (c^2+d^2) (x^2+0^2) \overset{p}{\equiv} (cx)^2+(dx)^2 . $$

  • $x = 0$ and $y \neq 0$ . By the lemma, $1$ can be written in the form $a^2+b^2$; where both of $c, d$ are non-zero, only notice that: $$ a \overset{p}{\equiv} 1 \cdot a \overset{p}{\equiv} (c^2+d^2) (0^2+y^2) \overset{p}{\equiv} (cy)^2+(dy)^2 . $$

$\endgroup$
5
  • 1
    $\begingroup$ How do we know that $x, y$ are nonzero? $\endgroup$ – Rafa Aug 30 '17 at 10:51
  • $\begingroup$ We've specified that $p \geq 7$, so the first doesn't apply, and for the second $4 \equiv 1^2 + 4^2 (\mathrm{ mod } 13)$. $\endgroup$ – Rafa Aug 30 '17 at 11:01
  • 1
    $\begingroup$ Given the hypothesis in the question (i.e. $p \geq 7$), can we show that any nonzero element is the sum of two nonzero squares? $\endgroup$ – Rafa Aug 30 '17 at 11:03
  • $\begingroup$ $5 = 1^2 + 2^2$ though? $\endgroup$ – Rafa Aug 30 '17 at 11:05
  • $\begingroup$ @Rafa , Dear Rafa, I have been used; the other answer to this question ; as a lemma, to complete my proof. I have edited my answer. $\endgroup$ – Davood KHAJEHPOUR Aug 30 '17 at 14:08
0
$\begingroup$

Since $\mathbf F_p :=\mathbf Z /p\mathbf Z$ is a field, it seems adequate to heartily use the theory of finite fields, more specifically the central result that an extension $\mathbf F_q /\mathbf F_p$, with $q=p^n$, is Galois with cyclic group of order $n$ generated by the Frobenius automorphism $\phi: x \to x^p$. It follows easily that the norm map $N:\mathbf F_q^{*} \to \mathbf F_p^{*}$ is surjective. For later use, I include a quick proof : by Hilbert's 90, $x\in KerN$ iff $x$ is of the form $\phi(z)/z = z^{p-1}$; in particular, since $\mathbf F_q^{*}$ is cyclic, $KerN$ has order $(q-1)/(p-1)$, hence $ImN$ has order $p-1$, i.e. $N$ is surjective.

Apply this for $n=2$ : if $p\neq 2$, then $\mathbf F_{p^2} = \mathbf F_p (\sqrt d)$ where $d$ is the class of a non quadratic residue mod $p$, hence every $x\in \mathbf F_p^{*}$ can be written $x=a^2 -db^2$ = a sum of two squares. But one of these squares could still be zero, so it remains to prove that every element of $(\mathbf F_p^{*})^2$ is a sum of two nonzero squares, or equivalently that $1=x^2+y^2, xy\neq0$. The latter property has been shown in the answers given by @Jyrki Lahtonen and @Lord Shark the Unknown. Although it's not necessary to give all the solutions $(x, y)$, let's provide a parametrization analogous to that of the pythagorean triples ((3, 4, 5) is the "first" such triple). Put $1=a^2-db^2$= a norm from $\mathbf F_p (\sqrt d)$ with $d$ as above. The same argument using Hilbert's 90 will give $a+b\sqrt d= \phi(z)/z$, and writing $z=e+f\sqrt d$, we'll get $a=(e^2+df^2)/(e^2-df^2)$ and $y=-2ef/(e^2-df^2)$ . For example, if $d=-1$, we recover $(\frac 35)^2 + (\frac 45)^2 =1$ by taking $e=2, f=-1$.

$\endgroup$

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.