Let $f(x) = a_k x^k + a_{k-1}x^{k-1} + \cdots + a_1x + a_0 \in \mathbf{Z}[x]$ be irreducible with no common factor among $f(1), f(2), f(3), \cdots$


  • $k \geq 3$, $a_k \geq 1$


  • $k = 2$, $a_k \geq 2$

I want to show that for all $f \in \mathbf{Z}[x]$ with the aforementioned properties there exists $n_0 \in \mathbf{N}$ such that $f(n_0) > 0$ is composite with all its proper divisors $d \lvert f(n_0)$ satisfying $d > n_0$.

EDIT: For my purposes, it also suffices to show that under the above assumptions on $f \in \mathbf{Z}[x]$ there exists $n_0 \in \mathbf{N}$ such that $f(n_0)$ has at least two "disjoint" divisors both $> n_0$. In other words that there exists $n_0$ such that $f(n_0) = (n_0 + k_1)(n_0 + k_2)$ for some $k_1, k_2 \in \mathbf{N}$.


The simplest polynomial satisfying our properties is $f(x)=2x^2 + 1$. We expect to eventually find an $n_0$ such that $f(n_0) = 2n_0^2 + 1$ is composite with all proper divisors (i.e. the least prime divisor) of $f(n_0)$ exceeding $n_0$. In fact $n_0 = 2$ is such an example. $f(2) = 9 = 3^2$. Indeed, all proper divisors of $f(2)$ exceed $2$.


If $k=2$ we require $a_k \geq 2$. The reason for this is that if we take $f(x) = x^2 + 1$ there is no $n_0$ such that $f(n_0)$ is composite and all proper divisors exceed $n_0$. Indeed if $n_0^2 + 1$ is composite, since $n_0^2 + 1 < (n_0 + 1)^2$ we must have that at least one of the proper divisors $d \lvert f(n_0)$ satisfies $d < n_0+1$ i.e. $d \leq n_0$.

  • $\begingroup$ Consider $f(x)=2x^2+1$, which is clearly irreducible. Then $\gcd(f(1),f(3))=1$. But $f(4)=33$ has a prime divisor $p=3<4=n$. Or have I misunderstood your question? Similarly for $g(x)=x^3+x+1$ you have $\gcd(f(1),f(3))=1$ and $f(4)=69=3\times23$. $\endgroup$
    – Servaes
    Feb 17 at 15:47
  • $\begingroup$ @Antosha I honestly have no idea what your question might be. Voting to close as 'unclear', please give it some more thought. $\endgroup$
    – Servaes
    Feb 17 at 15:53
  • $\begingroup$ Note that the coefficients of $f(x)$ can be negative; does a negative composite output count for you? $\endgroup$ Feb 17 at 19:11
  • $\begingroup$ @GregMartin I will say no. I've added the assumption though that the leading coefficient is greater than 1 to ensure at most finitely many values of the polynomial will be negative. $\endgroup$
    – Antosha
    Feb 17 at 19:24

1 Answer 1


We prove the following, which does not solve the original question but does satisfy the conditions in the edit. I believe the original question may be very hard.

Claim. Let $f(x)$ be any polynomial with integer coefficients such that either (i) $\deg f\geq 3$ and $f$ has positive leading coefficient or (ii) $\deg f\geq 2$ and $f$ has leading coefficient at least $2$. Then there exists some positive integer $n$ and positive integers $a$ and $b$ so that $f(n)=(n+a)(n+b)$.

Proof. Pick a positive integer $a$, large enough so that

  1. $|f(-a)|>3a$, and
  2. $f(x)>(3/2)x^2$ for all $x>2a$.

We can choose such an $a$ because $f(x)$ grows at least on the order of $2|x|^2$ (possibly with lower-order terms) as $|x|\to\infty$.

Now, let $n=|f(-a)|-a$. Note that $n>2a$, by (1). In particular, $n>0$. We compute $$f(n)=f\big(|f(-a)|-a\big)\equiv f(-a)\equiv 0\pmod{|f(-a)|}.$$ As a result, we can write $$f(n)=|f(-a)|(n+b)=(n+a)(n+b)$$ for some integer $b$. In fact, we have $$f(n)>\frac 32n^2>n(n+a)$$ by (2) and then (1). So, $b>0$. This provides the desired factorization.

  • $\begingroup$ Thank you so much. This is marvelous! $\endgroup$
    – Antosha
    Feb 18 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .