USAMO 2007, Problem 5
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.
Share:
ano:
Interesting, thank you. Does your last sentence mean that for any number m other than 3 and 7, (x^m+1)/(x+1) is not necessarily composite for all x=m^(m^n)? Or do you just mean that the same idea does not seem to work (which is intriguing, as you say)?
20 May 2010, 10:41 amTanya Khovanova:
ano,
The same idea doesn’t seem to work.
20 May 2010, 10:46 amSteven Stadnicki:
Well, in general (x+1)(m-1)-(xm+1)/(x+1) is going to be divisible by m; this is just saying that the binomial coefficients (m-1 C n) are congruent to (-1)n mod m. But there’s no reason to expect the result (of dividing by m*x, specifically) to be a square; still, given that we’re talking about Pascal’s triangle here and given the well-known patterns of coefficients (especially mod 2), maybe the proof provided goes through whenever m is a Mersenne prime?
20 May 2010, 4:25 pmSteven Stadnicki:
Augh, failure of the sup tag there. That should be (x+1)^(m-1)-(x^m+1)/(x+1), of course, and (-1)^n later in the sentence.
20 May 2010, 7:13 pmT.:
This has a generalization to cyclotomic polynomials of order p and 2p. The first few examples:
p=3 x^2 + x + 1 = (x-1)^2 + 3x is composite when x = -3t^2
2p=4 x^2 + 1 = (x+1)^2 – 2x is composite when x=2t^2
p=5 x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 – 5x(x+1)^2 is composite when x = 5t^2
2p=6 x^2 – x + 1 = (x+1)^2 – 3x is composite when x = 3t^2
p=7 (x^7 – 1)/(x-1) = (x-1)^6 + 7x (x^2 – x + 1)^2 is composite when x = -7t^2
For the problem at hand, 2p=14, and (x^7+1)/(x+1) is composite when x=7t^2
21 May 2010, 4:33 amFabiano Mendes:
I find the following identity holds for k=0,1,2
21 May 2010, 8:12 am(y+1)^(2k+2)-[y^(2k+3)+1]/(y+1)=(2k+3)y(y^2+y+1)^k
T.:
Identities based on (x + 1)^k or (x-1)^k don’t work for higher exponents. The general pattern is based on Gauss sums and is used in factorizing numbers of the form x^p +- Ay^p.
22 May 2010, 12:56 amFabiano Mendes:
Maybe the mystery has been solved [Fermat squares]
27 May 2010, 2:39 pmhttps://www.qbyte.org/puzzles/p158s.html