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.

Post a comment or leave a trackback: Trackback URL.


  • ai  On July 24, 2011 at 12:57 pm

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: