# Positive integer solutions of $a^3 + b^3 = c$

Is there any fast way to solve for positive integer solutions of $$a^3 + b^3 = c$$ knowing $c$?
My current method is checking if $c – a^3$ is a perfect cube for a range of numbers for $a$, but this takes a lot of time for larger numbers. I know $c = (a+b)(a^2-ab+b^2)$, but I can’t think of a way this would speed up the process. Factoring numbers can be done fairly quickly but then the values of $a$ and $b$ have to be chosen. This is for a previous question I had about Fibonacci numbers. Any relevant literature is appreciated.

#### Solutions Collecting From Web of "Positive integer solutions of $a^3 + b^3 = c$"

A very fast way to see that a positive integer $c$ is not the sum of two cubes are modular constraints. The equation $a^3+b^3=c$ has no integer solutions if $c$ satisfies one of the following congruences:

$$(1) \quad c\equiv 3,4 \mod 7$$

$$(2) \quad c\equiv 3,4,5,6 \mod 9$$

$$(3) \quad c\equiv 3,4,5,6,10,11,12,13,14,15,17,18,21, 22, 23, 24, 25, 30, 31, 32, 33, 38, 39, 40, 41, 42, 45, 46, 48, 49, 50, 51, 52, 53, 57, 58, 59, 60 \mod 63$$

On the other hand, there are intrinsic properties of $c$ known, such that $c$ is the sum of two squares:

Theorem (Broughan 2003): Let $c$ be a positive integer. Then the equation $c=a^3+b^3$ has solutions in positive integers if and only if the following conditions are satisfied:

1.) There exists a divisor $d\mid c$ with $c^{1/3}\le d\le 2^{2/3}c^{1/3}$ such that

2.) for some positive integer $l$ we have $d^2-c/d=3l$ such that

3.) the integer $d^2-4l$ is a perfect square.

$c=(a+b)(a^2−ab+b^2)$ should actually be quite helpful. After factoring $c$, you find all possibly ways of writing $c = xy$. Let $x = a + b$ or $b = x – a$, so

$$a^2-ab+b^2 = a^2 – a(x-a) + (x-a)^2 = 3a^2 – 3ax + x^2 = y$$

Solve this quadratic equation for a and check that a is an integer.

Obviously many factors need not be examined: If we keep the sum $x = a+b$ fixed, then $a^3 + b^3$ is between $x^3/4$ and $x^3$, so $x$ must be between $c^{1/3}$ and $(4c)^{1/3}$.

After reading previous posts, this seems to be a published result, cited as (Broughan, 2003). Had a look at the paper. Oh well, you can sure make this complicated.

For not very large c, say $c < 10^9$, brute force may be quicker: Let a = 0, b = $c^{1/3}$, rounded down. As long as $a^3 + b^3 < c$ increase a by 1. If $a^3 + b^3 = c$ note that you found a solution. Then decrease b by 1, repeat until $a > b$.

You might as well concentrate on the case that $a$ and $b$ are relatively prime. This means that $a^{2}+b^{2}-ab$ must either be a product of primes all congruent to $1$ (mod $3$), or else $3$ times such a product. Hence if you write $c = 3^{m-1}d\cdot3f$, where $3^{m}$ is the exact power of $3$ dividing $c$ and $d$ is the product of all prime divisors of $c$ which are congruent to $2$ (mod $3$) (including multiplicities), then if $m=0$, we need to express $f$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ (and this can be done). If $m >0$, we need to express $3f$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ (and this can be done). For every such expression (and the number of such expressions can be calculated precisely from the rational prime factorization of $f$), we need to check whether or not $d = x+y$ when $m = 0$, or $3^{m-1}d = x+y$ when $m >0$.

While this is theoretically correct, I can’t claim that it is fast or efficient (it depends on factorization properties of the Eisenstein integers $\mathbb{Z}[\omega]$, where $\omega = e^{\frac{2 \pi i}{3}}\!\!$). However, let’s analyse $c = 468 = 9 \times 52$. According to the above method, we have to express $39$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ and we should have $x+y = 12$ if we are to obtain $x^{3}+y^{3} = 468$. At this stage there are few possibilities to check and up to symmetry, the solution is $x = 5,y = 7$. It might be helpful to note that in general, we need $(3^{m-1}d)^{2} > 3f$ when $3$ divides $c$ and $d^{2} > f$ when $3$ does not divide $c$, if there is to be any chance of having solution to $c = a^{3}+b^{3}$, with $a$ and $b$ both positive.