This post was inspired by a joke from Futurama in which two robots laugh at the fact that their serial numbers (3370318 and 2716057) are both expressible as the sum of two cubes. I’ll explain how to express these numbers as sums of two cubes and discuss some of the relevant mathematics.

## Modular Arithmetic

Modular arithmetic is a basic yet powerful technique in number theory. Whereas usual arithmetic involves the integers, modular arithmetic involves the remainders of integers after division by an integer . Integers that have the same remainder after division by are equivalent in the following sense: we say that and are *congruent modulo* if is a multiple of . This is written . The set

(that is, the set of all integers that are congruent to modulo ) is called the

*congruence class*of .

Everyone who can tell time has used modular arithmetic. Hours are measured modulo 12 (or modulo 24 in military time). 5 hours past 10:00 is 3:00 rather than 15:00. We can write to express this as a congruence relation.

It turns out to be very helpful to consider cubes modulo 9. This is because every cube is congruent to either 0, 1, or -1 modulo 9. You can check this by cubing 0, 1, 2, 3, 4, 5, 6, 7, and 8 (the only possible remainders after division by 9). For example, .

Because cubes can only be congruent to 1, 0, or -1 modulo 9, the sum of two cubes can only be -2, -1, 0, 1, or 2 modulo 9. Therefore any integer that is congruent to 3, 4, 5, or 6 modulo 9 cannot be expressed as the sum of two cubes.

A similar argument shows that any integer that is congruent to 3 or 4 modulo 7 is not expressible as the sum of two cubes. You can check this by cubing 0, 1, 2, 3, 4, 5, and 6.

## Finding two cubes

If an integer is in the right congruence classes modulo 9 and modulo 7, we would like to know if it is possible to express as the sum of two cubes. To do this, we will use the following factorization.

This reduces the problem of finding two cubes that add up to to finding a factorization of the form . Note that when is outside the ellipse . Because of this, we may assume that is the smaller divisor whenever is large enough. I leave it to the reader to verify that is sufficient.

We can simplify our computations by changing coordinates.

The equation becomes . Solving for in terms of and , we obtain

If and are integers, then so are and . It is also true that if and are integers then and are integers, but this is trickier to show. We know that is an integer, and so must be divisible by 4. This is only possible if and are either both even or both odd. (This is yet another helpful application of modular arithmetic: even integers are exactly those that are congruent to 0 modulo 2; odd integers are those which are congruent to 1 modulo 2). From the equations and we see that and are integers.

The upshot of all this is that we can check whether a given integer is a sum of two cubes by (1) finding all factorizations where and (2) checking whether is an integer. Here’s an implementation in Python.

```
import math
```

```
def print_cube_sum(n,a,b):
# Prints n = a^3 + b^3 with appropriate parentheses if a or b is negative.
# This only supports nonnegative n.
# Make sure a is the smaller of a and b so that b > 0.
if a > b:
a, b = b, a
s = str(n) + ' = ' + str(b) + '^3'
if a < 0:
s += ' + (' + str(a) + ')^3'
elif a > 0:
s += ' + ' + str(a) + '^3'
print(s)
return
```

```
def find_two_cubes(n):
if n % 9 not in {0, 1, 2, 7, 8}:
return
if n % 7 not in {0, 1, 2, 5, 6}:
return
# Find divisors c such that n = cd and c <= d.
for c in range(1, math.floor(math.sqrt(n))+1):
if n % c == 0 and 4*n - c**3 >= 0:
d = math.sqrt((4*n - c**3)/(3*c))
if d.is_integer():
# If d is an integer, then a and b are integers and n = a^3 + b^3.
a = int((c - d) // 2)
b = int((c + d) // 2)
print_cube_sum(n,a,b)
return
```

Let’s test this for the numbers 1 through 100, and also for Flexo and Bender’s serial numbers.

```
for n in range(1,101):
find_two_cubes(n)
```

```
# Express Flexo's serial number as a sum of two cubes.
find_two_cubes(3370318)
```

```
# Express Bender's serial number as a sum of two cubes.
find_two_cubes(2716057)
```

Notice that the algorithm failed to find the expression . This is because of our earlier assumption that . When , the inequality is false. This is the only special case that our algorithm missed.

It’s interesting to note that some integers that are in the right congruence classes modulo 9 and modulo 7 are not expressible as the sum of two cubes. 20, for example, is congruent to 2 modulo 9 and -1 modulo 7, yet it is not expressible as a sum of two cubes.

## Broughan’s Theorem

A very nice paper by Kevin A. Broughan explains why some numbers (like 20) aren’t expressible as a sum of two cubes. Broughan’s main theorem is this:

The equation has a solution in positive integers and if and only if the following three conditions are satisfied:

- There exists a divisor of with such that
- for some positive integer , and such that
- is a perfect square.

has a solution in positive integers and if and only if the following three conditions are satisfied:

- There exists a divisor of with such that
- for some positive integer , and such that
- is a perfect square.

An interesting corollary of Broughan’s theorem is that no prime number (except for 2) is expressible as a sum of two positive cubes.

## Russell Schwartz says:

Doesn’t it follow immediately from the factorization $a^3 + b^3 = (a+b)(a^2 – ab + b^2)$ that no odd prime is expressible as the sum of two positive cubes?

Thanks for the fun read!