Legendre’s three-square theorem

A natural number ${n}$ can be written can sum of three squares, ${n=X^{2}+Y^{2}+Z^{2}}$ if and only if ${n}$ is not of the form ${n=4^{a}(8 b+7)}$ for nonnegative integers ${a}$ and ${b}.$

Modulo ${8}$ every square has to be ${0}$ , ${1}$ or ${4}$ and hence ${n}$ cannot be ${7 \mod 8.}$ Also if ${4}$ divides ${n}$ then ${X, Y, Z}$ all have to be even. These two facts prove the only if part.

Now to show the existence of solutions for ${n}$ which satisfies these constraints- we use reduction of ternary quadratic forms, and the fact that ${X^2+Y^2+Z^2}$ is the the unique quasi-reduced form of discriminant ${1}$ . Given these facts, if we can create some ternary quadratic form of the same discriminant which represents ${n}$ , by changing coordinates, we can reduce it to ${X^2+Y^2+Z^2}$ (by the uniqueness) and hence found solutions of ${X^2+Y^2+Z^2=n}$

$\displaystyle F(X,Y,Z)=a_{11} X^{2}+a_{22} Y^{2}+a_{33} Z^{2}+2 a_{12} X Y+2 a_{13} X Z+2 a_{23} Y Z$

$\displaystyle =[X, Y, Z]\left[\begin{array}{lll}a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33}\end{array}\right] \left[\begin{array}{l}X \\ Y \\ Z\end{array}\right]$

$\displaystyle M_F=\left[\begin{array}{lll}a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33}\end{array}\right]$

Let ${ \left[\begin{array}{lll}A_{11} & A_{12} & A_{13} \\ A_{12} & A_{22} & A_{23} \\ A_{13} & A_{23} & A_{33}\end{array}\right]}$ be the adjoint of ${M_F.}$

A positive-definite ternary quadratic form ${F}$ is called quasi-reduced if
(i) ${\left|a_{11}\right|<2 \Delta_{F}^{1 / 3}}$
(ii) ${\left|A_{33}\right|<2 \Delta_{F}^{2 / 3}}$
(iii) ${\left|a_{12}\right| \leq \frac{1}{2} a_{11}}$
(iv) ${\left|A_{13}\right| \leq \frac{1}{2}\left|A_{33}\right|}$
(v) ${\left|A_{23}\right| \leq \frac{1}{2}\left|A_{33}\right|}$

Use this conditions we can verify that ${X^2+Y^2+Z^2}$ is the unique positive definite quasi reduced form of discriminant ${1.}$

Now given any ${n}$ satisfying the local conditions, we consider the form ${F(X, Y, Z)=a_{11} X^{2}+a_{22} Y^{2}+n Z^{2}+2 a_{12} X Y+2 X Z}$ which represents ${n}$ because ${F(0,0,1)=n.}$

To make sure that it is positive definite we need ${a_{11}>0, D=a_{11} a_{22}-a_{12}^{2}>0.}$

Discriminant one condition is
$\displaystyle (a_{11} a_{22}-a_{12}^{2})n-a_{22}=1$

${Dn-1=a_{22}}$ , so these conditions are equivalent to finding ${D>0}$ such ${-D}$ being a square modulo ${Dn-1}$

Now the problem is about finding such a ${D}$ for any ${n}$ satisfying the local conditions and this can be done by quadratic reciprocity as follows:

$\displaystyle n \equiv 1(\bmod 8)$
Choose a prime ${p \equiv 6 n-1(\bmod ~~{8n})}$ so that ${p= Dn-1, D= 6 \mod 8.}$
Now
$\displaystyle \left(\frac{-D}{Dn-1}\right)=\left(\frac{-D}{p}\right)=\left(\frac{-2}{p}\right)\left(\frac{D / 2}{p}\right)=-\left(\frac{D / 2}{p}\right)=-\left(\frac{p}{D / 2}\right)=-\left(\frac{-1}{D / 2}\right)=1$

Similarly for ${n \equiv 3(\bmod 8) ,}$ choose ${p \equiv \frac{5 n-1}{2} \quad(\bmod 4 n).}$
If ${n \equiv 5(\bmod 8)}$ , choose ${p \equiv \frac{3 n-1}{2} \quad(\bmod 4 n)}$ If ${n \equiv 2}$ or ${6(\bmod 8)}$ , choose ${p \equiv 2 n-1 \quad(\bmod 4 n)}$

With these choices in all the cases we can see that ${\left(\frac{-D}{Dn-1}\right) = \left(\frac{-D}{p}\right)=1.}$

Thus we are done. To recap, we used congruence conditions, quadratic reciprocity to find primes ${p}$ of the form ${Dn-1}$ such that ${-D}$ is a square mod ${p=Dn-1.}$ Once we have such a ${D}$ , we can construct a positive definite form of discriminant ${1.}$ which represents ${n}$ (by construction, it has a special form). And now by reduction theory and the uniqueness of quasi reduced forms of discriminant ${1}$ , this form has to be equivalent to ${X^2+Y^2+Z^2.}$ Thus we found solutions to ${X^2+Y^2+Z^2=n.}$