uniolympiads Ελληνικά

IMC 2008, Day 2, Problem 1

Let n,kn, k be positive integers and suppose that the polynomial x2k−xk+1x^{2k} - x^k + 1 divides x2n+xn+1x^{2n} + x^n + 1. Prove that x2k+xk+1x^{2k} + x^k + 1 divides x2n+xn+1x^{2n} + x^n + 1.

Original from the official PDFLet n, k be positive integers and suppose that the polynomial x 2k − x k + 1 divides x 2n + x n + 1. Prove that x 2k + x k + 1 divides x 2n + x n + 1.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Let f(x)=x2n+xn+1f(x) = x^{2n} + x^n + 1, g(x)=x2k−xk+1g(x) = x^{2k} - x^k + 1, h(x)=x2k+xk+1h(x) = x^{2k} + x^k + 1. The complex number x1=cos⁡(π3k)+isin⁡(π3k)x_1 = \cos(\frac{\pi}{3k}) + i\sin(\frac{\pi}{3k}) is a root of g(x)g(x).

Let α=πn3k\alpha = \frac{\pi n}{3k}. Since g(x)g(x) divides f(x)f(x), f(x1)=g(x1)=0f(x_1) = g(x_1) = 0. So, 0=x12n+x1n+1=(cos⁡(2α)+isin⁡(2α))+(cos⁡α+isin⁡α)+1=00 = x_1^{2n} + x_1^n + 1 = (\cos(2\alpha) + i\sin(2\alpha)) + (\cos\alpha + i\sin\alpha) + 1 = 0, and (2cos⁡α+1)(cos⁡α+isin⁡α)=0(2\cos\alpha + 1)(\cos\alpha + i\sin\alpha) = 0. Hence 2cos⁡α+1=02\cos\alpha + 1 = 0, i.e. α=±2π3+2πc\alpha = \pm\frac{2\pi}{3} + 2\pi c, where c∈Zc \in \mathbb{Z}.

Let x2x_2 be a root of the polynomial h(x)h(x). Since h(x)=x3k−1xk−1h(x) = \frac{x^{3k}-1}{x^k-1}, the roots of the polynomial h(x)h(x) are distinct and they are x2=cos⁡2πs3k+isin⁡2πs3kx_2 = \cos\frac{2\pi s}{3k} + i\sin\frac{2\pi s}{3k}, where s=3a±1,a∈Zs = 3a \pm 1, a \in \mathbb{Z}. It is enough to prove that f(x2)=0f(x_2) = 0. We have f(x2)=x22n+x2n+1=(cos⁡(4sα)+sin⁡(4sα))+(cos⁡(2sα)+sin⁡(2sα))+1=(2cos⁡(2sα)+1)(cos⁡(2sα)+isin⁡(2sα))=0f(x_2) = x_2^{2n} + x_2^n + 1 = (\cos(4s\alpha) + \sin(4s\alpha)) + (\cos(2s\alpha) + \sin(2s\alpha)) + 1 = (2\cos(2s\alpha) + 1)(\cos(2s\alpha) + i\sin(2s\alpha)) = 0 (since 2cos⁡(2sα)+1=2cos⁡(2s(±2π3+2πc))+1=2cos⁡(4πs3)+1=2cos⁡(4π3(3a±1))+1=02\cos(2s\alpha) + 1 = 2\cos(2s(\pm\frac{2\pi}{3} + 2\pi c)) + 1 = 2\cos(\frac{4\pi s}{3}) + 1 = 2\cos(\frac{4\pi}{3}(3a \pm 1)) + 1 = 0).

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?