1 Introduction
Prime numbers and irreducible polynomials having integer coefficients are intimately connected and their coherence has been an influential theme in the development of number theory and geometry. For example, a century old open problem known as Buniakowski’s conjecture (1854) states that if
$f\in \Bbb {Z}[x]$
is an irreducible polynomial such that the integers in the set
$f(\Bbb {N})$
have no common divisor other than 1, then f takes prime values infinitely often. Conversely, if f takes prime values for infinitely many values of n, then f must be irreducible. Otherwise, if
$f(x)=g(x)h(x),$
where g and h are nonconstant polynomials in
$\Bbb {Z}[x]$
, then
$f(n)=g(n)h(n)$
with
$f(n)$
prime infinitely often yields either
$g(n)=\pm 1$
or
$h(n)=\pm 1$
infinitely often. This is absurd, since a polynomial can take the values
$\pm 1$
at most finitely many times. Thus, the converse of Buniakowski’s conjecture is true. Here, primality is used to deduce irreducibility of a polynomial.
As a strong converse of Buniakowski’s conjecture, Ram Murty in [Reference Ram Murty2] deduced irreducibility of a polynomial
$f\in \Bbb {Z}[x]$
assuming
$f(n)$
to be prime for a sufficiently large n. Girstmair in [Reference Girstmair1] generalised Ram Murty’s criterion by showing that f is irreducible over
$\Bbb {Q}$
if f is primitive and
$f(n)=\pm pd$
for a sufficiently large n, where p is a prime not dividing d. Recall that a polynomial
$f\in \Bbb {Z}[x]$
is primitive if the greatest common divisor of its coefficients is 1. We further generalise Girstmair’s criterion to the case when a primitive polynomial f takes a composite value, say
$f(n)=\pm p^kd$
for a sufficiently large n, where p is a prime not dividing d and k is a positive integer.
Let
$f'(x)$
denote the formal derivative of f with respect to x. We now assert the following result.
Theorem 1.1. Let
$f=a_0+a_1 x+\cdots +a_mx^m\in \Bbb {Z}[x]$
be primitive and let
$H=\max _{0\leq i\leq m-1}\{|a_i/a_m|\}$
. If there exist natural numbers n, d, k and a prime
$p\nmid d$
such that
$n\geq H+d+1$
,
$f(n)=\pm p^k d$
and, in case
$k>1$
, also
$p\nmid f'(n)$
, then f is irreducible in
$\Bbb {Z}[x]$
.
In the following two examples, each of m, d, k is a positive integer and p is a prime.
Example 1.2. Consider the polynomials defined by
$$ \begin{align*} X(x)=p^k-x\pm (p^k d) x^m \end{align*} $$
for which
$H\leq 1$
and
$X(p^k)=\pm p^{k(1+m)}d$
. Also,
$X'(p^k)\equiv -1\pmod p$
, which shows that
$p\nmid X'(p^k)$
. Now, if we take
$n=p^k\geq d+2>H+1+d$
, then the irreducibility of X is immediate from Theorem 1.1.
Example 1.3. Let
$p\geq 5$
be a prime. The polynomial
$$ \begin{align*} Y(x)=(p-1)(1+x+x^2+\cdots+x^m)+1 \end{align*} $$
satisfies
$Y(p)=p^{m+1}$
and
$H=p/(p-1)<2$
. If we take
$n=p$
, then
$n>H+2$
. As
$Y'(p)\equiv (p-1)\pmod p$
, it follows that
$p\nmid Y'(p)$
. So, by Theorem 1.1, the polynomial Y is irreducible in
$\mathbb {Z}[x]$
.
2 Proof of Theorem 1.1
By definition of H, we have
$|a_i|\leq |a_m| H$
for all
$i=0, 1,\ldots ,m-1$
. Using this inequality,
$$ \begin{align*} |f(x)| \geq |a_m||x|^m-\sum_{i=0}^{m-1}|a_i||x|^{i}\geq |a_m|\bigg(|x|^m-H\sum_{i=0}^{m-1}|x|^{i}\bigg) =|a_m|\bigg(|x|^m-H\frac{|x|^m-1}{|x|-1}\bigg). \end{align*} $$
If a complex number x satisfies
$|x|\geq H+1 (>1)$
, then
$-({H}/{(|x|-1)})\geq -1$
and so
$$ \begin{align*} \bigg(|x|^m-H\frac{|x|^m-1}{|x|-1}\bigg) \geq (|x|^m-(|x|^m-1))=1. \end{align*} $$
Consequently,
$|f(x)|\geq |a_m|\times 1=|a_m|>0$
, which shows that
$f(x)\neq 0$
for all complex numbers x with
$|x|\geq (H+1)$
. Thus, every zero
$\theta $
of f must satisfy
$|\theta |<(H+1)$
.
Now suppose on the contrary that
$f(x)=f_1(x)f_2(x)$
, where
$f_1$
and
$f_2$
are nonconstant polynomials in
$\Bbb {Z}[x]$
. Since
$f(n)=f_1(n)f_2(n)=\pm p^k d$
, at least one of the factors
$f_1(n)$
or
$f_2(n)$
is divisible by p. Assume that
$p\mid f_2(n)$
.
First, consider the case when
$p\nmid f_1(n)$
. Since
$|f_1(n)||f_2(n)|=p^k d$
, it follows that
$p^k$
divides
$f_2(n)$
, so that
$p^k\leq |f_2(n)|$
. Moreover,
$|f_1(n)|$
must divide d, which yields
$|f_1(n)|\leq d$
. Further, if
$\theta _1, \ldots ,\theta _{\deg {f_1}}$
denote the zeros of
$f_1$
and
$\alpha \neq 0$
the leading coefficient of
$f_1$
, then we may express
$f_1$
as
$$ \begin{align} f_1(x)=\alpha(x-\theta_1)\cdots(x-\theta_{\deg{f_1}}). \end{align} $$
Note that for each
$i=1,\ldots ,\deg {f_1}$
,
$$ \begin{align*} |n-\theta_i|\geq n-|\theta_i|>H+d+1-(H+1)=d. \end{align*} $$
In view of (2.1), this gives
$|f_1(n)|>d^{\deg {f_1}}\geq d$
, which is a contradiction.
Now consider the case when p divides
$f_1(n)$
, so that
$k\geq 2$
. By the product rule of derivatives,
$$ \begin{align*} f'(n)=f_1'(n)f_2(n)+f_1(n)f_2'(n), \end{align*} $$
where p divides
$f_1(n)$
and p divides
$f_2(n)$
. Consequently, p divides
$f'(n)$
, which contradicts the hypothesis and the theorem follows.
Remark 2.1. The Theorem in [Reference Girstmair1] is the special case
$k=1$
of Theorem 1.1. The advantage of Theorem 1.1 is that when both Girstmair’s criterion and Theorem 1.1 apply, Girstmair’s criterion may require factorisation of much larger numbers. For example, for the polynomial
$$ \begin{align*} U(x)=7 + 5 x - 16 x^2 + 6 x^3 + 2 x^4 + 7 x^5 + x^6 + 6 x^7 + 2 x^8 + 8 x^9 + 4 x^{10}, \end{align*} $$
$$\begin{align*}H=4, U(10)=48261724457=137^5, d=1,137\nmid U'(10)= 47402959485.\end{align*}$$
Thus, in view of Theorem 1.1, U is irreducible in
$\Bbb {Z}[x]$
. The smallest value of n for which
$U(n)$
satisfies the hypotheses of the Theorem in [Reference Girstmair1] is
$n=50$
, where
$$\begin{align*}U(50)=406332830325710257,\end{align*}$$
an 18-digit prime.
Now consider the polynomial
$$ \begin{align*} V(x)=9 -x +18 x^8 \end{align*} $$
for which
$H<1$
,
$V(9)=3^{18}\times 2$
,
$V'(9)\equiv -1\pmod 3$
,
$9>H+1+2$
. By Theorem 1.1, U is irreducible. Here, the smallest value of n for which Theorem 1.1 applies is nine, whereas the smallest value of n for which V takes a prime value is
$26$
with
$V(26)=3758887162351$
, a large prime.
3 A generalisation of Theorem 1.1
In this section, we prove a generalisation of Theorem 1.1. In what follows, let
$f^{(0)}(x)=f(x)$
and, for each natural number j, let
$f^{(j)}(x)$
denote the jth derivative of f with respect to x.
Theorem 3.1. Let
$f=a_0+a_1 x+\cdots +a_mx^m\in \Bbb {Z}[x]$
be primitive and let
$H=\max _{0\leq i\leq m-1}\{|a_i/a_m|\}$
. If there exist natural numbers n, d, k,
$j\leq m$
and a prime
$p\nmid d$
such that
$n\geq H+d+1$
,
$f(n)=\pm p^k d$
,
$\gcd (k,j)=1$
,
$p^k \mid {f^{(i)}(n)}/{i!}$
for each index
$i=0, 1, \ldots ,j-1$
and, in case
$k>1$
, also
$p\nmid {f^{(j)}(n)}/{j!}$
, then f is irreducible in
$\Bbb {Z}[x]$
.
The proof of Theorem 3.1 rests on the following result proved in [Reference Singh and Kumar3, Lemma 3].
Lemma 3.2 (Singh and Kumar [Reference Singh and Kumar3])
Let
$f=a_0+ a_{1}x+\cdots +a_m x^m$
and let
$f_1$
and
$f_2$
be nonconstant polynomials in
$\Bbb {Z}[x]$
such that
$f(x)=f_1(x)f_2(x)$
. Suppose that there exist a prime p and coprime natural numbers
$k\geq 2$
and
$j\leq m$
satisfying
$p^k\mid \gcd (a_0,a_1,\ldots ,a_{j-1})$
and
$p^{k+1}\nmid a_0$
. If
$p\mid f_1(0)$
and
$p\mid f_2(0)$
, then
$p\mid a_j$
.
Proof of Theorem 3.1
Let
$s_i={f^{(i)}(n)}/{i!}$
for
$i=0,\ldots ,m$
and define
$$ \begin{align} g(x)=f(x+n)=s_0+s_1x+\cdots+s_mx^m. \end{align} $$
It will be enough to prove that g is irreducible. By hypothesis,
$p \mid s_i$
for
${i=0,\ldots ,j-1}$
. Assume to the contrary that
$g(x)=g_1(x)g_2(x)$
, where
$g_1$
and
$g_2$
are nonconstant polynomials in
$\Bbb {Z}[x]$
. Observe that
$$ \begin{align} g(0)=f(n)=\pm p^k d=g_1(0)g_2(0). \end{align} $$
This shows that p divides one of the factors
$g_1(0)$
or
$g_2(0)$
. Assume that
$p\mid g_2(0)$
.
If
$p\mid g_1(0)$
, then
$k>1$
and Lemma 3.2 applied to g yields
$p\mid s_j$
. This contradicts the hypothesis.
Now suppose that
$p\nmid g_1(0)$
. In view of (3.2),
$g_1(0)$
divides d and so
$|g_1(0)|\leq d$
. If
$\theta _1$
,
$\ldots $
,
$\theta _{\deg {g_1}}$
are the zeros of
$g_1$
and
$\alpha \neq 0$
is the leading coefficient of
$g_1$
, then
$g_1(x)=\alpha (x-\theta _1)\cdots (x-\theta _{\deg {g_1}})$
. In view of (3.1),
$f(\theta _i+n)=0$
for each i. Arguing as in the proof of Theorem 1.1,
$$ \begin{align*} |\theta_i|\geq n-|\theta_i+n|>H+d+1-(H+1)=d, \end{align*} $$
which gives
$|g_1(0)|=|\alpha ||x-\theta _1|\cdots |x-\theta _{\deg {g_1}}|>d^{\deg {g_1}}\geq d$
, leading to a contradiction as before.
Example 3.3. Let k, d and p be positive integers such that k is odd, p is a prime number coprime to d and
$2+d<p<k-1$
. Then the polynomial
$$ \begin{align*} Z(x) = (x-p)^2+(p^{k-p}d) x^p \end{align*} $$
satisfies
$Z(p)=p^kd=Z'(p)$
and
$Z''(p)/2!=1+p^{k-1}d(p-1)/2\equiv 1 \pmod p$
, so that
$p\nmid Z''(p)/2!$
. Since
$p<k-1$
, we also have
$H=p^2/(p^{k-p}d)\leq 1$
and consequently
$H+1+d\leq 2+d<p$
. So, the polynomial Z satisfies the hypothesis of Theorem 3.1 for
$n=p$
,
$j=2$
and any
$k>p+1$
. Hence, Z is irreducible in
$\mathbb {Z}[x]$
.
Example 3.4. More generally, let d, k, j be positive integers such that
$\gcd (k,j)=1$
and let p be a prime with
$p\nmid d$
,
$(2+d)\leq j<p$
and
$j+p^{{\kern1pt}j-1}\leq k$
. Then the polynomial
$$ \begin{align*} Z_j(x)= (x-p)^{{\kern1pt}j}+(p^{k-p^{{\kern1pt}j-1}}d) x^{p^{{\kern1pt}j-1}} \end{align*} $$
satisfies
$Z_j(p)=p^kd$
and
$$ \begin{align*} Z_j^{(i)}(p)/i!= p^{k+j-1-i}(p^{{\kern1pt}j-1}-1)(p^{{\kern1pt}j-1}-2)\cdots (p^{{\kern1pt}j-1}-i) \quad\mbox{for} \ i=1,\ldots,j-1, \end{align*} $$
which shows that
$p^k\mid (Z^{(i)}(p)/i!)$
for
$i = 1,\ldots ,j-1$
. We also have
$$ \begin{align*} Z_j^{(j)}(p)/j!=1+ p^{k-1}(p^{{\kern1pt}j-1}-1)(p^{{\kern1pt}j-1}-2)\cdots (p^{{\kern1pt}j-1}-j)\equiv 1\pmod p, \end{align*} $$
which shows that
$p\nmid (Z_j^{(j)}(p)/j!)$
. Since
$j\leq k-p^{{\kern1pt}j-1}$
, we have
$H=p^{{\kern1pt}j}/(p^{k-p^{{\kern1pt}j-1}}d)\leq 1$
and so
$H+1+d\leq 2+d\leq j<p$
. Applying Theorem 3.1 to
$Z_j$
with
$n=p$
shows that the polynomial
$Z_j$
is irreducible in
$\mathbb {Z}[x]$
.
Acknowledgement
The authors are indebted to the anonymous referee for valuable suggestions to improve the article.
