Saturday, April 28, 2007

Just A "Natural" Thing. Topic: Algebra. Level: AIME/Olympiad.

Problem: Factor $ 7^{6(2k-1)}-7^{5(2k-1)}+7^{4(2k-1)}-7^{3(2k-1)}+7^{2(2k-1)}-7^{2k-1}+1 $.

Solution: Consider the polynomial $ x^7+1 $. We have

$ x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-1) $,

so we want to factor the second term when $ x = 7^{2k-1} $. Call it $ P(x) $ so that $ P(x) = \frac{x^7+1}{x+1} $. Consider the relation

$ (x+1)^7-(x^7+1) = 7x^6+21x^5+35x^4+35x^3+21x^2+7x $.

Since $ -1 $ is a root of the LHS, we factor it out of the RHS as well to get

$ (x+1)^7-(x^7+1) = 7x(x+1)(x^4+2x^3+3x^2+2x+1) = 7x(x+1)(x^2+x+1)^2 $.

Dividing through by $ x+1 $ and rearranging, we obtain the nice expression

$ P(x) = (x+1)^6-7x(x^2+x+1)^2 $.

Letting $ x = 7^{2k-1} $, this becomes

$ P(7^{2k-1}) = (7^{3(2k-1)}+3 \cdot 7^{2(2k-1)}+3 \cdot 7^{2k-1}+1)^2-7^{2k}(7^{2(2k-1)}+7^{2k-1}+1)^2 $

which is conveniently enough a difference of two squares. And we'll leave it as this because the factors are not particularly nice or anything. QED.


Comment: This "natural" factorization was basically the one crucial step to solving the USAMO #5 this year and most people did not see it, unsurprisingly. Taking the difference $ (x+1)^7-(x^7+1) $ was the trickiest/cleverest part, and there were definitely a limited number of approaches to this factorization. Oh well, at least it seems sort of cool after you know about it.


Practice Problem: (2007 USAMO - #5) Prove that for every nonnegative integer n, the number $7^{7^{n}}+1$ is the product of at least $2n+3$ (not necessarily distinct) primes.

1 comment:

  1. Man, I wish I could come up with problems this contrived.