# Next step to take in this proof by contradiction?

This is a problem from Discrete Mathematics and its Applications

Here is my work so far

It's similar to this other question I had Next step to take to reach the contradiction?.

I am assuming that I what I am trying to prove is false, that is there is a positive perfect cube less than 1000 that is the sum of the cubes of two positive integers. From here I need to take logical steps to show that assuming that what I am trying to prove is false leads to a contradiction(false no matter what is passed in).

The first algebraic step I took was saying that if s^3 < 1000, cubing root both sides, s < 10. The next logical step i took was saying that if a^3 + b ^3 = s ^ 3, a^3 + b^3 < 1000 as well. If a ^ 3 + b ^ 3 < 1000, I implied that a ^ 3 < 1000 and b ^ 3 < 1000 because if either component >= 1000, the result will also be >= 1000. Going off of that, repeating(recursion) the step I did for s^3 < 1000. I got that b < 10 and a < 10.

In the end i have three intervals 0 < s < 10, 0 < a < 10, and 0 < b < 10. I don't where to go from here though. I think it be too brute force to test every s from 1 to 9 and showing that there is no a^3 and b^3 that will add to it.

What's the next step I should take to reach the contradiction that would be more efficient/not as exhaustive?

• The number of cases is small, and one can use shortcuts. "Brute force" is not at all brutal. – André Nicolas Jan 22 '15 at 2:27
• Thanks for disclosing the course that you're taking; it helps provide good answers. Textbooks are usually named with their authors since their titles are so similar. Is that Ensley and Cawley's book? – Matthew Leingang Jan 22 '15 at 2:28
• think so McGraw Hill? – committedandroider Jan 22 '15 at 21:35

An analytic proof is probably beyond the scope of your discrete math course. I suspect brute force is the intended approach from here.

• but for this you would still have to check (9,8), (9,7), ....(9,1), (8,8),...(8,1), all the way down to (1,1) which i think is too many cases... – committedandroider Jan 22 '15 at 21:37

As M. Leingang says, this is likely intended to be a brute force problem. But there are ways to pare the solution set down.

For instance, note that if $a$ and $b$ are both even or both odd, then $s$ must be even, and must be odd otherwise. Also note that we can interchange $a$ and $b$ without loss of generality, so we only need to check for $a \leq b$. These two facts alone should make the problem very manageable.

• can you say change interchange a and b without loss of generality because a^3 + b^3 is the same as b^3 + a ^3? – committedandroider Jan 22 '15 at 21:29
• Yes, exactly. Once you have checked e.g. $3^3 + 5^3$ there is no need to check $5^3 + 3^3$. – Michael Cromer Jan 22 '15 at 21:34
• but for this you would still have to check (9,8), (9,7), ....(9,1), (8,8),...(8,1), all the way down to (1,1) which i think is too many cases... – committedandroider Jan 22 '15 at 21:36
• It is 45 cases. But even $9^3 + 8^3 = 1241 > 1000$, so you can discard some anyway - I count 41 valid cases. Just write down a list of these 41 numbers, then a list of the nine cubes $1^3, \ldots, 9^3$ - 50 numbers in all. If these two lists do not have any numbers in common, you have proved it. – Michael Cromer Jan 22 '15 at 21:51
• I feel like the question is supposed to get you to leverage proof by cases which is what you mentioned to get less than 10 cases like all the other problems. I feel like even 41 valid cases is too many to consider. – committedandroider Jan 22 '15 at 21:53

List the cubes less than 1000. There are only 9 of them. Now if $a^3+b^3 = 1000$, then of course $a^3 = 1000-b^3$ and so you only have to check 10 cases, one for each $b$, seeing whether $1000-b^3$ is in your list or not. This would take no more than 1 minute if you already have the list.