The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. In the week leading up to the contest, I plan to take a look at some of the problems from the senior paper from 2018. A list of all the posts can be found here.

Today we will look at the third problem from the 2018 South African Mathematics Olympiad:

Determine the smallest positive integer n whose prime factors are all greater than 18, and that can be expressed as n = a^3 + b^3 with positive integers a and b.

In many number theory problems, it helps to consider the prime factors of the numbers involved, and in this problem we are in fact forced to do so because the question itself is about the prime factors of a number. When dealing with factors of a number or an expression representing some number, it of course helps to consider whether we can factorise the given expression.

We recall (or learn for the first time) the factorisation a^3 + b^3 = (a + b)(a^2 - ab + b^2). Since all of the prime factors of n are greater than 18, the same is true for the prime factors of a + b and a^2 - ab + b^2.

For n to be small, a and b, and hence a + b, should be reasonably small. We are led to consider solutions where a + b is as small as possible. We do need to be careful, however. It is not automatically true that the value of n that we find when considering the smallest possible value of a + b is necessarily the smallest possible value of n. Considering the smallest possible value of a + b might be a valuable starting point, but we would need to do more work to establish that the value that we find is the true minimum. It is not true that larger values of a + b correspond to larger values of a^3 + b^3 in general. For example, we have that 1^3 + 4^3 > 3^3 + 3^3 even though 1 + 4 < 3 + 3.

Ignoring for now the problem of finding the optimal value of a + b (we have seen above that it is not necessarily the smallest possible value of a + b), how would we go about finding the smallest value of a^3 + b^3 if we have already chosen a fixed value for a + b?

Experience with inequalities, or some experimentation, leads one to speculate that for a given value of a + b, the minimum value of a^3 + b^3 will occur when a and b are equal, and that the value of a^3 + b^3 increases as a and b move further apart. This can be proven by showing that

\displaystyle f(x) = {\left(\frac{a + b}{2} - x\right)}^3 + {\left(\frac{a + b}{2} + x\right)}^3

is an increasing function of x for non-negative values of x. In fact, we have that

\displaystyle f(x) = \frac{{(a + b)}^3}{4} + 3(a + b) x^2

which is a parabola with a turning point at x = 0. It is clear that as x increases, so does the value of f(x).

Another way of establishing the same result would be to show that if x and y are positive integers, then {(x - 1)}^3 + {(y + 1)}^3 > x^3 + y^3. The reader is invited to fill in the details for this approach.

We know that a + b does not have any prime factors smaller than 18, and so a + b must be larger than 18. The smallest value that we need to consider is then a + b = 19. In this case, we know that a^3 + b^3 is minimised when a = 9 and b = 10. (Remember that a and b must be integers, so the expression is minimised when these are the closest integers to \frac{19}{2}.) For these values, we find that

\displaystyle a^3 + b^3 = 19 (9^2 - 9 \times 10 + 10^2) = 19 \times 91 = 7 \times 13 \times 19.

This has prime factors which are smaller than 18, and so is not a valid solution. The next smallest value of a^3 + b^3 occurs when a = 8 and b = 11. In this case we have that

\displaystyle a^3 + b^3 = 19 \times (8^2 - 8 \times 11 + 11^2) = 19 \times 97.

This number indeed has no prime factors smaller than 18, and so is a candidate for the smallest value of n that solves the problem. We need only verify that it is not possible to find a smaller value of n by considering a larger value of a + b.

We saw earlier that the smallest possible value of a^3 + b^3 for some fixed value of a + b is equal to

\displaystyle \frac{{(a + b)}^3}{4}.

Perhaps it is the case that for larger values of a + b, this minimum value of a^3 + b^3 is already larger than 19 \times 97 = 1843. We note that the next smallest possible value for a + b is 23. (All the numbers between 19 and 23 have prime factors which are smaller than 18.) We see that if a + b \neq 19, and a + b has no prime factors smaller than 18, then

\displaystyle a^3 + b^3 \geq \frac{{(a + b)}^3}{4} \geq \frac{23^3}{4} = 3041.75.

This is indeed larger than 1843, and so it is not possible to find a smaller value for n by considering a larger value for a + b. The smallest n satisfying the conditions of the problem is thus 1843 = 8^3 + 11^3.

How clear is this post?