Fermat's Two-Square Theorem

In a letter from Fermat to Mersenne on Christmas Day 1640, e annunciò la dimostrazione di un risultato che, da allora, viene appunto chiamato teorema di Natale. Ma prima di enunciarlo dobbiamo fare un passo indietro, e meditare sui possibili «modi di essere» dei numeri primi. A parte il 2, di cui non ci interesseremo, si inizia notando che alcuni primi hanno l’interessante proprietà di essere uguali alla somma di due quadrati: per esempio, 5 è 1 più 4, 13 è 4 più 9, 17 è 1 più 16, eccetera. E altri invece no: per esempio, il 3, il 7 e l’11. Nella ricerca di una regolarità, si continua osservando che i primi di un tipo si alternano, fra i numeri dispari, ai primi dell’altro tipo: detto altrimenti, i primi uguali alla somma di due quadrati sono tutti della forma 4n + 1, e gli altri della forma 4n + 3. Nel 1632 Albert Girard congetturò che la cosa valesse in generale: cioè, che i numeri primi dispari uguali alla somma di due quadrati fossero esattamente quelli del tipo 4n + 1. Una direzione era ovvia, perché ogni quadrato è del tipo 4n (se pari) o 4n + 1 (se dispari): dunque, ogni somma di quadrati è del tipo 4n, 4n + 1 or 4n + 2, e se è dispari l’unica possibilità è che sia del tipo 4n + 1. Nella sua lettera natalizia Fermat affermò di aver dimostrato anche l’altra direzione: cioè, che ogni numero primo del tipo 4n + 1 è uguale alla somma di due quadrati. Ma la sua dimostrazione non si trovò da nessuna parte, e il primo ad averne scritta una fu Eulero nel 1749, in una lettera a Goldbach. In seguito se ne sono trovate molte altre, ma nessuna così elementare da stare in questa pagina. La proprietà che divide i due tipi di numeri primi si ispira ovviamente al teorema di Pitagora, perché la radice √p di un numero p uguale alla somma di due quadrati m² e n² è ovviamente la lunghezza dell’ipotenusa di un triangolo rettangolo, che ha cateti di lunghezza m e n. In questo caso lo stesso numero p è la lunghezza dell’ipotenusa di un triangolo rettangolo, che ha cateti di lunghezza m² – n² e 2mn. Per esempio, nel caso di 5, il primo triangolo ha cateti 1 e 2 e ipotenusa √5, e il secondo cateti 3 e 4 e ipotenusa 5. Per questo motivo Diofanto chiamava «pitagorici» i primi uguali alla somma di due quadrati, che il teorema di Natale caratterizza come i primi della forma 4n + 1. Nelle Disquisitiones Arithmeticae del 1801 Gauss andò oltre, dimostrando che i primi pitagorici sono l’ipotenusa di un solo triangolo rettangolo a lati interi: per esempio, 3 e 4 nel caso di 5. Ma i loro quadrati lo sono in due modi: per esempio, 7 e 24, o 15 e 20, nel caso di 25. I loro cubi, in tre modi, e così via. La dicotomia fra primi pitagorici e non pitagorici si è in seguito rivelata fondamentale in teoria dei numeri, attraverso la connessione con i numeri interi complessi, della forma m ± n. Le somme di quadrati sono infatti le norme di tali numeri, e un primo della forma m² + n² si può in realtà scomporre nel prodotto dei due interi complessi m + in e m – in. Cioè, i primi pitagorici sembrano primi se li si guarda dal ristretto punto di vista dei numeri interi reali, ma si rivelano non esserlo quando li si osserva dal più ampio punto di vista dei numeri interi complessi. Che i primi pitagorici siano in realtà «falsi primi» lo dimostra anche il fatto che è complicato dimostrare che ce ne sono infiniti: non si può adattare la famosa dimostrazione di Euclide dell’esistenza di infiniti numeri primi, che invece si adatta senza difficoltà ai primi non pitagorici. Supponiamo infatti che ci sia solo un numero finito di primi del tipo 4n + 3, e consideriamo il numero N pari a 4 volte il loro prodotto, meno 1. Questo numero è del tipo 4n + 3, ma ogni suo fattore primo è del tipo 4n + 1: infatti, i primi del tipo 4n + 3 dividono tutti N + 1, e dunque nessuno divide N. La contraddizione si ottiene notando che il prodotto di numeri del tipo 4n + 1 è ancora dello stesso tipo. Il che equivale, per il teorema di Natale, al fatto che il prodotto di somme di quadrati sia ancora una somma di quadrati: una proprietà scoperta da Diofanto, ma ovvia quando si ricordi il legame fra le somme di quadrati e le norme dei numeri complessi.

The next section is devoted to proving the claim that whenever p is a prime with p ≡ 1 mod 4, it follows that p = a² + b² for some integers a and b. Before we dive into the technical details of the proof, let us briefly discuss why it is interesting to consider a² + b² in modular arithmetic, in particular modulo 4.

An integer n is a perfect square if and only if it can be expressed as the square of some other integer i.e. there exists some integer a such that n = a². Before we consider a² + b², just consider squares a². Can we know whether some numbern is a perfect square by knowing its remainder mod k?

4.13.1 Proposition If n is a perfect square, then either n ≡ 1 (mod 4), or n ≡ 0 mod 4.

Proof. Suppose a is even so a = 2k, for some integer k, and n = a² = 4k² ≡ 0 (mod 4). Otherwise, a is odd, and a = 2k+1. Then n = a² = (2k + 1)²= 4k² + 4k + 1 = 4(k² + k) + 1 ≡ 1 (mod 4).□

So the sum of two squares can be either

4.13.2 Fermat's Two-Square Theorem. An odd prime number, p can be expressed as sum of two squares if and only if p = 4k +1.

Proof. First of all, notice that every integer a is congruent either to 0, 1, 2 or 3 mod 4, and a² ≡ 0,1 mod 4 since 0², 1², 2², 3² are equal to 0,1,0,1 mod 4. Hence it follows

as shown in the previous proposition.

No prime number can be 0 modulo 4 because it would be divisible by 4. Also, every n ≡ 2 (mod 4) is an even number so the only prime p ≡ 2 mod 4 is p = 2. Thus, every odd prime p is congruent to 1 or 3 mod 4, that is

So if p ≡ 3 (mod 4) the equation p = a² + b² is impossible. We thus proved that if p is an odd prime then it is a sum of two squares then necessarily p ≡ 1 mod 4.

We now prove the converse, if p is an odd prime such that p ≡ 1 (mod 4), then it is the sum of two squares: p = a² + b² for some a,b ∈ ℤ.

We want to show that p divides 1 + x²; This impolies that

has solutions. We'll show that x = [(p − 1)/2]! is a solution.

Let p be a prime number of the form 4k + 1. Since (p − 1)/2 = 2k is an even number, also the factors are of

are even, hence x can be written as

from which

Since p − h ≡ −h (mod p)   4.13.1

through the congruence with add p to each of the negative numbers.

Where the last congruence was obtained by Wilson's theorem.

We proved that there exists a solution to x² ≡ −1 (mod p), which means that p divides 1 + x², where x = [(p − 1)/2]!. If we think to 1 + x² as an element of ℤ[i], we have 1 + x² = (1 + ix)(1 −ix), then

hence p divides (1 +ix) (1 −ix), but it does not divide neither of the two factors. Indeed if p | 1 + i [(p-1)/2]!,

for some a,b ∈ ℤ, we would have pa = 1 which is impossible. Thus p is not prime in ℤ[i], hence not ierreducible. It follows that for some αβγ,δ ∈ ℤ we must have

which by taking the norms

which is a factorization in ℕ, from which follows that p = (α² + β²).□

4.13.3 Proposition. The product of the sums of two squares is still a sum of two squares.

Proof. We have

For example

85 = 5 ⋅ 17 = (2² + 1²)(4² + 1²) = (2 ⋅ 4 - 1 ⋅ 1)² + (2 ⋅ 1 + 1 ⋅ 4)² = 7² + 6².

4.13.4 Theorem. A positive integer n can be written as a sum of two squares if and only if each prime of the form 4n + 3 appearing in the canonical factorization of n is raised to an even power.

Proof. Let

the factorization of n in irreducible factors. To prove that n is the sum of two squares, owing to proposition 4.13.3, it sufficies to prove that the three factors: 2^k, one factor among (4k + 3) and one among (4k + 1), are sum of two squares. Concerning 2^k we know that 2 can be expressed as a power of two squares, and so its powers. Every prime of the form 4k + 1 can be expressed as sum of two squares by Fermat's theorem and also they products are. By Fermat's theorem we know that prime of the form 4k + 3 cannot be expressed as the sum of two squares, but since their exponent is even and the square of a number is clearly a trivial sum of two squares, also this factor is expressible by sum of two squares, proving the theorem.□

The converse of this theorem holds true as well.

4.13.5 Examples. 168 = 2³ ⋅ 3 ⋅ 7² is not expressible as sum of two squares since there a factor of the form 4k + 3 namely 3, which has not even exponent.

187 = 11 ⋅ 17 also is not a sum of two squares.

392 = 2³ ⋅ 7² can be written as 7² ⋅ 2² ⋅ 2 = (7² + 0²) ⋅ (2² + 2²) = 14² + 14².

377 = 13 ⋅ 29 = (3² + 2²)(5² + 2²) = N(3 + 2i) N(5 + 2i) = N[(3 + 2i)⋅(5 + 2i)] = N(11 + 16i) = 11² + 16².

The norm of the conjugates is the same, so we can find another expression: N[(3 - 2i)⋅(5 + 2i) = N(19 - 4i) = 19² + 4² = 377.

The previuos proposition and theorems are useful for example to determine whether a positive integer n, is suitable to represent the norm of a Gaussian integer.