Representing an integer as a sum of squares

Vera Serganova, Berkeley Math Circle, November 19, 2000

In how many ways can a given integer $ n $ be written as a sum of two squares? Let us start with an easier problem.

1. How many integer solutions does the equation

\begin{displaymath} x^{2}-y^{2}=n \notag\end{displaymath}  

have depending on an integer $ n? $

2. Show that the equation

\begin{displaymath} x^{2}+y^{2}=n \notag\end{displaymath}  

does not have an integer solution if $ n\equiv 3\left(\mod 4\right) $.

Denote by $ S\left(n\right) $ the number of integer solutions of the equation $ x^{2}+y^{2}=n $. Let $ z=x+iy $ be a complex number with integer real and imaginary part. Such a number is called a Gaussian integer. The set $ {\mathbb Z}\left[i\right] $ of all Gaussian integers is a ring, i.e. the set is equipped with addition and multiplication satisfying distributivity and associativity law.

3. Show that $ S\left(n\right) $ is the number of all Gaussian integers with absolute value $ n $. Show that if $ S\left(n\right)\not=0 $ and $ S\left(m\right)\not=0 $, then $ S\left(nm\right)\not=0 $.

The last problem motivates us to look at the equation

\begin{displaymath} x^{2}+y^{2}=p \notag\end{displaymath}  

for prime $ p $. Let $ {\mathbb Z}_{p} $ be the set of all remainders modulo $ p $ with naturally defined addition and multiplication. Note that $ {\mathbb Z}_{p} $ is a ring.

4. Show that the equation $ x^{2}+y^{2}\equiv 0\left(\mod p\right) $ has a non-zero solution in $ {\mathbb Z}_{p} $ if and only if the equation $ t^{2}\equiv -1\left(\mod p\right) $ has a solution in $ {\mathbb Z}_{p} $.

Let us recall some facts about the structure of $ {\mathbb Z}_{p} $. First we can divide by any non-zero element. Second, by Fermat theorem for all non-zero $ a $

\begin{displaymath} a^{p-1}\equiv 1\left(\mod p\right) \notag\end{displaymath}  

An element $ a $ in $ {\mathbb Z}_{p} $ is called primitive if every other non-zero element of $ {\mathbb Z}_{p} $ is a power of $ a $. For example, 2 is primitive in $ {\mathbb Z}_{13} $.

5. Show that a primitive element exists for all $ p $ and find the number of primitive elements in $ {\mathbb Z}_{p} $.

6. Show that $ -1 $ is a square in $ {\mathbb Z}_{p} $ if $ p\equiv 1\left(\mod 4\right) $.

7. How many solutions does the equation $ x^{2}+y^{2}\equiv 0\left(\mod p\right) $ have in $ {\mathbb Z}_{p}? $

8. Show that $ S\left(p\right)=8 $ if $ p=4k+1 $, $ S\left(p\right)=0 $ if $ p=4k+3 $, and $ S\left(2\right)=4 $.

9. Let $ n=2^{k_{0}}p_{1}^{k_{1}}\dots p_{r}^{k_{r}}q_{1}^{l_{1}}\dots q_{s}^{l_{s}} $, where $ p_{i}\equiv 1\left(\mod 4\right) $ and $ q_{j}\equiv 3\left(\mod 4\right) $ be the prime factorization of of $ n $. Show that $ S\left(n\right)\not=0 $ if and only if all $ l_{j} $ are even.

To obtain a formula for $ S\left(n\right) $ we look again at Gaussian integers.

10. Show that all invertible elements in $ {\mathbb Z}\left[i\right] $ are $ \pm1 $, $ \pm i $. Define what is a prime Gaussian integer. Which of the following are prime: $ 2,3+i,5,10+i? $

We are going to prove that every Gaussian integer can be factored into primes in unique way (up to multiplication by invertible number). Let us recall our old friend Euclidean algorithm.

A ring is called Euclidean if one can define a non-negative function $ g\left(a\right) $ on all non-zero elements such that $ g\left(ab\right)\geq g\left(a\right) $ and one can divide with remainder, i.e. for any $ a $ and $ b,a\not=0 $ one can write $ b=qa+r $ with $ g\left(r\right)<g\left(a\right) $ or $ r=0 $.

11. Show that the ring of integers and the ring of polynomials are Euclidean.

12. Show that $ {\mathbb Z}\left[i\right] $ is also Euclidean.

13. Show that in Euclidean rings a greatest common divisor exists and can be found by using Euclidean algorithm.

14. Show in a Euclidean ring every non-zero element is a product of primes and prime factors are defined uniquely up to multiplication by invertible elements.

Not all rings satisfy the unique factorizarion property.

15. Let $ {\mathbb Z}\left[\sqrt{ -3}\right] $ be the set of complex numbers $ x+y\sqrt{ -3} $ with integer $ x $ and $ y $. Then prime factorization is not unique.

16. Show that $ S\left(n\right)=4\left(k_{1}+1\right)\dots \left(k_{r}+1\right) $, assuming that $ k_{i} $ are as in Problem 9 and all $ l_{j} $ are even.

17. Show that if an integer is a sum of squares of two rational numbers, then it is a sum of two integer squares.

Let us attack another problem using the same method. Find the number of integer solutions of

\begin{displaymath} x^{2}+xy+y^{2}=n. \notag\end{displaymath}  

18. Let $ \varepsilon=\left(1+\sqrt{ -3}\right)/2 $, and $ {\mathbb Z}\left[\varepsilon\right] $ be the ring of complex numbers $ x+y\varepsilon $ with integer $ x $ and $ y $. Such numbers may be called triangular. Draw them on the complex plane. Show that $ \vert z\vert^{2}=x^{2}+xy+y^{2} $. Find all invertible elements.

19. Show that $ {\mathbb Z}\left[\varepsilon\right] $ is Euclidean.

20. Show that the equation $ x^{2}+xy+y^{2}\equiv 0 \left(\mod p\right) $ has a non-zero solution in $ {\mathbb Z}_{p} $ if $ p\equiv 1\left(\mod 3\right) $ or $ p=3 $.

21. The number of integer solutions of $ x^{2}+xy+y^{2}=p $ is 12 for $ p\equiv 1\left(\mod 3\right) $.

This result is harder, but you can try to prove it now.

Theorem. Any integer can be represented as a sum of four perfect squares.

22. Consider the ring $ {\mathbb Z}\left[i,j,k\right] $ of all the numbers $ z=x_{1}+x_{2}i+x_{3}j+x_{4}k $, $ x_{1},\dots ,x_{4} $ are integer, with multiplication defined by relations

\begin{displaymath} i^{2}=j^{2}=k^{2}=-1, \notag\end{displaymath}  


\begin{displaymath} ij=k\text{, }ij=-ji,ik=-ki,jk=-kj. \notag\end{displaymath}  

These are integer quaternions. Show that in general $ zy\not=yz. $ Let $ \vert z\vert=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2} $. Show that $ \vert zy\vert=\vert z\vert\vert y\vert $.

23. Show that $ x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=p $ has an integer solution for every $ p $. You will probably have to do the next problem first.

24. (Minkovsky Lemma) Let $ L $ be a lattice of full rank in $ {\mathbb R}^{n} $, i.e. the set of all integer linear combinations of $ n $ linearly independent vectors in $ {\mathbb R}^{n} $. Let $ V $ be the volume of a minimal parallelepiped generated by vectors from $ L $, and $ B $ be a convex body centrally symmetric with respect to the origin. If the volume of $ B $ is greater than $ 2^{n}V $ then $ B $ contains a non-zero point of the lattice.