Let $P(n)$ be a quadratic trinomial with integer coefficients. For each positive integer $n$, the number $P(n)$ has a proper divisor $d_{n}$ (i.e. $1 < d_{n} < P(n)$), such that the sequence $d_{1},d_{2}, d_{3},\ldots$ is increasing. Prove that either:
i) $P(n)$ is the product of two linear polynomials with integer coefficients, or
ii) all the values of $P(n)$, for positive integers $n$, are divisible by the same integer $m>1$.

This Russian problem was posted some time ago at math.SE. A bounty was placed on it, but no solution was received. Any suggestion is appreciated. Thanks in advance.


Assume the contrary.

At first, $P(n+2)-3P(n+1)+3P(n)-P(n-1)=0$, thus if the same number $m>1$ divides three consecutive values of $P$, it divides all values of $P$ and case ii) takes place.

Denote $P(n)=d_na_n$, $\ell(n)=P(n+1)-P(n)$ is a linear function. If $\ell(x)$ divides $P(x)$ as a polynomial, case i) takes place, if not, then $a(x)P(x)+b(x)\ell(x)=C\ne 0$ for some $a(x),b(x)\in \mathbb{Z}[x]$, hence ${\rm gcd}\,(P(n),\ell(n))\leq C$. Thus equality $d_{n+1}=d_n$ implies $d_n\leq C$, so, this may hold only for finitely many $n$ (otherwise $d_n=m$ for large enough $m$ and case ii) takes place.)

Now assume that $d_n\geq 2\ell(20n)$ (and $n$ is large enough). Then $a_{k+1}\leq P(k+1)/d_k=a_k+\ell(k)/d_k<a_k+1$ for $k=n,n+1,\dots,20n$. Thus either $a_k$ takes the same value three times in a row, see above why it implies case ii), or $a_{k+2}\leq a_k-1$ for $k=n,\dots,20n$. That is, $0<a_{20n}<a_n-9n$, i.e. $a_n>9n$, $P(n)=a_nd_n>9n\cdot 2\ell(20 n)$, this is false for large enough $n$.

So, $d_n=O(n)$ (and of course $d_n=\Omega(n)$ as $d_n$ strictly increases from some place; $a_n=P(n)/d_n$ tends to infinity, thus $a_{n+1}\ne a_n$ for large $n$ (if $a_n=a_{n+1}=m$, $m$ divides above constant $C$.) For some $A>0$ there is a set $U$ of positive integers with positive upper density so that $d_{n+1}=d_n+A$ for $n\in U$. We have $a_{n+1}-a_n=P(n+1)/(d_n+A)-P(n)/d_n=O(1)$. It means that $a_{n+1}-a_n=A$ for some constant $A$ for all $n$ from some smaller set $ \tilde{U}\subset U$ of positive density.

Well, this is quadratic equation for $d_n$ if we fix $n$: $\ell(n)=Ad_n+DP(n)/d_n+AD$, $Ad_n^2-(\ell(n)-AD)d_n+DP(n)=0$. Its discriminant $(\ell(n)-AD)^2-4ADP(n)$ is (at most) quadratic trinomial in $n$. Three cases:

1) discriminant is a square of a linear function. Then $d_n$ is linear in $n$, and since $P(n)$ is divisible by $d_n$ for infinitely many $n$ we see that $P$ factorizes into two linear factors.

2) discriminant is a non-square quadratic trinomial. It may be a perfect square, but quite rarely. That is, for fixed $A,D$ only a null density of $n$ are ok (by Pell's type equation and blah-blah.)

3) discriminant is a linear function in $n$. The same as 2), but without Pell type argument.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.