uniolympiads Ελληνικά

IMC 2001, Day 1, Problem 4

Let kk be a positive integer. Let p(x)p(x) be a polynomial of degree nn each of whose coefficients is −1-1, 11 or 00, and which is divisible by (x−1)k(x - 1)^k. Let qq be a prime such that qln⁡q<kln⁡(n+1)\frac{q}{\ln q} < \frac{k}{\ln(n+1)}. Prove that the complex qqth roots of unity are roots of the polynomial p(x)p(x).

Original from the official PDFLet k be a positive integer. Let p(x) be a polynomial of degree n each of whose coefficients is −1, 1 or 0, and which is divisible by (x − 1) k . Let q be a k prime such that ln q q < ln(n+1) . Prove that the complex qth roots of unity are roots of the polynomial p(x).

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 p(x)=(x−1)k⋅r(x)p(x)=(x-1)^k\cdot r(x) and εj=e2πi⋅j/q\varepsilon_j=e^{2\pi i\cdot j/q} (j=1,2,…,q−1)(j=1,2,\dots,q-1). As is well-known, the polynomial xq−1+xq−2+…+x+1=(x−ε1)…(x−εq−1)x^{q-1}+x^{q-2}+\ldots+x+1=(x-\varepsilon_1)\ldots(x-\varepsilon_{q-1}) is irreducible, thus all ε1,…,εq−1\varepsilon_1,\dots,\varepsilon_{q-1} are roots of r(x)r(x), or none of them.

Suppose that none of ε1,…,εq−1\varepsilon_1,\dots,\varepsilon_{q-1} is a root of r(x)r(x). Then ∏j=1q−1r(εj)\prod_{j=1}^{q-1}r(\varepsilon_j) is a rational integer, which is not 0 and

(n+1)q−1≥∏j=1q−1∣p(εj)∣=∣∏j=1q−1(1−εj)k∣⋅∣∏j=1q−1r(εj)∣≥(n+1)^{q-1}\ge\prod_{j=1}^{q-1}\bigl|p(\varepsilon_j)\bigr|=\left|\prod_{j=1}^{q-1}(1-\varepsilon_j)^k\right|\cdot\left|\prod_{j=1}^{q-1}r(\varepsilon_j)\right|\ge
≥∣∏j=1q−1(1−εj)∣k=(1q−1+1q−2+…+11+1)k=qk.\ge\left|\prod_{j=1}^{q-1}(1-\varepsilon_j)\right|^k=(1^{q-1}+1^{q-2}+\ldots+1^1+1)^k=q^k.
This contradicts the condition qln⁡q<kln⁡(n+1)\frac{q}{\ln q}<\frac{k}{\ln(n+1)}.

Transcribed from the official solutions, page 2. 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?