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.

About these ads

By nbloomf, on December 26, 2010 at 10:00 am, under AA:DF. Tags: integers, irreducible polynomial. 1 Comment

Comments

ai On July 24, 2011 at 12:57 pm
Permalink | Reply

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$ .

Project Crazy Project

Prove that a given polynomial over ZZ is irreducible

Like this:

Related

Comments

Leave a Reply Cancel reply

What is this?

Contact

Navigation

Search PCP

Categories

Crazy Page Views

Tag Cloud

Tools

Similar Projects

Posts By Date

Recent Comments

Diversions

Follow “Project Crazy Project”