IMC 2001 · Day 1 · P4

Let $p(x) = (x-1)^k \cdot r(x)$ and $\varepsilon_j = e^{2\pi i \cdot j/q}$ ($j = 1, 2, \dots, q-1$). As is well-known, the polynomial $x^{q-1} + x^{q-2} + \dots + x + 1 = (x - \varepsilon_1) \dots (x - \varepsilon_{q-1})$ is irreducible, thus all $\varepsilon_1, \dots, \varepsilon_{q-1}$ are roots of $r(x)$, or none of them.

Suppose that none of $\varepsilon_1, \dots, \varepsilon_{q-1}$ is a root of $r(x)$. Then $\prod\limits_{j=1}^{q-1} r(\varepsilon_j)$ is a rational integer, which is not 0 and $$\begin{align*} (n+1)^{q-1} \ge \left| \prod_{j=1}^{q-1} p(\varepsilon_j) \right| &= \left| \prod_{j=1}^{q-1} (1 - \varepsilon_j)^k \right| \cdot \left| \prod_{j=1}^{q-1} r(\varepsilon_j) \right| \ge \\ &\ge \left| \prod_{j=1}^{q-1} (1 - \varepsilon_j) \right|^k = (1^{q-1} + 1^{q-2} + \dots + 1^1 + 1)^k = q^k. \end{align*}$$ This contradicts the condition $\dfrac{q}{\ln q} < \dfrac{k}{\ln(n+1)}$.