5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ another way to express $a^3+b^3$ might be $(a+b)[(a+b)^2-3ab]$. $\endgroup$ – Brian J. Fink May 19 '14 at 19:22
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is a link: researchcommons.waikato.ac.nz/handle/10289/2026. $\endgroup$ – marty cohen May 13 '14 at 0:24
  • $\begingroup$ There are also modular constraints which don't exclude values of $c$ but lead to modular conditions on any associated $a^3$ and $b^3$. For example, if $c \equiv 2\mod 7$ then $a^3,b^3 \equiv 1\mod 7$. $\endgroup$ – Adam Bailey May 16 '14 at 12:50
  • $\begingroup$ I'm curious: is there a set of modular constraints that only test for sums of positive cubes? Because as the test stands, it's flagging perfect cubes and differences of cubes a well. I believe the OP clearly stated that he wanted positive integer solutions. $\endgroup$ – Brian J. Fink May 16 '14 at 23:52
  • $\begingroup$ @BrianJ.Fink The modular constraints are best thought of not as flagging possible solutions but as excluding impossible values, either impossible values of $c$ or, for given $c$, impossible values of $a^3,b^3$. The exclusion of values which are impossible for modular reasons from the set of all positive values of $c,a^3,b^3$ can help to find positive solutions faster. It doesn't matter if, as is the case, the modular constraints also apply to $a^3+(-b)^3=c$. $\endgroup$ – Adam Bailey May 17 '14 at 10:15
  • $\begingroup$ @AdamBailey it remains that the modular constraints do not exclude nonpositive values of a,b and since the OP requested positive solutions, it would be far better to come up with constraints that show when $c=a^3+b^3$ has no solutions in $\mathbb{N}$, not just $\mathbb{Z}$. $\endgroup$ – Brian J. Fink May 18 '14 at 0:39
2
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ How is this f aster than checking every value of $a$? $\endgroup$ – qwr May 13 '14 at 1:08
  • 1
    $\begingroup$ You solve one quadratic equation for every factor x of c, instead of checking x different values. $\endgroup$ – gnasher729 May 13 '14 at 1:11
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.