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 $P(n)$ is the product of two linear polynomials with integer coefficients or all the values of $P(n)$, for positive integers $n$, are divisible by the same integer $m>1$.
Problem
Source: XVIII Tuymaada Mathematical Olympiad (2011), Senior Level
Tags: quadratics, algebra, polynomial, Analytic Number Theory, Integer sequence, Integer Polynomial
angiland
18.05.2016 18:22
Suppose $P(n)$ is irreducible, then up to a linear transformation $P(n) = n^2 - b$ with $b$ not a perfect square. Let $Q$ be the set of primes $q$ that do not divide any $P(n)$. It follows by quadratic reciprocity and Dirichlet's theorem that $Q$ has relative density $\frac{1}{2}$ among all primes (a very special case of Chebotarev density theorem). Consider a positive integer $d$ that divides some $P(n)$, then $d$ cannot contain any prime factor in $Q$. This means the number of such $d \leq x$ is $O\left(\frac{x}{\sqrt{\log{x}}}\right)$. Therefore, $d_n > cn\sqrt{\log{n}}$ for some positive constant $c$ and all large $n$. Now let $e_n = \frac{P(n)}{d_n}$, then each $e_n$ is a positive integer greater than $1$. Moreover, for large $n$ we have $$(e_n+1) d_{n+1} > (e_n+1)d_n = P(n) + d_n > P(n) + cn\sqrt{\log{n}} > P(n+1).$$It follows that $e_{n+1} \leq e_{n}$. But then the sequence $e_n$ must be a constant $k$ for all large $n$. That implies $k | P(n)$ for all large $n$ and thus for all $n$.
fattypiggy123
24.05.2016 13:07
Here's a more elementary solution but far longer... First let $P(n) = c_nd_n$. Then we can show there exists a constant $m$ such that if $d_n > mn$ then we must have $c_n \geq c_{n+1}$. This is easy as else we must have $\frac{P(n+1)}{d_n} \geq \frac{P(n)}{d_n} + 1$ which is not possible if $m$ is large enough depending on the coefficients of $P$. Furthermore, this implies that $\frac{P(n+1)}{d_{n+1}} \leq \frac{P(n)}{d_n} $ which gives us $d_{n+1} \geq \frac{P(n+1)}{P(n)} d_n$ which tells us that $d_{n+1} > m(n+1)$ if $n$ is large enough. Hence if $n$ is large enough and we have $d_n > mn$, then by induction we can get $d_{n+k} > m(n+k)$ and that $c_{n+k} \leq c_{n+k-1}$. Hence $c_n$ will become a non-increasing sequence of positive integers and hence eventually constant, giving us the condition that $P(n)$ will be divisible by the same integer $m$ for all $n$. Hence we can assume that for large enough $n$, there is a constant $m$ such that $d_n < mn$. Now let $j_n = d_{n+1} - d_n, k_n = c_{n+1} - c_n$. Now since $j_n$ is always positive, at most $\frac{1}{2}$ of them can be larger than $2m$ else we will end up with $d_n > mn$. Hence by pigeonhole, we can have a positive density of them to be equal to some value, say $j$. Now since $k_n$ is clearly bounded above as $d_n$ is increasing, we can repeat the same argument to have a positive density of them among those with $j_n = j$ to be equal to the same value. Let this be value be $k$. Now we have that $P(n+1) = (d_n + j)(c_n + k)$ for a positive density of $n$. Consider the polynomial $(x - k d_n)(x - jc_n)$ which expands into $x^2 - (kd_n - jc_n)x + kj d_n c_n = x^2 - (P(n+1) - P(n) - kj)x + kjP(n) = x^2 + r(n)x + s(n)$ where $r$ is a linear polynomial in $n$ and $s$ a quadratic polynomial. This polynomial has integer roots for a positive density of $n$ and hence its discriminant must have be a perfect square for those $n$. This discriminant is $r(n)^2 - 4s(n) = an^2 + bn + c$ for some integers $a,b,c$. If $a$ is not a perfect square, then the equation $an^2 + bn + c = y^2$ can be rewritten into $a(n + \frac{b}{2a})^2 + c - \frac{b^2}{4a} = y^2$ which is equivalent to $a(2an + b)^2 + 4a^2c - ab^2 = (2ay)^2$. Now, this equation is a generalized Pell's equation and it is known that the solutions of it will grow in size exponentially as they are generated by a finite numbers of units. Hence it is impossible for it to have solutions for a positive density of naturals as it grows too fast. hence the leading coefficient must be a square and by completing the square, it is easy to see that the discriminant must be a perfect square for all $n$. Now, the integer roots of $x^2 + r(n)x + s(n)$ can be seen to grow linearly since the square root of the discriminant will be a linear function and hence it is of the form $(x - (an + b))(x - (cn+d))$ for some integers $a,b,c,d$. Hence we get $kjP(n) = r(n) = (an+b)(cn+d)$. It is then easy to conclude that $P(n)$ is the product of two linear polynomials with integer coefficients.
anantmudgal09
22.09.2016 13:18
I solve this for the case when $P(X)=X^2-a$. For other forms (which are essentially linear transformations) I think the same argument can be extended, but since I have not gone into those details I am not really sure. Any help is appreciated!
Let $a$ be a natural number that is not a perfect square. Then there exists infinitely many prime numbers $p$ such that $a$ is a quadratic residue modulo $p$.
Proof: By Euler's result $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\cdot \left(\frac{b}{p}\right)$ and so we may assume that $a$ is a square-free number. Write $a=2^e\cdot p_1\cdot \dots \cdot p_k$ where $p_i \ge 3$ are primes and $e \in \{0,1\}$. Note that the product we have taken can be empty, in which case, it shall be assumed to be equal to $1$. If $e=0$, set $p \equiv 1 (\bmod \, 4p_1\cdot \dots \cdot p_k)$ and since $$1=\left(\frac{p}{p_i}\right)=(-1)^{\frac{p-1}{2}\cdot \frac{p_i-1}{2}}\cdot \left(\frac{p_i}{p}\right)=\left(\frac{p_i}{p}\right)$$we see that $a$ is a quadratic residue modulo $p$. If $e=1$, set $p \equiv 1 (\bmod \, 8p_1\cdot \dots \cdot p_k)$. The relations with $p_1,\dots,p_k$ remain unchanged and $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ so we still get that $a$ is a quadratic residue modulo $p$. In both the cases, the existence of infinitely many such prime numbers is assured by successively applying the Chinese Remainder Theorem and the Dirichlet's theorem on distribution of primes in an arithmetic progression.
Suppose that $P$ is not reducible in $\mathbb{Z}$. By an appropriate scaling (or linear transformation), we may assume that $P(n)=n^2-a$ where $a$ is not a perfect square. We explore two natural possibilities:
Case 1. If the sequence $(d_n)_{n \ge 1}$ is bounded above.
The sequence being increasing, the assumption implies that it is eventually constant. In this case, let us suppose $d_n=d$ for all sufficiently large $n$. Then, $d \mid P(m)$ for all $m$ sufficiently large and hence $d \mid P(n)$ for all $n$.
Case 2. If the sequence $(d_n)_{n \ge 1}$ is unbounded.
We claim that $d_{n+1} \ge d_n+2$ for all sufficiently large $n$. Indeed, for $n$ sufficiently large, we can assume that $d_n > |4a-1|$ in which case we cannot have $d_n=d_{n+1}$ since $d=d_n=d_{n+1}$ implies that $d \mid \left((n+1)^2-a\right)-\left(n^2-a\right)=2n+1$ and so $d \mid (2n+1)^2-4(n^2-a)=4n+1+4a=2(2n+1)+4a-1$ and we get $d \mid 4a-1$. This is false by our assumption; $d>|4a-1|$. Hence, the $d_n \ge n-M$ for some constant $M>0$. If $d+1=d_n+1=d_{n+1}$ then setting $$n^2-a=kd$$and $$(n+1)^2-a=l(d+1)$$gives that $2n+1=(l-k)d+l$. If $l \le k$ then $l \ge (2n+1)$ and we have $(n+1)^2-a \ge (2n+1)(n+1-M)$, which fails to hold for all sufficiently large $n$. If $l>k$ then $l \ge k+1$ and we have $$(n+1)^2-a \ge (k+1)(d+1)=kd+(k+d)+1=(n^2-a)+1+(k+d) \ge (n^2-a+1)+2\cdot \sqrt{n^2-a} \ge (n^2+2n+1-a)=(n+1)^2-a$$wherein the last inequality follows from the AM-GM estimate and $2(n-\sqrt{n^2-a})$ can be made arbitrarily small, the summands being integers gives this bound. In particular, we have $k+d=2n$ or $n^2-a=d(2n-d)$, i.e., $(n-d)^2=a$ which is a contradiction as $a$ is not a perfect square. Hence, we have $d_{n+1} \ge d_n+2$ for all sufficiently large $n$, say, for all $n>T$ where $T>0$ is a constant.
Note that by our lemma, we may choose a prime number $p>T^2+1$ such that $a$ is a quadratic residue modulo $p$. Let us have $p \mid j^2-a$ and replacing $j$ by $p-j$, if need be, we may suppose that $p>2j$. It also follows that $j \ge \sqrt{p-1}>T$. Suppose that $p \nmid d_j$ and we see that $\frac{j^2-a}{p}<j-T$. However, $j-T \le d_j \mid \frac{j^2-a}{p}<j-T$, a contradiction! Therefore, $p \mid d_j$ and $d_j >2j$. By the fact that $d_{n+1} \ge d_n+2$ we conclude that for all $n>j$, $d_n>2n$.
The last step (also the tricky one!) is that we consider the sequence $x_n=\frac{P(n)}{d_n}$ of positive integers. Notice the following chain of inequalities $$(x_n+1)d_{n+1}>(x_n+1)d_n=P(n)+d_n \ge P(n)+2n+1=P(n+1)=x_{n+1}d_{n+1}$$and we get that $x_{n+1} \le x_n$, which shows that the sequence $(x_n)_{n \ge j}$ converges and being an integer sequence, it is eventually constant, say, it equals $v$ for all large enough $n$. Then, $v \mid P(n)$ for all large enough $n$ and hence, for all $n \in \mathbb{N}$
angiland
22.09.2016 18:10
@anantmudgal09 The assumption $P(n) = n^2 - a$ might at first seem innocuous, but it actually helped your proof significantly, in deriving the key estimate $P(n) + d_n \geq P(n) + 2n+1 = P(n+1)$. If instead $P$ has leading coefficient $k$, then you would need $d_n > 2kn$ to carry out the same argument. In your proof that means finding a prime factor $p > 2kn$ of $P(n)$, which boils down to a strengthening of IMO 08 P3. As we know the result is true (due to Nagell), but it relies on analytic number theory. I think the essence is the same as my argument above for $d_n > cn \sqrt{\log(n)}$.