Sum of Squares

In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$.

Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares.

Example:

$S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7.

Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$.

Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity

$$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$

This shows that $st \in S_2$

Example:

We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$

Note: an equivalent identity can also be obtained by replacing $b_1$ with $-b_1$ie:

$$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2+b_1b_2)^2+(a_1b_2-b_1a_2)^2$$

The lemma suggest that, in determining elements of $S_2$, we should first consider prime numbers; each integer $n \ge 2$ is a product of primes, and if these prime factors are all in $S_2$ then so is $n$.How ever not all prime numbers are sum of two squares.prime 3 is an example.

Two square Theorem

Two square theorem was stated by Fermat in 1640 and proved by Euler in 1754.

Theorem: Each prime $p\equiv 1 \pmod{4}$ is a sum of two squares.

Here are some examples of primes of the form $4n+1$ that can be represented as the sum of two squares:

$5=1^2+2^2$
$13=2^2+3^2$
$17=1^2+4^2$
$29=2^2+5^2$
$37=1^2+6^2$
$41=4^2+5^2$

Example:

The integer 221(17.13) can be represented as sum of squares.$13\equiv 17 \equiv 1 \pmod{4}$.

$13=3^2+2^2$

$17=4^2+1^2$

So using the theorem the product can also be represented as sum of squares

$221=(3.4-2.1)^2+(3.1+2.4)^2=10^2+11^2$

We can also get a different expression using the formula $(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2+b_1b_2)^2+(a_1b_2-b_1a_2)^2$

$221=(3.4+2.1)^2+(3.1-2.4)^2=14^2+5^2$

Example:

Express 6409 as some of two squares

$6409 \equiv 1 \pmod{4}$

$6409=221 .29$

$221=10^2+11^2$

$29=5^2+2^2$

So $6409=(10.5-11.2)^2+(10.2+11.5)^2=28^2+75^2$

Theorem: A positive integer $n$ is a sum of two squares if and only if every prime $q \equiv 3 \pmod{4}$ divides $n$ into an even power ( which may of course be zero if $q \nmid n$)

A positive integer $n$ is expressible as the sum of two squares if and only if the exponent of each of its prime factors congruent 3 modulo 4 in the canonical decomposition of $n$ is even.

Lemma:If a positive integer $n$ can be expressed as the sum of two squares, then so can $k^2n$ for every positive integer $k$.

Example:

The integer $60=2^2.3.5$ is not a sum of two squares , since the exponent of $3$ dividing it is odd.However $180=2^2.3^2.5$ is a sum of two squares.To find them first write $5$ as a sum of two squares.$5=2^2+1^2$.Now multiplying through by $2^2.3^2$, we get $180=(2.3.2)^2+(2.3.1)^2=12^2+6^2$

Example:

Represent 5733 as sum of two squares

$5733=3^2.7^2.13$

It is noted that both 3 and 7 having even power.So 5733 can be represented as sum of two squares.

Since $13=2^2+3^2$.So according to the leamma $k^2n$ can also be represented as some of two squares.

$(3.7)^2(2^2+3^2)=(3.7.2)^2+(3.7.3)^2=42^2+63^2$

Corollary:A prime $p$ is a sum of two squares if and only if  p=2 or $p \equiv 1 \pmod{4}$

The Gaussian Integers

A representation of an integer $n$ as a difference of two squares say $n=x^2-y^2$, give rise to the factorization of $n$ as a product of two integers.

$$n=x^2-y^2=(x+y)(x-y)$$

where $x+y \equiv x-y \pmod{2}$.Conversely, if $n=rs$, where $r \equiv s \pmod{2}$, then by writing  $x=(r+s)/2$ and $y=(r-s)/2$ , we get $n=x^2-y^2$ with $x,y \in \mathbb{Z}$.

This link with factorisation can be extended to sum of two squares , if we write

$$n=x^2+y^2=(x+yi)(x-yi)$$

where $i=\sqrt{-1}\in C$.Given any factorisation $n=rs$ of this form, we now write $x=(r+s)/2$ and $y=(r-s)/2i$, provided these are integers.

This suggest that we should study the complex numbers of the form $x+yi(x,y \in Z)$, known as the Gaussian Integers.and in particular their factorisations.

The set

$$\mathbb{Z}[i]=\{x+yi\| \; x,y \in \mathbb{Z}\}$$

is closed under addition,subtraction and multiplication.The usual axioms associativity, distributivity etc is satisfied and $\mathbb{Z}[i]$ is a ring, however it is not a field, since not every non zero element of $\mathbb{Z}[i]$ is a unit.

Addition

$(a+bi)+(c+di)=(a+c)+(b+d)i$

Subtraction

$(a+bi)-(c+di)=(a+c)-(b+d)i$

Multiplication

$(a+bi)(c+di)=(ac-bd)+(ad+bc)i$

Thus $\mathbb{Z}_i$ shares many of the basic properties of $\mathbb{Z}$. So it is not surprising that many of the results of integer division and factorization extends in a natural way to Gaussian Integers.

There are two other important properties of $\mathbb{Z}$ shared by $\mathbb{Z}_i$.The first property is that if $rs=0$ then $r=0$ or $s=0$.A ring with this property is called Integral Domain.

The second property of $\mathbb{Z}$ is the division algorithm, which allows one to divide an integer $a$ by a non zero integer $b$ with a remainder which is small compared with $b$.

An Integral Domain $R$ is Euclidean domain if  for each $a \in R \setminus \{0\}$, there is an integer $d(a) \ge 0$ such that 

(1) $d(ab) \ge d(b)$ for all $a,b \ne 0$, with equality if and only if $a$ is a unit.

(2) for all $a,b \in R$ with $b \ne 0$, there exist $q,r \in R$ such that $a=qb+r$,with $r=0$ or $d(r) < d(b)$

The function $d$ assigns a measure of size to each non zero element of $R$.

Example:

The ring $Z[i]$ of Gaussian Integers is an Euclidean domain with $d(z)=z.\bar{z}=|z|^2=x^2+y^2$, for each $z=x+yi \in \mathbb{Z}_i$.This is called Norm of $z$, written as $N(z)$.

$d(zw)=d(z).d(w)$ for all $z,w$ and the units in $\mathbb{Z}[i]$ are $\pm 1$ and $\pm i$.

For each integer $p=4k+3 \in \mathbb{Z}$, the gaussian prime is $p$ itself.

For each integer $p=4k+1 \in \mathbb{Z}$, the two gaussian primes are $a \pm bi$,where $a^2+b^2=p$

If the norm is prime not of the form $4n+3$ then the Gaussian numbers are Gaussian Primes.

Example:$5+2i$ is a gaussian prime

$5^2+2^2=29$ 29 is prime of form $4n+1$

$-1-i$ is gaussian prime

$1^2+1^2=2$ 2 is prime

Note :the number $13$ is prime having factors 1,13 in $\mathbb{Z}$

But we can factorize 13 in $\mathbb{Z}[i]$ as $(2+3i)(2-3i)$ ie $13=2^2+3^2$

if $p$ is a prime integer, then $p$ is an irreducible Gaussian integer if and only if $p$ is not the sum of two squares.

Prime Factorisation

Using the characterization of irreducible elements, we can describe a method for factoring an arbitrary Gaussian integer into irreducibles. (This is the “prime factorization” in $\mathbb{Z}[i]$.)

• First, find the prime factorization of $N(a + bi) = a^ 2 + b ^2$ over the integers $\mathbb{Z}$, and write down a list of all (rational) primes $p ∈ \mathbb{Z}$ dividing $N(a + bi)$. 
• Second, for each $p$ on the list, find the factorization of $p$ over the Gaussian integers $\mathbb{Z}[i]$.
• Finally, use trial division to determine which of these irreducible elements divide $a + bi$ in $\mathbb{Z}[i]$, and to which powers. (The factorization of $N(a + bi)$ can be used to determine the expected number of powers.)

Example:: Find the prime factorization of $4 + 22i$ in $\mathbb{Z}[i].$

• We compute $N(4 + 22i) = 4^2 + 22^2 = 2^2 · 5^3$ . The primes dividing $N(4 + 22i)$ are 2 and 5.
• Over $\mathbb{Z}[i]$, we find the factorizations $2 = −i(1 + i)^ 2$ and $5 = (2 + i)(2 − i)$. 
• Now we just do trial division to find the correct powers of each of these elements dividing $4 + 22i$. Since $N(4 + 22i) = 2^2 · 5^3$ , we should get two copies of $1 + i$ and three elements from $\{2 + i, 2 − i\}$. 
• Doing the trial division yields the factorization $4 + 22i = −i · (1 + i)^ 2 · (2 + i)^ 3$ . (Note that in order to have powers of the same irreducible element, we left the unit −i in front of the factorization.)

Example: Find the prime factorization of $27 − 19i$ in $Z[i]$. 

• We compute $N(27 − 19i) = 27^2 + 19^2 = 2 · 5 · 109$. 
• Over $Z[i]$, we find the factorizations $2 = −i(1 + i)^ 2 , 5 = (2 + i)(2 − i)$, and $109 = (10 + 3i)(10 − 3i)$. 
• Now we just do trial division to find the correct powers of each of these elements dividing $4 + 22i$. Since $N(27 - 19i) = 2 · 5 · 109$, we should get one copy of $1 + i$, one element from $\{2 + i, 2 − i\}$, and one element from $\{10 + 3i, 10 − 3i\}$. 
• Doing the trial division yields the factorization $27 − 19i = −i(1 + i)(2 + i)(10 − 3i)$.

Sum of Three Squares

Gauss provided that $n \in S_3$ if $n \ne 4^e(8k+7)$;ie;$7,15,23,28,\ldots$ are not sum of three squares.

;ie; $n$ cannot be represented as sum of three squares if it is in the form $4^e(8k+7)$

Example:

$3=1^2+1^2+1^2$

$6=2^2+1^2+1^2$

$14=3^2+2^2+1^2$

$26=4^2+3^2+1^2$

Note:$S_3$ is not closed under multiplication.For instance 3 and 6 are sums of three squares, but 18 is not.

Sum of Four Squares

This deals with how $n$ can be represented as sum of squares of four numbers

Example:$7=2^2+1^2+1^2+1^2$

Example:

$7=2^2+1^2+1^2+1^2$

$11=3^2+1^1+1^2+0^2$

$7.11.=77=(2.3+1.1+1.1+1.0)^2+(2.1-1.3+1.0-1.1)^2+\\(2.1-1.0-1.3+1.1)^2+(2.0+1.1-1.1-1.3)^2$

$=8^2+3^2+2^2+0^2$

lemma: every prime can be written as the sum of four squares.

Four square Theorem By Lagrange

Theorem: Every non negative integer is a sum of 4 squares.

Proof:Let $n$ be a positive integer. since $1=1^1+0^2+0^2+0^2$, the result is true when $n=1$.Now assume that $n \ge 2$. Let $n=\prod p_{i}^{ei}$ be the canonical decomposition of $n$.By the above lemma, each $p_i$ can be written as sum of four squares and hence $\prod p_i^{ei}=n$, can be written as the sum of four squares.

Example: write 15,795 as the sum of 4 squares

$15795=3^5.5.13$

$3=1^2+1^2+1^2+0^2$

$5=2^2+1^2+0^2+0^2$

$13=3^2+2^2+0^2+0^2$

Then $3^5=3^4(1^2+1^2+1^2+0^2)=9^2+9^2+9^2+0^2$

$5.13=(2^2+1^2+0^2+0^2)(3^2+2^2+0^2+0^2)$

$=8^2+1^2+0^2+0^2$

$15795=3^5.5.13=(9^2+9^2+9^2+0^2)(8^2+1^2+0^2+0^2)$

$=81^2+72^2+63^2+9^2$

Pythagorean Triplets

This is one of the most famous result of elementary geometry.It states that if a right angled triangle has side $a,b,c$ then

$$a^2+b^2=c^2$$

Fermat's Last Theorem(FLT)

There are no positive integer solutions $a,b,c$ of the equations

$$a^n+b^n=c^n$$

for integers $n \ge 3$