The Primes That Split in Two

A yes-or-no question with a one-digit answer

Here is a question a child could ask and a professional could chew on. Take a prime number, any prime, and try to write it as two square numbers added together. Thirteen works: 13 = 2² + 3², that is 4 + 9. Five works: 5 = 1² + 2². Now try seven. You will not find it, because there is nothing to find: 7 is not a sum of two squares, and neither is 3, nor 11, nor 19, nor 23. Some primes split cleanly in two; some refuse, forever.

The astonishing part is that you can tell which is which without trying at all. Pierre de Fermat stated the rule in a letter of 1640, so exactly, and with so little visible working, that it took Leonhard Euler the better part of seven years to prove it (finished around 1749). It is sometimes called Fermat's Christmas theorem, after the 25 December 1640 letter in which he laid it out. The rule is this:

An odd prime p is a sum of two squares if and only if p leaves a remainder of 1 when you divide it by 4.

That is the whole thing. Divide the prime by four. If the remainder is 1, it splits. If the remainder is 3, it never will. (Two is the odd one out, an even prime, and it splits too: 2 = 1² + 1².) Every figure below is computed live by a sieve running in your browser, no stored tables, nothing that can go stale.

The sieve, coloured by remainder

The first console lays the odd primes out and paints each one by its remainder mod 4. Blue for the 4k+1 primes, the ones that split; ember for the 4k+3 primes, the ones that cannot. Turn on show the split and every blue tile carries its unique decomposition: 5 = 1²+2², 13 = 2²+3², 17 = 1²+4², 29 = 2²+5², and on.

Two things are worth noticing as you slide the range out. First, the rule has no exceptions, none, ever. It is not "usually" true or "true for small primes." It was checked here against every odd prime below two hundred thousand before this article was written, and the two teams came out to 8,977 splittable primes and 9,006 stubborn ones, with not a single prime on the wrong side of its remainder. Second, the two teams stay close to equal in size, because the primes divide themselves almost evenly between the two remainders, the same near-tie that drove the prime race. But evenly split or not, which team a prime lands on is fixed the moment you know its last-digit-mod-4.

A circle hunting for a lattice point

Why should dividing by four decide anything about squares? The cleanest way to feel it is to make the question geometric, which the second console does. Writing n = a² + b² is the same as finding a point (a, b) with whole-number coordinates sitting exactly on a circle of radius √n centred at the origin, because a² + b² is that point's squared distance out. So the question "is n a sum of two squares?" becomes "does the circle of radius √n pass through a point of the integer grid?"

Pick 13 and the circle threads a single grid point in the first slice, (2, 3), and its mirror images. Pick 7 and the circle of radius √7 slips between every lattice point and lands on none. Pick a prime ≡ 1 (mod 4) and there is always exactly one such point (up to swapping and reflecting), which is why the split of a prime is unique. Pick a composite like 65 and the circle can pass through several grid points at once: 65 = 1² + 8² and 65 = 4² + 7², two genuinely different splits, because 65 = 5 × 13 is built from two splittable primes.

The console also names the reason a number fails. Feed it 21 and it factors to 3 × 7: both 3 and 7 are ≡ 3 (mod 4), each to an odd power, and either one alone is enough to knock the circle off every lattice point. Feed it 45 = 3² × 5, though, and it splits (45 = 3² + 6²), because here the 3 appears squared, an even power, and an even power of a bad prime is forgiven. That exception is the hinge of the whole general rule.

The deep reason, one level down, is the Gaussian integers: the numbers a + bi with whole a and b. In that larger world a prime ≡ 1 (mod 4) is not prime at all, it factors as (a + bi)(a − bi), and multiplying that pair back out gives a² + b² = p. A prime ≡ 3 (mod 4) stays stubbornly prime even there, so no such factoring exists, and the sum-of-two-squares fails. Fermat's one-digit tell is really a statement about which ordinary primes crack open when you let yourself use i.

Past the primes, and Lagrange's promise

Once the primes are settled, two rules carry the answer to every other whole number. The first is an identity older than the theorem itself, the Brahmagupta–Fibonacci identity (Brahmagupta, 7th century; Fibonacci, 13th):

(a² + b²)(c² + d²) = (ac − bd)² + (ad + bc)².

In words: multiply two sums-of-two-squares and you get another sum of two squares. So the splittable numbers are closed under multiplication, and the yes-primes breed yes-composites. Multiply 5 = 1²+2² by 13 = 2²+3² and the identity spits out 65 = 4² + 7², while the other choice of sign gives 65 = 8² + 1², the two splits we already saw. The third console works this exact product by hand.

The second rule says the primes ≡ 3 (mod 4) are the only obstruction:

A whole number is a sum of two squares exactly when every prime ≡ 3 (mod 4) in its factorisation appears to an even power.

One stray 3, or 7, or 11, to an odd power, and the number is out; but two of them, or a square of one, and it is back in. Checked here to twenty thousand against a brute-force search, zero disagreements.

And what about the numbers that are locked out of two squares, the 7s and 21s and 23s? They are never locked out for long. The console's final panel is a wall of the numbers 1 to 143, each tile coloured by how many squares it truly needs. The green tiles need just one (the perfect squares); the blue need two (everything console 01 and 02 turned up); the amber need three; and the ember tiles need all four. No tile needs more than four. That is Lagrange's four-square theorem (1770): every natural number, without exception, is a sum of at most four squares. The stubborn ones, the tiles that genuinely need the full four, are not random either. Legendre pinned them down: they are exactly the numbers of the form 4ᵃ(8b + 7), which is why 7, 15, 23, 28, 31 light up ember and almost nothing else does.

So the arc runs from a one-digit test on a single prime out to a guarantee that covers every number there is. Ask whether a prime is two squares and the answer hides in its remainder mod 4. Ask the same of any whole number and the primes ≡ 3 (mod 4) are the only gatekeepers. And ask how far you ever have to go, two squares, three, more? and the answer, forever, is: four is always enough.