Baltic Way 2019

The answer is $n=1$ or $n$ prime. It is clear that $n=1$ has the desired property.

Assume that $n>1$. To see that $n$ must be a prime, assume that $n$ is composite, and let $d$ be a non-trivial divisor of $n$. We consider $k=-2^d$. Since $2$ is a prime number, and $d<n$, $2^d$ is not a perfect $n$th-power so $x^n-2^d=0$ has no integer solutions. On the other hand, $x^n-2^d=(x^{n/d}{)}^d-2^d$ is divisible by $x^{n/d}-2$ which has degree less than $n$ since $d>1$. Therefore $x^n+k$ has no integer root and is not irreducible, and $n$ does not have the desired property.

Assume that $n$ is a prime. If $n=2$, $n$ has the desired property, so assume that $n$ is odd. Let $k$ be given, and define $a=-k^{1/n}$, i.e. $a$ is the real root of $x^n+k$. If $k$ is a perfect $n$th-power, $a$ is an integer, and $x^n+k$ has an integer root. Assume that $k$ is not a perfect $n$th-power. Assume that $f(x)$ is a non-constant polynomial with integer coefficients dividing $x^n+k$. Any root $r\in \mathbb{C}$ of $f$ satisfy $r^n=-k$, and hence $|r{|}^n=k=|a{|}^n$ since also $a^n=-k$. Therefore $|r|=|a|$.

Assume that $\mathrm{deg}f=m$, and $f$ has roots $r_1,\dots ,r_m$. The constant term of $f$ is an integer since $f(x)$ divides $x^n+k$ which has integer coefficients. But the constant term is also given by $(-1{)}^m{r}_1\cdots r_m$, so $|(-1{)}^m{r}_1\cdots r_m|=|a^m|$ is an integer, and hence $a^m$ is an integer. But $a$ was given by $a=-k^{1/n}$ so since $n$ is a prime, and $k$ is not a perfect $n$th-power, $a^m$ is an integer if and only if $n\mid m$. Therefore $n\mid m$, and $\mathrm{deg}f=m\ge n$, so we must have $f(x)=x^n+k$ which shows that $x^n+k$ is irreducible, and $n$ has the desired property.