Two proofs of Fermat’s theorem on sums of two squares

May 22, 2011

Two proofs of Fermat’s theorem on sums of two squares

Filed under: mathematics — ckrao @ 7:55 am

Way back in 1640 Fermat stated that an odd prime number p can be written as the sum of two squares if and only if it has remainder 1 when divided by 4 (i.e p is of the form p = 4k+1 where k is an integer). It is believed that the first proof was given by Euler in 1747. Below are shown two of my favourite proofs in the “if” direction (the “only if” direction follows from any odd square being 1 modulo 4). Another cool proof worth looking at is by application of Minkowski’s Theorem for bounded symmetric convex sets [5].

In both proofs we use the fact that if p = 4k+1, then there exists an integer a such that $a^2 + 1 \equiv 0 \mod p$ . For example, we may choose $a = (2k)!$ , since

$\begin{array}{lcl} a^2 &\equiv& (1.2\ldots 2k)(1.2\ldots 2k)\ \mod p\\& \equiv & (1.2\ldots 2k)(-1).(-2)\ldots (-2k) (-1)^{2k}\ \mod p\\ &\equiv& (1.2\ldots 2k)(p-1).(p-2)\ldots (p-2k)\ \mod p\\ & \equiv & (p-1)! \ \mod p \\ &\equiv& -1 \mod p,\end{array}$

where the last step follows from Wilson’s theorem (in (p-1)! each element can be paired with its multiplicative inverse except for 1 and (p-1) – hence the product of the numbers from 1 to p-1 has remainder (p-1) modulo p).

Proof using Gaussian Integer Factorisation ([1]):

In the set of Gaussian integers ( $\left\{m + ni: m,n \in \mathbb{Z}, i^2 = -1\right\}$ ), one can divide a number x by another y to obtain a quotient q and remainder r where |r| < |y|. This fact leads to unique factorisation being possible among the Gaussian integers (Euclidean domain implies unique factorisation via the principal ideal domain property.) Using the a found above, since $a^2 + 1$ is divisible by p and neither of its factors (a+i) nor (a-i) are multiples of p, p cannot be prime in the set of Gaussian integers. Hence we may write p = cd, where c and d are Gaussian integers each with norm greater than 1. This gives

$p^2 = |c|^2 |d|^2$ ,

which forces $|c|^2 = |d|^2 = p$ . Therefore if c = x+ iy we have

$x^2 + y^2 = |c|^2 = p$ ,

showing that p can be written as the sum of two squares.

Proof by Pigeonhole Principle ([2]):

Using the a found above, consider the set of integers $ax-y$ , where integers x and y satisfy $0 \leq x,y < \sqrt{p}$ . The number of possible pairs (x,y) is $\left( \left \lfloor \sqrt{p} \right \rfloor + 1\right)^2 > \left( \sqrt{p} \right)^2$ , and so applying the pigeonhole principle, there exist two distinct pairs $(x_1,y_1)$ and $(x_2,y_2)$ such that

$\displaystyle ax_1-y_1 \equiv ax_2 - y_2\ \mod p.$

Hence $\displaystyle a(x_1 - x_2) \equiv y_1 - y_2\ \mod p$ and $(y_1-y_2)^2 = a^2(x_1 - x_2)^2 \equiv (-1)(x_1 - x_2)^2 \ \mod p$ . This means

$\displaystyle (x_1 - x_2)^2 + (y_1 - y_2)^2 \equiv 0 \ \mod p$ .

Since the pairs $(x_1,y_1)$ and $(x_2,y_2)$ are distinct and $0 \leq x_i,y_i < \sqrt{p}$ ,

$\displaystyle 0 < (x_1 - x_2)^2 + (y_1 - y_2)^2 < \left(\sqrt{p}\right)^2 + \left(\sqrt{p}\right)^2 = 2p$ .

This forces $(x_1 - x_2)^2 + (y_1 - y_2)^2 = p$ and we are done.

Some more facts:

A positive integer can be written as the sum of two squares if and only if any prime factor of the form 4k+3 occurs as an even power in its factorisation. To proves this requires the beautiful fact that if two numbers are each the sum of two squares, so too is their product:
$\begin{array}{lcl}(a^2 + b^2)(c^2 + d^2) &=& (a+bi)(a-bi)(c+di)(c-di)\\ &=& (a+bi)(c+di)(a-bi)(c-di)\\ &=& (ac-bd)^2 + (ad + bc)^2. \end{array}$ .
The number of ways in which the positive integer $n = 2^{a_0}p_1^{2a_1}\ldots p^{2a_r} q^{b_1}\ldots q^{b_s}$ can be written as the sum of two squares (here $p_i$ have the form 4k+3, $q_i$ have the form 4k+1) is
$r(n) = 4(b_1 +1)(b_2+1)\ldots(b_s+1)$ ,

where signs and order are distinguished (e.g. r(5) = 8). [3]
We have the limit
$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N}\sum_{n=1}^N r(n) = \pi$ .

This can be proved by counting the number of lattice points inside a circle of radius $\sqrt{N}$ , then in the limit this number becomes the area of the circle. [4]
Finally, if signs and order are not to be distinguished (e.g. 5 can be written as the sum of two squares in the one way $2^2 + 1^2$ ), the number of ways $n = 2^{a_0}p_1^{2a_1}\ldots p^{2a_r} q^{b_1}\ldots q^{b_s}$ can be written as the sum of two squares is ([3])
$\displaystyle \frac{1}{2} \left( (b_1 +1)(b_2+1)\ldots(b_s+1) - (-1)^{a_0} \right)$ , if all of the $b_i$ values are even,
$\displaystyle \frac{1}{2} (b_1 +1)(b_2+1)\ldots(b_s+1)$ otherwise.

(The first case deals with the possibility of whether n is of the form $n = 2x^2$ , in which case it has the additional representation $x^2 + x^2$ .)