Prove that, for all integers $a, b$, there exists a positive integer $n$, such that the number $n^2+an+b$ has at least $2018$ different prime divisors.
Problem
Source: Turkey Team Selection Test 2018 P1
Tags: quadratics, polynomial, number theory, prime numbers, C.R.T
27.03.2018 13:52
Let $P(x)=x^2+ax+b$. Suppose that $P(n)$ has $m$ prime divisors. Note that $P(n)\mid P(n+kP(n))$ for all $k\in\mathbb N$. Since $P(n+kP(n))$ is a nonconstant polynomial in $k$, by Schur, we can find a prime $p$ and a positive integer $k_0$ such that $p\nmid P(n)$ but $p\mid P(n+k_0P(n))$. It follows that $P(n+k_0P(n))$ has at least $m+1$ prime divisors. In this way it's easy to see that the number of prime divisors of $P(n)$ is unbounded.
27.03.2018 14:10
Here's my solution which I thought of in a hurry. Please point out if there are mistakes. We will prove there are infinitely many primes $p$, such that the equation $n^2 + an + b \equiv 0 \ (mod \ p )$ has a solution. This gives the desired result by CRT. If $a$ is even, denote $a = 2c$ $n^2 + an + b = n^2 + 2cn + b = (n + c)^2 + d$ for some constant $d$. So we want $(n+c)^2 \equiv e \ (mod \ p)$ for some constant $e$. Of course, $(n + c)^2$ goes through all quadratic residues modulo $p$. It's well known that for any $e \in \mathbb{Z}$ there are infinitely many $p$ such that $e$ is a quadratic residue modulo $p$ (Proof outline: we pick $p \equiv 1 \ (mod \ 4e)$ (possible by Dirichlet), and use quadratic reciprocity for each prime power of $e$ separately, as we can break the Legendre symbol $\Big ( \frac{e}{p} \Big )$ into prime powers, and eliminate exponents greater than $1$ due to Euler's criterion). Thus, this congruence equation has a solution for infinitely many primes $p$. If $a$ is odd, we have $n^2 + an + b \equiv n^2 + (p - a)n + b \ (mod \ p )$. Again, we can complete the square as $p - a$ is even for all $p \neq 2$. So the case of $a$ being odd is okay too. The result follows.
27.03.2018 17:27
Am i missing something? Let $P(n)=n^2+an+b$ Thus P is non-constant,from Schur we know that there exist distinct primes $p_1,p_2,...,p_k$ such as $p_i \mid P(n_i)$ for all $i=1,k$ Take $x=n_i( mod$ $p_i)$(the existence is obvious from CRT) Now $P(x)$ has $k$ distinct prime divisors.Take $k=2018$
27.03.2018 21:33
den_thewhitelion wrote: Am i missing something? Let $P(n)=n^2+an+b$ Thus P is non-constant,from Schur we know that there exist distinct primes $p_1,p_2,...,p_k$ such as $p_i \mid P(n_i)$ for all $i=1,k$ Take $x=n_i( mod$ $p_i)$(the existence is obvious from CRT) Now $P(x)$ has $k$ distinct prime divisors.Take $k=2018$ You are absolutely correct and concise,my friend!!!
12.04.2018 05:19
Standard Schur + CRT
14.09.2018 21:42
Without Schur.
22.04.2021 13:13
Let $P(x)=x^2+ax+b$ and for a positive integer $n$, assume $P(n)$ has $r$ prime divisor. We will show that one can find a positive integer $m$ such that $P(m)$ has at least $r+1$ prime divisors. $P(n)|P(m)\Leftrightarrow n^2+an+b|m^2+am+b=(m^2-n^2+am-an)+(n^2+an+b)=(m-n)(m+n+a)+(n^2+an+b)$. Thus, if $n^2+an+b|m-n$ then $P(n)|P(m)$. Take $m$ such that $m-n=k(n^2+an+b)$ for a positive integer $k$ ($m=kn^2+kan+n+kb$). Then, $P(m)=P(n).(kn^2+kan+2n+bk+a+k)$. Let $Q(k)=kn^2+kan+2n+bk+a+k$. Since $P(n)$ has finite prime divisors, we can find a prime number $p$ such that $p\nmid P(n)$ and $p>2n+a$. Take $k=p-2n-a$. Let $(n^2+an+b,kn^2+kan+2n+bk+a+k)=d$. Then, $d|(kn^2+kan+2n+bk+a+k)-k(kn^2+kan+2n+bk+a+k)=2n+a+k=p$. So $d=1$ or $d=p$. But we said $p\nmid P(n)$. Hence, $d=1$. $Q(k)>1$ so it has at least $1$ prime divisor, say $q$, and $q\nmid P(n)$. In conclusion, $P(m)=P(n).Q(k)$ has at least $r+1$ prime divisors.
11.10.2021 18:27
23.07.2023 09:34
BarisKoyuncu wrote: Let $(n^2+an+b,kn^2+kan+2n+bk+a+k)=d$. Then, $d|(kn^2+kan+2n+bk+a+k)-k(kn^2+kan+2n+bk+a+k)=2n+a+k=p$. So $d=1$ or $d=p$. But we said $p\nmid P(n)$. Hence, $d=1$. $Q(k)>1$ so it has at least $1$ prime divisor, say $q$, and $q\nmid P(n)$. In conclusion, $P(m)=P(n).Q(k)$ has at least $r+1$ prime divisors. you should edit this part that shows $d$ is a divisor of $p$ because you wrote $d|(kn^2+kan+2n+bk+a+k)-k(kn^2+kan+2n+bk+a+k)$ but it has to be$d|(kn^2+kan+2n+bk+a+k)-k(n^2+an+b,kn^2)$.