ProofOfLagrangesFourSquareTheorem 2003-01-04 15:39:28 2008-01-23 00:03:12 Proof Lagrange's four-square theorem 0 % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) \usepackage{graphicx} % for neatly defining theorems and propositions \usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them \usepackage[usenames]{color} \usepackage{latexsym} % define commands here \newtheorem{thm}{Theorem} \newtheorem{lem}{Lemma} \PMlinkescapeword{complete} \PMlinkescapeword{clearly} The following proof is essentially Lagrange's original, from around 1770. First, we need three lemmas. \begin{lem} For any integers $a,b,c,d,w,x,y,z$, \begin{eqnarray*} (a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2) & = & (aw+bx+cy+dz)^2 \\ & + & (ax-bw-cz+dy)^2 \\ & + & (ay+bz-cw-dx)^2 \\ & + & (az-by+cx-dw)^2. \end{eqnarray*} \end{lem} This is the Euler four-square identity, q.v., with different notation. \begin{lem} If $2m$ is a sum of two squares, then so is $m$.\end{lem} \begin{proof} Say $2m=x^2+y^2$. Then $x$ and $y$ are both even or both odd. Therefore, in the identity $$m=\Big(\frac{x-y}{2}\Big)^2 + \Big(\frac{x+y}{2}\Big)^2,$$ both fractions on the right side are integers. \end{proof} \begin{lem} If $p$ is an odd prime, then $a^2+b^2+1=kp$ for some integers $a,b,k$ with $0<k<p$. \end{lem} \begin{proof} Let $p = 2n + 1$. Consider the sets $$A:=\lbrace a^2 \mid a=0,1,...,n\rbrace\quad\mbox{ and }\quad B:=\lbrace -b^2-1 \mid b=0,1,...,n \rbrace.$$ We have the following facts: \begin{enumerate} \item No two elements in $A$ are congruent mod $p$, for if $a^2\equiv c^2 \pmod p$, then either $p\mid (a-c)$ or $p\mid (a+c)$ by unique factorization of primes. Since $a-c, a+c \le 2n< p$, and $0\le a,c$, we must have $a=c$. \item Similarly, no two elements in $B$ are congruent mod $p$. \item Furthermore, $A\cap B=\varnothing$ since elements of $A$ are all non-negative, while elements of $B$ are all negative. \item Therefore, $C:=A\cup B$ has $2n+2$, or $p+1$ elements. \end{enumerate} Therefore, by the pigeonhole principle, two elements in $C$ must be congruent mod $p$. In addition, by the first two facts, the two elements must come from different sets. As a result, we have the following equation: $$a^2+b^2+1=kp$$ for some $k$. Clearly $k$ is positive. Also, $p^2 = (2n + 1)^2 > 2n^2 + 1 \ge a^2+b^2+1 = kp$, so $p > k$. \end{proof} Basically, Lemma 3 says that for any prime $p$, some multiple $0<m<p$ of $p$ is a sum of four squares, since $a^2+b^2+1=a^2+b^2+1^2+0^2$. \begin{proof}[Proof of Theorem] By Lemma 1 we need only show that an arbitrary prime $p$ is a sum of four squares. Since that is trivial for $p=2$, suppose $p$ is odd. By Lemma 3, we know $$mp=a^2+b^2+c^2+d^2$$ for some $m,a,b,c,d$ with $0<m<p$. If $m=1$, then we are done. To complete the proof, we will show that if $m>1$ then $np$ is a sum of four squares for some $n$ with $1\le n<m$. If $m$ is even, then none, two, or all four of $a,b,c,d$ are even; in any of those cases, we may break up $a,b,c,d$ into two groups, each group containing elements of the same parity. Then Lemma 2 allows us to take $n = m/2$. Now assume $m$ is odd but $>1$. Write \begin{eqnarray*} w & \equiv & a\pmod{m} \\ x & \equiv & b\pmod{m} \\ y & \equiv & c\pmod{m} \\ z & \equiv & d\pmod{m} \end{eqnarray*} where $w,x,y,z$ are all in the interval $(-m/2, m/2)$. We have $$w^2+x^2+y^2+z^2 < 4\cdot \frac{m^2}{4} = m^2$$ $$w^2+x^2+y^2+z^2\equiv 0\pmod{m}.$$ So $w^2+x^2+y^2+z^2 = nm$ for some integer non-negative $n$. Since $w^2+x^2+y^2+z^2 < m^2$, $n<m$. In addition, if $n=0$, then $w=x=y=z=0$, so that $a\equiv b\equiv c\equiv d \equiv 0 \pmod m$, which implies $mp=a^2+b^2+c^2+d^2=m^2q$, or that $m|p$. But $p$ is prime, forcing $m=p$, and contradicting $m<p$. So $0<n<m$. Look at the product $(a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2)$ and examine Lemma 1. On the left is $nm^2p$. One the right, we have a sum of four squares. Evidently three of them $$ax-bw-cz+dy=(ax-bw)+(dy-cz)$$ $$ay+bz-cw-dx=(ay-cw)+(bz-dx)$$ $$az-by+cx-dw=(az-dw)+(cx-by)$$ are multiples of $m$. The same is true of the other sum on the right in Lemma 1: $$aw+bx+cy+dz \equiv w^2+x^2+y^2+z^2 \equiv 0\pmod{m}.$$ The equation in Lemma 1 can therefore be divided through by $m^2$. The result is an expression for $np$ as a sum of four squares. Since $0<n<m$, the proof is complete. \end{proof} \textbf{Remark:} Lemma 3 can be improved: it is enough for $p$ to be an odd number, not necessarily prime. But that stronger statement requires a longer proof.