# Proving for every $f \in \mathbf{Z}[x]$ (with a few conditions) there will be composite $f(n)$ with only "large" divisors

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

Suppose,

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

or,

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

Example:

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

Comment:

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

• 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$. Feb 17 at 15:47
• @Antosha I honestly have no idea what your question might be. Voting to close as 'unclear', please give it some more thought. Feb 17 at 15:53
• Note that the coefficients of $f(x)$ can be negative; does a negative composite output count for you? Feb 17 at 19:11
• @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. Feb 17 at 19:24

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.

• Thank you so much. This is marvelous! Feb 18 at 16:11