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 whose prime factors are all greater than , and that can be expressed as with positive integers and .
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 . Since all of the prime factors of are greater than , the same is true for the prime factors of and .
For to be small, and , and hence , should be reasonably small. We are led to consider solutions where is as small as possible. We do need to be careful, however. It is not automatically true that the value of that we find when considering the smallest possible value of is necessarily the smallest possible value of . Considering the smallest possible value of 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 correspond to larger values of in general. For example, we have that even though .
Ignoring for now the problem of finding the optimal value of (we have seen above that it is not necessarily the smallest possible value of ), how would we go about finding the smallest value of if we have already chosen a fixed value for ?
Experience with inequalities, or some experimentation, leads one to speculate that for a given value of , the minimum value of will occur when and are equal, and that the value of increases as and move further apart. This can be proven by showing that
is an increasing function of for non-negative values of . In fact, we have that
which is a parabola with a turning point at . It is clear that as increases, so does the value of .
Another way of establishing the same result would be to show that if and are positive integers, then . The reader is invited to fill in the details for this approach.
We know that does not have any prime factors smaller than , and so must be larger than . The smallest value that we need to consider is then . In this case, we know that is minimised when and . (Remember that and must be integers, so the expression is minimised when these are the closest integers to .) For these values, we find that
This has prime factors which are smaller than , and so is not a valid solution. The next smallest value of occurs when and . In this case we have that
This number indeed has no prime factors smaller than , and so is a candidate for the smallest value of that solves the problem. We need only verify that it is not possible to find a smaller value of by considering a larger value of .
We saw earlier that the smallest possible value of for some fixed value of is equal to
Perhaps it is the case that for larger values of , this minimum value of is already larger than . We note that the next smallest possible value for is . (All the numbers between and have prime factors which are smaller than .) We see that if , and has no prime factors smaller than , then
This is indeed larger than , and so it is not possible to find a smaller value for by considering a larger value for . The smallest satisfying the conditions of the problem is thus .