I am facing the following problem:
Let $n \in \mathbb{N}_{\geq0}$ and $f \in \mathbb{Z}[X]$ be a polynomial with $\deg f = 2n + 1$, as well as (in pairs different) $a_1, \dots, a_{2n+1}$ such that $f(a_i) \in \{+1, -1\}, \forall i \in {1,\dots,2n+1}$. Show that $f$ is irreducible in $\mathbb{Z}[X]$ and $\mathbb{Q}[X]$.
Usually I have some ideas to start with, but this time I am totally stuck. One 'idea' would have been to show that $f$ is primitive and then try to show that $f$ is irreducible in $\mathbb{F}_2[X]$.
Any hints, ideas? Thank you very much in advance.
Suppose $f = gh, g, h \in \mathbb{Z}[x]$. We'll show that at least one of $g$ or $h$ is constant.
If $f(a) = \pm 1$, then $g(a)$ and $h(a)$ are also equal to $\pm 1$. One of these, WLOG $g$, has degree at most $n$. But $g(a) = \pm 1$ for $2n+1$ different values of $a$. By pigeonhole, it takes the same value (either $1$ or $-1$) at least $n+1$ times, and so since it has degree at most $n$, it must in fact be constant with that value.