Fermat's Theorem on Sums of Two Squares

The question of which integers can be written as the sum of two squares is a classic problem in number theory that exemplifies mathematical beauty. It starts as a simple arithmetic puzzle but quickly reveals deep connections between prime numbers, modular arithmetic, and the complex plane. While elementary observations can rule out certain numbers, such as those leaving a remainder of 3 when divided by 4, this test is incomplete and fails to capture the full picture. The complete answer requires a profound shift in perspective, one that moves from the familiar world of integers into the richer structure of Gaussian integers.

This article will guide you through this fascinating journey. In the first chapter, "Principles and Mechanisms," we will uncover the complete rule for determining if a number is a sum of two squares, building the theory from the ground up using Gaussian integers and their unique factorization properties. Following this, the chapter on "Applications and Interdisciplinary Connections" will explore the surprising and far-reaching impact of this theorem, showing how it provides tools for modern computation, aids in solving other number theory problems, and even describes physical phenomena in quantum mechanics and secures data in cryptography.

Some of the most beautiful ideas in mathematics are those that connect seemingly disparate fields, revealing a hidden unity. The question of which numbers can be written as the sum of two integer squares is a perfect example. What begins as a simple arithmetic curiosity—can I write 5 as $a^2+b^2$? Yes, $1^2+2^2$. What about 7? No, try as you might—unfurls into a stunning narrative involving prime numbers, modular arithmetic, and a journey into the world of complex numbers.

Let’s begin our investigation like any good scientist: by playing with the numbers and looking for a pattern. We want to know which integers $n$ can be expressed as $n = a^2 + b^2$.

What are the building blocks here? Squares. Let's see how they behave. Any integer is either even or odd.

• If a number $x$ is even, say $x=2k$, its square is $x^2 = (2k)^2 = 4k^2$. This is a multiple of 4.
• If a number $x$ is odd, say $x=2k+1$, its square is $x^2 = (2k+1)^2 = 4k^2+4k+1 = 4(k^2+k)+1$. This leaves a remainder of 1 when divided by 4.

In the language of modular arithmetic, this means any perfect square is congruent to either $0$ or $1$ modulo $4$. $x^2 \equiv 0 \pmod{4} \quad \text{or} \quad x^2 \equiv 1 \pmod{4}$

Now, what about a sum of two squares, $a^2+b^2$? We can check the possible remainders when divided by 4:

• If both $a$ and $b$ are even, $a^2+b^2 \equiv 0+0 \equiv 0 \pmod{4}$.
• If one is even and one is odd, $a^2+b^2 \equiv 0+1 \equiv 1 \pmod{4}$.
• If both are odd, $a^2+b^2 \equiv 1+1 \equiv 2 \pmod{4}$.

Look at what's missing! There is no combination of squares that adds up to 3 modulo 4. This gives us a powerful, simple rule: ​​An integer that leaves a remainder of 3 when divided by 4 can never be written as the sum of two squares​​.

This is a wonderful first step. We can immediately rule out an infinite collection of numbers: 3, 7, 11, 15, 19, 23, and so on. For instance, if you were asked whether 199 can be written as a sum of two squares, you wouldn't need to check every possibility. You'd simply note that $199 = 4 \times 49 + 3$, so its remainder is 3, and the answer is definitively no.

But is this the whole story? If a number is not congruent to 3 modulo 4, is it always a sum of two squares? Let's test this. The number 6 leaves a remainder of 2. Is it a sum of two squares? $1^2+1^2=2$, $1^2+2^2=5$, $2^2+2^2=8$. No. The number 21 leaves a remainder of 1. Is it a sum of two squares? No. Our simple test is a necessary condition, but it is not sufficient. There is a deeper structure at play.

To find the complete answer, we must take a leap of imagination, one that puzzled mathematicians for centuries until the great Carl Friedrich Gauss provided the key. The expression $a^2+b^2$ should look familiar to anyone who has encountered complex numbers. It is the square of the magnitude, or the ​​norm​​, of the complex number $z=a+bi$.

Let's define a new set of numbers, which we call the ​​Gaussian integers​​, denoted by $\mathbb{Z}[i]$. These are simply complex numbers where the real and imaginary parts are integers: $\{a+bi \mid a,b \in \mathbb{Z}\}$. This set behaves beautifully; you can add, subtract, and multiply Gaussian integers and the result is always another Gaussian integer. It forms what mathematicians call a ​​ring​​.

For any Gaussian integer $\alpha = a+bi$, its norm is $N(\alpha) = a^2+b^2$. Our original question, "Which integers $n$ are a sum of two squares?" can now be reframed in this new world: ​​"Which integers $n$ are the norm of a Gaussian integer?"​​

This might seem like a mere change of language, but it is a profound shift in perspective. It allows us to use the powerful tools of factorization and prime numbers in this new domain.

One of the most elegant properties of the norm is that it is ​​multiplicative​​: for any two Gaussian integers $\alpha$ and $\beta$, the norm of their product is the product of their norms. $N(\alpha\beta) = N(\alpha)N(\beta)$

Let's see what this means. Suppose we have two numbers, $m$ and $n$, that are each a sum of two squares. In our new language, this means $m=N(\alpha)$ and $n=N(\beta)$ for some Gaussian integers $\alpha=a+bi$ and $\beta=c+di$. The product $mn$ is then: $mn = N(\alpha)N(\beta) = N(\alpha\beta)$ Since $\alpha\beta$ is just another Gaussian integer, its norm is also a sum of two squares! Let's calculate the product $\alpha\beta$: $\alpha\beta = (a+bi)(c+di) = (ac-bd) + i(ad+bc)$ The norm of this product is: $N(\alpha\beta) = (ac-bd)^2 + (ad+bc)^2$ So we have found that $mn = (ac-bd)^2 + (ad+bc)^2$. This amazing formula, known as the ​​Brahmagupta-Fibonacci identity​​, shows that the set of numbers that can be written as a sum of two squares is closed under multiplication. For example, since $5=1^2+2^2$ and $13=2^2+3^2$ are sums of two squares, their product $65$ must also be. Using the formula with $a=1, b=2, c=2, d=3$, we get $65 = (1\cdot2-2\cdot3)^2 + (1\cdot3+2\cdot2)^2 = (-4)^2+7^2 = 16+49=65$.

This property is immensely powerful. It tells us that to understand which composite numbers are sums of two squares, we first need to understand the building blocks: the prime numbers.

Just as we can factor an integer like 12 into its prime factors $2^2 \times 3$, we can factor Gaussian integers into ​​Gaussian primes​​. A Gaussian prime is a Gaussian integer that cannot be factored into the product of two non-unit Gaussian integers. (The units are just $\{\pm 1, \pm i\}$, the numbers whose norm is 1.

The key to our entire puzzle lies in what happens to an ordinary prime number from $\mathbb{Z}$ when we view it in the world of $\mathbb{Z}[i]$. It turns out a rational prime faces one of three fates:

1. ​​Ramification (The Case of 2):​​ The prime 2 is special. In $\mathbb{Z}[i]$, it factors as $2 = (1+i)(1-i)$. Since $1-i = -i(1+i)$, the factors are essentially the same (they are associates). The number 2 "ramifies" into a squared prime factor, up to a unit. This factorization immediately gives us its representation as a sum of two squares: $N(1+i) = 1^2+1^2=2$.

2. ​​Splitting (Primes of the form $4k+1$):​​ A prime $p$ of the form $4k+1$ (like 5, 13, 17, 29) always ceases to be prime in the Gaussian integers. It ​​splits​​ into a product of two distinct, conjugate Gaussian primes: $p = \pi \cdot \overline{\pi}$. For example:

   • $5 = (2+i)(2-i)$
   • $13 = (3+2i)(3-2i)$ If we take the norm of this equation, we get $N(p) = p^2 = N(\pi) N(\overline{\pi})$. Since the norm of a Gaussian prime $\pi = a+bi$ must be greater than 1, and $N(\pi) = N(\overline{\pi}) = a^2+b^2$, this forces $N(\pi)=p$. And there it is! The very act of splitting in $\mathbb{Z}[i]$ means the prime is a norm of a Gaussian integer, and therefore $p = a^2+b^2$. This happens if and only if $p \equiv 1 \pmod 4$.

3. ​​Inertness (Primes of the form $4k+3$):​​ A prime $p$ of the form $4k+3$ (like 3, 7, 11, 19) remains ​​inert​​. It does not factor in $\mathbb{Z}[i]$; it stays prime in this new world. If such a prime were a sum of two squares, say $p=a^2+b^2$, it would have to factor as $p=(a+bi)(a-bi)$, contradicting its inertness. This provides the deep, structural reason for the pattern we first observed with our modulo 4 test.

We can now assemble all the pieces to state the full, beautiful theorem on sums of two squares.

A positive integer $n$ can be written as the sum of two squares if and only if in its prime factorization, ​​every prime factor of the form $4k+3$ appears with an even exponent.​​

Let's see why this must be true. Suppose an integer $n$ can be written as a sum of two squares, $n = a^2+b^2$. In the ring of Gaussian integers, this is $n = (a+bi)(a-bi)$. Let $q$ be a prime factor of $n$ of the form $4k+3$. As we've seen, such primes are inert—they remain prime in $\mathbb{Z}[i]$. Since $q$ divides the product $(a+bi)(a-bi)$ and is a Gaussian prime, it must divide one of the factors. Let's say $q$ divides $a+bi$. This means $a+bi = q(c+di)$ for some Gaussian integer $c+di$. Thus, $a=qc$ and $b=qd$. This shows that $q$ must divide both $a$ and $b$. Consequently, $q^2$ must divide both $a^2$ and $b^2$, and therefore $q^2$ must divide their sum, $n = a^2+b^2$. We can then write $n/q^2 = (a/q)^2+(b/q)^2$, which is a smaller number that is also a sum of two squares. We can repeat this argument, dividing out factors of $q^2$ until no factors of $q$ remain. This means that if we start with the prime factorization of $n$, any prime factor $q$ of the form $4k+3$ must be paired up, so its total exponent must be even.

The exponents of 2 and primes of the form $4k+1$ can be anything. They are already sums of two squares, and thanks to the Brahmagupta-Fibonacci identity, their products are too.

Let's test this with our earlier counterexample, $n=6=2 \times 3$. The prime factor 3 is of the form $4k+3$, and its exponent is 1 (odd). So 6 cannot be a sum of two squares. What about $n=18=2 \times 3^2$? Here, the prime 3 appears with an exponent of 2 (even). The theorem predicts it is a sum of two squares, and indeed it is: $18 = 3^2+3^2$.

This theorem is not just a rule; it is a window into the deep structure of numbers. The simple question of adding two squares leads us to a hidden world of Gaussian integers, where the behavior of prime numbers reveals the answer in a way that is both surprising and profoundly logical. This journey from a simple pattern to a deep structural explanation is the very essence of mathematical beauty. And remarkably, the properties of these representations are not random. For a prime $p \equiv 1 \pmod 4$, its representation as a sum of two squares is essentially unique. The number of ways to write any integer $n$ as a sum of two squares can be counted precisely by a formula involving its divisors—a testament to the incredible order hidden within the integers.

Having journeyed through the elegant machinery of Gaussian integers and the "if and only if" precision of Fermat's theorem, one might be tempted to view the sum of two squares problem as a beautiful, but self-contained, island in the vast ocean of mathematics. Nothing could be further from the truth. This seemingly simple question is not an end point, but a crossroads, a place where paths from seemingly disparate fields of science and mathematics converge in the most unexpected and delightful ways. To appreciate the true power of an idea, we must see what it does. Let us, then, explore the far-reaching consequences and surprising applications of this theorem, and see how it helps us count, compute, encrypt, and even understand the fundamental vibrations of the universe.

The theorem tells us which numbers can be written as a sum of two squares, but it doesn't immediately hand us the squares themselves. How do we find $a$ and $b$ for a giant prime like $p=65537$? This practical question moves us from the realm of pure existence to the world of algorithms and computation.

The theory itself provides the blueprint. The Brahmagupta–Fibonacci identity, which arises naturally from the multiplicative nature of the norm in Gaussian integers, gives us a recipe for construction. If we know the representations for two numbers, say $n_1 = a^2+b^2$ and $n_2 = c^2+d^2$, we can find a representation for their product $n_1 n_2$ simply by multiplying the corresponding Gaussian integers $a+bi$ and $c+di$ and taking the norm of the result. This allows us to build representations for composite numbers from those of their prime factors.

For the prime factors themselves, the connection to Gaussian integers is our guide. The fact that a prime $p \equiv 1 \pmod 4$ is reducible in $\mathbb{Z}[i]$ is the key. Finding the factors of $p$ in this larger ring is equivalent to finding the two squares. This can be done constructively by finding a solution to $x^2 \equiv -1 \pmod p$ and then using the Euclidean algorithm in $\mathbb{Z}[i]$ to compute the greatest common divisor of $p$ and $x+i$. This GCD will be a Gaussian integer whose real and imaginary parts are, up to sign, the numbers we seek. Amazingly, this process can be translated into an efficient, purely integer-based procedure known as Cornacchia's algorithm, which uses the familiar Euclidean algorithm on regular integers to extract the desired squares, bridging the gap between abstract algebra and practical computation.

The sum of two squares theorem is not an isolated result; it serves as a crucial tool for tackling other problems in number theory. Consider the question of representing a number as a sum of three squares. Legendre's three-square theorem gives a complete answer: a number $n$ can be written as $x^2+y^2+z^2$ if and only if it is not of the form $4^k(8m+7)$.

How might one go about finding such a representation? A natural approach is to try to reduce the problem to one we already know how to solve. We can rewrite the equation as $n - z^2 = x^2+y^2$. For a given $n$, our task then becomes a search: can we find an integer $z$ such that the remaining part, $n-z^2$, is a number that can be written as a sum of two squares? We have a complete and effective test for this from Fermat's theorem. For some numbers, like $n=2023$, this search will always fail. A clever argument using arithmetic modulo 8 shows that for any choice of $z$, the number $2023-z^2$ can never be a sum of two squares. For other numbers, like $n=2026$, the search is guaranteed to succeed, and we find representations like $2026 = 1^2 + 45^2 + 0^2$. The two-square theorem becomes an essential subroutine in the larger algorithm for three squares.

Perhaps the most breathtaking connection lies in the field of spectral geometry, which asks a famous question posed by Mark Kac: "Can one hear the shape of a drum?" This field studies the relationship between the geometric shape of an object and the frequencies at which it can vibrate. These characteristic frequencies are the eigenvalues of a fundamental physical operator, the Laplacian.

Let's imagine a very peculiar drum: a two-dimensional flat torus, which you can think of as a square video game screen where moving off the right edge makes you reappear on the left, and moving off the top makes you reappear on the bottom. In physics, this could represent the universe for a particle living in a small, periodic box. What are the possible quantum energy levels of this particle, or equivalently, the "pure tones" this torus can produce?

The answer is astonishing. The eigenvalues (which determine the energy levels) are all of the form $\lambda_n = 4\pi^2 n$, where $n$ is a non-negative integer. But not every $n$ produces an eigenvalue. A value $n$ corresponds to an allowed energy level if and only if it can be written as a sum of two integer squares, $n=k_1^2 + k_2^2$. Furthermore, the multiplicity, or degeneracy, of that energy level—the number of distinct quantum states that share the same energy—is precisely $r_2(n)$, the number of ways to write $n$ as a sum of two squares (counting order and signs).

So, for a prime $p \equiv 1 \pmod 4$, the energy level corresponding to $n=p$ has a multiplicity of 8, because we found there are exactly eight representations (e.g., for $p=5=1^2+2^2$, the pairs are $(\pm 1, \pm 2)$ and $(\pm 2, \pm 1)$). In contrast, for a prime $q \equiv 3 \pmod 4$, the energy level corresponding to $n=q$ is forbidden; its multiplicity is zero. Our abstract number theory question about integer representations has become a physical statement about the allowed energies in a quantum system. The structure of the integers dictates the music of the cosmos.

The story takes yet another turn, leading us to the forefront of modern information security. Elliptic curve cryptography is a cornerstone of the systems that protect our financial transactions and digital communications. The security of these systems relies on the mathematical difficulty of certain problems on elliptic curves defined over finite fields.

A fundamental property of an elliptic curve over a finite field $\mathbb{F}_p$ is the number of points on it. This count is governed by an integer called the trace of Frobenius, $a_p$. For a special class of curves with "complex multiplication," this trace is deeply connected to number theory. Consider the curve $E_{-1}: y^2 \equiv x^3 - x \pmod p$. It turns out that its trace of Frobenius, $a_p$, is intimately related to the sum of two squares representation of the prime $p$.

If $p \equiv 3 \pmod 4$, the trace is simply $a_p=0$. But if $p \equiv 1 \pmod 4$, we must first write $p = a^2+b^2$. Under specific constraints to make the choice of $a$ and $b$ unique (e.g., $a$ is odd, $b$ is even, and $a+b \equiv 1 \pmod 4$), the trace is given by the beautifully simple formula $a_p = -2a$. For the prime $p=65537$, a famous Fermat prime, we have the representation $65537 = 1^2+256^2$. The unique choice of $a$ that fits the criteria is $a=1$, leading to a trace of $a_p = -2$. This means the number of points on the curve is $p+1-a_p = 65537+1-(-2) = 65540$. The ability to find the components of the sum-of-squares representation is not just a mathematical exercise; it is a crucial part of understanding the properties of objects central to modern cryptography.

The function $r_2(n)$ that counts our representations is erratic. It is $0$ for $n=3$, $8$ for $n=5$, $0$ for $n=6$, $0$ for $n=7$, $4$ for $n=8$. The values jump around with no obvious pattern. In the face of such chaos, a mathematician might ask a different kind of question: what is its behavior on average? If we pick a very large number $N$ and sum up all the $r_2(k)$ values from $k=1$ to $N$, what will the average $\frac{1}{N}\sum_{k=1}^N r_2(k)$ look like?

The answer is found using the powerful tools of analytic number theory, specifically the Epstein zeta function, which packages all the information about $r_2(k)$ into a single function $Z_2(s) = \sum_{k=1}^\infty \frac{r_2(k)}{k^s}$. A deep result known as a Tauberian theorem connects the average value of the coefficients to the behavior of this function near its singularity. The analysis reveals a result of profound beauty:

The average number of ways to write an integer as a sum of two squares is $\pi$! An inquiry that began with discrete integers and whole number squares leads us, in the end, to the most famous transcendental number from geometry, the ratio of a circle's circumference to its diameter. It is hard to imagine a more stunning testament to the hidden unity of mathematics.

From concrete algorithms to the abstract harmonies of physics and the security of our digital world, the sum of two squares theorem is a shining example of how a simple, elegant idea can ripple outwards, connecting diverse landscapes of thought in a unified and beautiful tapestry.