## Prove that a given polynomial over ZZ is irreducible

Let $n \geq 1$. Prove that $p(x) = \prod_{k=1}^n (x-k) + 1$ is irreducible over $\mathbb{Z}$ for all $n \neq 4$.

[There is probably a more direct way to do this.]

We begin with a combinatorial lemma.

Lemma: Let $n = 2m \geq 6$ be an even integer. Then there does not exist a partition $\{A,B\}$ of $[1,n]$ such that $|A| = |B|$ and $\prod A - \prod B = 2$. Proof: Note that $\mathsf{gcd}(\prod A, \prod B) \in \{1,2\}$. If $\mathsf{gcd}(\prod A, \prod B) = 1$, then since $2 \in [1,n]$, one of $\prod A$ and $\prod B$ is odd and the other even. Mod 2 we have $1 \equiv 0$, a contradiction. Thus $\mathsf{gcd}(\prod A, \prod B) = 2$. In particular, for each odd prime $p$, if $p \in A$ then all multiples of $p$ are in $A$; likewise for $B$. Also, one of $A$ or $B$ contains only odd numbers except for one, which is maximally divisible by $2^1$.

Now we will consider how 2, 3, 4, and 5 might be distributed between $A$ and $B$. Suppose $3$ and $4$ are in different classes. Then $3$ and $2$ are in the same class, and so $6$ and $2$ are in the same class. But then 4 divides $\prod A$ and $\prod B$, a contradiction. Thus 3 and 4 are in the same class. Suppose now that 5 is in the same class as 3 and 4. Now the class containing 3, 4, and 5 must contain all multiples of 3 and 5, as well as all multiples of 2 except for one. Since $n$ is even and greater than 5, this class contains $m+1$ elements, a contradiction since $A$ and $B$ must have the same cardinality. Thus it must be the case that 3 and 4 are in the same class and 5 is in the other class. Then 2 must be in the same class as 5. But now 10 cannot be in either class, since it is both even and a multiple of 5. So $n \in \{6,8\}$.

Suppose $n = 6$. We are forced to have 3 and 4 in one class and 5 and 2 in the other; thus 6 is forced to be in the class with 3 and 4 and 1 with 5 and 2. But then the products $\prod A$ and $\prod B$ are 72 and 10; neither difference of these is 2.

Suppose $n = 8$. Again, the divisibility criteria force the partition $\{\{3,4,6,8\}, \{1,2,5,7\}\}$, but now $\prod A$ and $\prod B$ are 70 and 576, a contradiction.

Thus no such partition exists. $\square$

We are now prepared for the main problem.

Let $n \geq 1$ and $p(x) = \prod_{k=1}^n (x-k) + 1$. Suppose $p(x)$ is reducible in $\mathbb{Z}[x]$, with $p(x) = a(x)b(x)$. Note that for each $k \in [1,n]$, we have $p(x) = a(x)b(x) = 1$. Since $a,b \in \mathbb{Z}[x]$, we have $a(k),b(k) \in \mathbb{Z}$ for all such $k$; thus $a(k),b(k) \in \{1,-1\}$, and moreover $a(k) = b(k)$. Let $A = \{k \in [1,n] \ |\ a(k) = 1\}$ and $B = [1,n] \setminus A$. Certainly then $b(k) = -1$ for all $k \in B$. By a lemma to this previous exercise, we have $a(x) = q(x)\prod_{k \in A} (x-k) + 1$ and $b(x) = r(x)\prod_{k \in B} (x-k) - 1$. Considering degrees and the monicness of $a$ and $b$, we have $q = r = 1$. Now $p(x) = a(x)b(x) = (\prod_{k \in A} (x-k) - 1)(\prod_{k \in B} (x-k) + 1) = p(x) + \prod_{k \in A} (x-k) - \prod_{k \in B} (x-k) + 2$, and thus $\prod_{k \in B} (x-k) - \prod_{k \in A} (x-k) = 2$. If $|A| \neq |B|$, then the left hand side of this equation has positive degree while the right is constant, a contradiction. Thus $|A| = |B|$, and in particular $n = 2m$ is even. Now evaluating at $x = 0$, we have $(-1)^m \prod_{k \in B} k - (-1)^m \prod k = 2$, and thus $\prod_{k \in B} k - \prod_{k \in A} k = 2$ or $\prod_{k \in A} k - \prod_{k \in B} k = 2$, depending on whether $m$ is even or odd. In either case, no such partition $A$ exists for $n \geq 6$, so that $n \in \{2,4\}$.

Note that for $n = 2$, $p(x) = x^2 - 3x + 3$. This polynomial is Eisenstein at 3 and thus irreducible. For $n = 4$, we have $p(x) = x^4 - 10x^3 + 35x^2 - 50x + 25$. Taking the partition $\{\{2,3\},\{1,4\}$, we let $a(x) = (x-2)(x-3) - 1 = x^2 - 5x + 5$ and $b(x) = (x-1)(x-4) + 1 = x^2 - 5x + 5$; indeed, $p(x) = (x^2 -5x + 5)^2$ is reducible.

A more direct way for $n\geq5$ is to assume for reductio that $p(x)$ is reducible, and to reduce as you did to the case that $p(x)=a(x)^2$. Then $n$ must be even, so $n\geq6$. Evaluating the equation at $x = 3/2$ we have that the RHS is $\geq0$, but the LHS is $< -5$, a contradiction. So $p(x)$ is irreducible for all $n\geq 5$.