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



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!