A week ago I chatted with my son Sergei about memorable math problems. He mentioned problem 5 from USAMO 2007. The problem can be reduced to the following:
Prove that (x7 + 1)/(x + 1) is composite for x = 77n, where n is a non-negative integer.
Perhaps Sergei remembered this problem because as far as he knew, he was the only one in that competition to solve it. That made me curious as to how he solved it. His solution is available as solution 2 at the Art of Problem Solving website. His solution seemed mysterious and impossible to invent on the spot. I became even more curious to understand the thought process underlying his solution.
Here is his recollection:
We need to factor x6 − x5 + x4 − x3 + x2 − x + 1. If such factoring existed it would have been known. Therefore, we need to somehow use the fact that x = 77n. What is the simplest way to factor? We should try to represent the polynomial in question as the difference of squares. Luckily, x is an odd power of 7. We can make it a square if we multiply or divide it by 7 or another odd power of 7. So with a supply of squares on one side, we need to find a match for one of them to build the difference.
Let us simplify the problem and see what happens for (y3 + 1)/(y + 1) for y = 33n, when n = 1. In other words we want to represent 703 as a difference of squares. This can be done: 703 = 282 − 92. Now let us see how we can express 282 and 92 through y which in this case is equal to 27. The first term is (y + 1)2, and the second is 3y.
Now let’s go back to 7 and x, and check whether (x + 1)6 − (x6 − x5 + x4 − x3 + x2 − x + 1) is 7x. Oops, no. The difference is 7x5 + 14x4 + 21x3 + 14x2 +7x. On the plus side, it is divisible by 7x which we know is a square. The leftover factor is x4 + 2x3 + 3x2 +2x + 1, which is a square of x2 +x + 1.
The problem is solved, but the mystery remains. The problem can’t be generalized to numbers other than 3 and 7.