Let $p$ a prime number, $p\geq 5$. Find the number of polynomials of the form \[ x^p + px^k + p x^l + 1, \quad k > l, \quad k, l \in \left\{1,2,\dots,p-1\right\}, \]which are irreducible in $\mathbb{Z}[X]$. Valentin Vornicu
Problem
Source: Romanian TST 1 2006, Problem 2
Tags: algebra, polynomial, algebra proposed
19.04.2006 22:02
Consider the polynomial in $\mathbb Z_p[x]$. We say that it has the factorization : \[ x^p+1=(x+1)^p \] It's true because $(x+1)^p=\sum_{i=0}^p {p\choose i} x^i=x^p+1$ and $p|{p\choose i}$ for $0<i<p$. Now suppose that in $\mathbb Z[x]$ we have \[ x^p+px^k+px^l+1=g(x)h(x) \]. So in $\mathbb Z_p[x]$ we must have \[ h(x)=(x+1)^k \] and \[ g(x)=(x+1)^{p-k} \]. So we have \[ x^p+px^k+px^l+1=((x+1)^k+pr(x))((x+1)^{p-k}+ps(x)) \] for some $r(x),s(x)\in \mathbb Z[x]$. But now just put $x=-1$ in the equation and we get \[ (-1)^k+(-1)^l=pr(-1)ps(-1) \] So if $2|k-l$ then the lhs is $2$ or $-2$ but rhs is divisible by $p$ which is contradiction. But if $2\nmid k-l$ then we obviously have that $x+1|x^p+px^l+px^k+1$ and so the polynomial is reducible. So the answer is the number of $k,l$ pairs such that $2| k-l$ and that is $2{\frac{p-1}2\choose2}$.
19.04.2006 22:11
Note that, if $k-l$ is odd, then $x+1$ divides $x^p+1$ and also $x^k+x^l$, so $P(x)$ is not irreducible. Now suppose $k=l+2r$, $r$ a positive integer. Then let $Q(x)=P(x-1)$. We'll prove that $Q(x)$ is irreducible, from which it will follow that $P(x)$ is irreducible as well. We have $P(x-1)=(x-1)^p+p(x-1)^k+p(x-1)^l+1$. The binomial expansion of the first term produces multiples of $p$, except for the last term, which is $-1$ and cancels out with the fourth term, $1$. The binomial expansions of the middle two terms produce multiples of $p$ (obviously, since they are multiples of $p$ themselves). The last terms given by each expansion are either both $p$ or both $-p$, since $k, l$ are both even or both odd. Thus $P(x-1)=x^p+pxR(x) \pm 2p$, which is irreducible by Eisenstein's criterion. So we have to count the number of pairs $k, l$ with $k-l$ even, $p>k>l>0$. This gives $2 \times \binom{ \frac{p-1}{2}}{2}$.
29.07.2016 21:14
Nima Ahmadi Pour wrote: ... But if $2\nmid k-l$ then we obviously have that $x+1|x^p+px^l+px^k+1$ and so the polynomial is reducible. ... Why??
29.07.2016 21:51
Wow, 10-year-old post! It's saying that -1 is a root since $(-1)^p=-1$, and $(-1)^l$ and $(-1)^k$ have opposite signs because $l$ and $k$ have odd difference.
30.11.2020 19:59
The answer is when $k, l$ are same parity. Clearly if they are different parity, then $x + 1$ is a factor. Let $f(x) = x^{p} + px^{l} + px^{k} + 1$, where $k, l$ are the same parity. By the rational root theorem, since $f(\pm1)\neq 0$, this means $f$ has no rational roots. Assume $f = g\cdot h$ for nonconstant polynomials $g, h$. Take $\mod p$ to get $g\cdot h\equiv x^{p} + 1 = (x+1)(x^{p-1} - x^{p-2} + \ldots + 1)$. Observe that $\Phi_{2p} = (x^{p-1} - x^{p-2} + \ldots + 1)$, so it is irreducible. Thus, $g\equiv x+1, h\equiv x^{p-1} - x^{p-2} + \ldots + 1\mod p$. Since the degree of $h$ is at least $p-1$, the degree of $g$ is $1$, so $g$ has a rational root, which also means $f$ has a rational root, a contradiction. Thus, $f$ is irreducible.
18.08.2022 00:31
Eyed wrote: The answer is when $k, l$ are same parity. Clearly if they are different parity, then $x + 1$ is a factor. Let $f(x) = x^{p} + px^{l} + px^{k} + 1$, where $k, l$ are the same parity. By the rational root theorem, since $f(\pm1)\neq 0$, this means $f$ has no rational roots. Assume $f = g\cdot h$ for nonconstant polynomials $g, h$. Take $\mod p$ to get $g\cdot h\equiv x^{p} + 1 = (x+1)(x^{p-1} - x^{p-2} + \ldots + 1)$. Observe that $\Phi_{2p} = (x^{p-1} - x^{p-2} + \ldots + 1)$, so it is irreducible. Thus, $g\equiv x+1, h\equiv x^{p-1} - x^{p-2} + \ldots + 1\mod p$. Since the degree of $h$ is at least $p-1$, the degree of $g$ is $1$, so $g$ has a rational root, which also means $f$ has a rational root, a contradiction. Thus, $f$ is irreducible. $\Phi_{2p} = (x^{p-1} - x^{p-2} + \ldots + 1)$ is irreducible in $\mathbb{Z}$, but not in $\mathbb{Z}_p$.
25.06.2023 08:21
Valentin Vornicu wrote: Let $p$ a prime number, $p\geq 5$. Find the number of polynomials of the form \[ x^p + px^k + p x^l + 1, \quad k > l, \quad k, l \in \left\{1,2,\cdots,p-1\right\}, \]which are irreducible in $\mathbb{Z}[X]$. Valentin Vornicu $\color{blue}\boxed{\textbf{Answer:}2{\frac{p-1}{2} \choose 2}}$ $\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ $$P(x)=x^p+px^k+px^{\ell}+1$$By Rational Root Theorem: $P(x)$ is reducible in $Z[x]$ if $P$ has a root $x_1\in\mathbb{Z}$ such that $x_1|1$ $$\Rightarrow x_1=1 \text{ or }-1$$$\color{red}\boxed{\textbf{If } x_1=1:}$ $\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow 1+p+p+1=0(\Rightarrow \Leftarrow)$$$\color{red}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{If } x_1=-1:}$ $\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow (-1)^p+(-1)^k+(-1)^{\ell}+1=0$$$$\Rightarrow (-1)^k+(-1)^{\ell}=0$$$$\Rightarrow k\not\equiv \ell \pmod{2}$$But we want the complement, that is, the irreducibles in $Z[x]$, counting we get: $$2 {\frac{p-1}{2} \choose 2} _\blacksquare$$$\color{red}\rule{24cm}{0.3pt}$ $\color{blue}\rule{24cm}{0.3pt}$
13.10.2023 18:14
The idea is to look at this polynomial $f$ in $\mathbb F_p$. Suppose that $f=gh$. Note that $$f \equiv x^p + 1 \equiv (x+1)^p,$$so in particular $g$ and $h$ mod $p$ are both powers of $x+1$. Now, assume for the sake of contradiction that $f(-1) \neq 0$. Then $f(-1) = 2p$, and hence $$p^2 \mid g(-1)h(-1) = 2p$$which is an obvious contradiction. So $k$ and $\ell$ must be the same parity, and the number of such pairs is then $\frac{(p-1)(p-3)}4$.