We show a more general result: let $P(x)=(x+d_1)(x+d_2)\dots(x+d_k)$ be a polynomial where wlog $d_1<d_2<\dots<d_k$ are integers. There exists some positive integer $N$ such that $P(n)$ is divisible by at least $k$ distinct primes for all $n\geq N$. Since there are exactly $8$ primes that are less than $20$, namely $2,3,5,7,11,13,17,19$, the proposed problem is a particular case of this result where $k=9$. Although my bound for $N$ is probably lousy as hell...

There are 8 primes $p_1,\ldots,p_8$ below 20. Assume the contrary that there are infinitely many numbers $a_1,a_2,\ldots$ such that $P(a_i)$ is not divisible by a prime greater than 20. So $a_i+d_j$ has only prime factors $p_1,\ldots,p_8$, for $i\ge1,1\le j\le8$. Note that $\nu_{p_k}(a_i+d_1)$ must be unbounded as $i\to\infty$ for some $k$, wlog $k=1$. If $\nu_{p_1}(a_i+d_1)>\nu_{p_1}(d_1-d_2)$, then $\nu_{p_1}(a_i+d_2)=\nu_{p_1}(a_i+d_1)$ is bounded. Similarly, $\nu_{p_1}(a_i+d_j)$ is bounded for $j\ge2$. There are infinitely such $a_i$. In fact we can assume all $a_i$s have such property, otherwise just remove those without this property. Analogously, wlog $\nu_{p_2}(a_i+d_2)$ is unbounded. Then $\nu_{p_2}(a_i+d_j)$ is bounded for infinitely $a_i$ and $j\ge3$. Again, assume it's true for all $a_i$. Continuing this way, we'll end up concluding that $\nu_{p_k}(a_i+d_9)$ is bounded for $1\le k\le8$ as $i\to \infty$, which is evidently impossible.

I'd like to note something : by Kobayashi's Theorem, we can show in general for a positive integer $d$ and fixed integers $a \neq b$, $(x+a)(x+b)$ has a prime divisor greater than $d$ for all sufficiently large $x$. Proof: Suppose not. Let $P$ be the set of primes less than $d$. Suppose there is an infinite set of integers, $n_1 < n_2 < ...$, such that all the prime divisors of $n_i + a$ and $n_i + b$ are in $P$ for each positive integer $i$. Then the sequence $x_k = n_k + a$ has only finitely many prime divisors. By Kobayashi's Theorem, the sequence $x_k + (b-a)$ has infinitely many prime divisors then. But this is a contradiction, hence there are only finitely many such $n_i$ and the result follows.

Let $P$ be the product of all primes below $20$ and let $N=P^s+max{|d_{i}|}$. Now if for $x\ge N$ the polynomial isn't divisble by a prime larger than $20$ then let $f(x+d_{i})$ be the prime number dividing $x+d_{i}$ with the biggest exponnent denoted by $d(x+d_{i})$.Now note by definition of $N$ that $d(x+d_{i})\ge s$ but since there are $8$ primes below $20$ then there are some $i,j$ such that $f(x+d_{i})=f(x+d_{j})=p$ now we have that $p^s|d_{i}-d_{j}$ but clearly we can choose a big enough $s$ such that this is never true.

jgnr wrote: Note that \nu_{p_k}(a_i+d_1) must be unbounded as i\to\infty for some k, wlog k=1. If \nu_{p_1}(a_i+d_1)>\nu_{p_1}(d_1-d_2), then \nu_{p_1}(a_i+d_2)=\nu_{p_1}(a_i+d_1) is bounded. Similarly, \nu_{p_1}(a_i+d_j) is bounded for j\ge2. There are infinitely such a_i. In fact we can assume all a_is have such property, otherwise just remove those without this property. I do not understand how do you conclude that for every $p_i$ there are infinetly many $a_i$ such that $\nu_{p_i}(a_i+d_i)$ is unbounded. Can you explain this further?

orl wrote: Consider a polynomial $P(x) = \prod^9_{j=1}(x+d_j),$ where $d_1, d_2, \ldots d_9$ are nine distinct integers. Prove that there exists an integer $N,$ such that for all integers $x \geq N$ the number $P(x)$ is divisible by a prime number greater than 20. Proposed by Luxembourg Assume otherwise; then we can find a sequence $x_1<x_2<\dots$ with $P(x_i)$ having prime factors among $\{2,3,5,7,11,13,17,19\}$. Translate $x$, if necessary, to assume $d_i>0$ for all $i \ge 1$. Pick $n$ large and look at the maximal prime power $p_n^{\alpha_n} \mid P(x_n)$. Let $v_{p_n}(x_n+d_i)=e_i$ for $1 \le i \le 9$. Suppose $e_9$ is the largest among them. Observe that $\gcd(x_n+d_i, x_n+d_j)<|d_i-d_j|$ hence it is possible to find a constant $M>0$ with $e_i<M$ for all $1 \le i \le 8$. Hence $e_9>\alpha_n-8M$. Consequently, we have $$x_n+d_9 \ge p_n^{e_n}>\left(\frac{1}{20}\right)^{8M}p_n^{\alpha_n}>\left(\frac{1}{20}\right)^{8M}\sqrt[8]{\prod^9_{i=1}(x_n+d_i)}$$yielding a contradiction as $x_n \rightarrow \infty$. $\blacksquare$

Assume for the sake of contradiction, there exist infinitely many $x$ such that $P(x)$ is only divisible by primes less than $20$. For each number $x+d_i$, let $p_i$ denote the prime number such that $p_i \mid\ x+d_i$ and $v_{p_i}(x+d_i)$ is maximum among all other primes dividing $x+d_i$. Call such a prime number a perfect prime divisor. Note that there are $8$ primes less than $20$. Since there are $9$ factors and each has a perfect prime divisor, by the pigeonhole principle, there are two numbers $x_i$ and $x_j$ with the same perfect prime divisor. Let $p_i^{a_i} \parallel x+d_i$ and $p_j^{a_j} \parallel x+d_j$. WLOG, $a_i \geq a_j$. Then, $p^{a_j} \mid d_i - d_j $. Choose $x$ large enough such that $p^{a_j} > |d_i - d_j|$. This imples $d_i = d_j$. Contradiction. Lastly, there exist finitely many $x$ such that $P(x)$ is divisible by primes less than $20$. Hence, at some point $\forall x \geq N$ a prime number greater than $20$ divides $P(x)$.

This is pretty magical! Without loss of generality all $d_i$ are positive integers. Pick $N$ greater than $\textstyle\left|\prod_{j=1, j \neq i}^9 (d_j - d_i)\right|$ for all $i$. For any $M \geq N$, consider the set $\{M+d_1, M+d_2, \dots, M+d_9\}$. We color red the element with the largest power of $2$, the largest power of $3$, and so on, until the largest power of $19$. Because there are $8$ primes less than $20$, there must be at least one element uncolored, say $M+d_i$. Then $$M+d_i \mid \frac{1}{M+d_i}(M+d_1)(M+d_2) \dots (M+d_9) \implies M+d_i \mid (d_1 - d_i)(d_2 - d_i)\dots (d_9-d_i),$$which evidently fails.

Suppose $P(x)$ is not divisible by any prime greater than $20$. So assume the only primes dividing $P(x)$ are in $\{p_1,..., p_8\}$. Now, choose a large integer $M$ such that $2^M > \max(d_1,\dots, d_9)$ and take $a > (p_1,\dots, p_8)^M$. Now we look at the sequence of numbers $a+d_1,\dots, a+d_9$ where all the primes dividing these numbers are in the set $\{p_1,\dots, p_8\}$ and each number is greater than $(p_1 \dots p_8)^M$ so for each of them we can find a prime (within $p_1,\dots,p_8$) in its factorization with exponent greater than than $M$. But we have 9 numbers in the sequence and only 8 prime numbers. So by pigeonhole, there are two indices of $d$ say, $u < v \in \{1,\dots,9\}$ such that $p^{M+1} \mid a+d_u, a+d_v$. Which implies that $p^{M+1} \mid d_u-d_v$. But this is impossible since $p^{M+1} > 2^M > \max(d_1,\dots,d_9) > |d_u-d_v| \blacksquare$

Can anyone please check if that is correct? Ok so shift $d_i$ so they are all positive. Also WLOG $d_1 <d_2<...<d_9$. Let us set $N = \prod_{i<j}(d_j-d_i)$, and let $x$ be arbitrary, but fixed $>N$ Note: $GCD(x+d_i, x+d_j) = GCD(x+d_i, d_j-d_i) \leq d_j-d_i $ Let $d_{i,j}$ refer to the greatest common divisor of $x+d_i$ and $x+d_j$ Because $x+d_i>N$, there is $a_i>1, a_i|(x+d_i)$ such that: GCD($a_i$, $\frac{x+d_j}{d_{i,j}}$)=1 for all $j$ not equal to $i$. Similar argument for all $i$ gives $a_1, a_2,...,a_9$, all relatively prime to one another, which concludes.

Let \(P(x)\) have no prime factors greater than 20; we will show \(x\) is bounded. Let \(D=\prod_{j>i}(d_j-d_i)\). Observe for all \(x\) that \(\gcd(x+d_i,x+d_j)\mid d_j-d_i\mid D\). In particular, for all primes \(p\le20\), \[\min\{\nu_p(x+d_i),\nu_p(x+d_j)\}\le\nu_p(D),\]so there is at most one \(j=1,\ldots,9\) with \(\nu_p(x+d_j)>\nu_p(D)\). But there are eight primes \(p\le20\), so by Pigeonhole for some \(j=1,\ldots,9\), we have \(\nu_p(x+d_j)\le\nu_p(D)\) for all \(p\), so \(x+d_j\le D\), implying that \(x\) is bounded above by a constant.

dame dame

I am really glad I know Kobayashi's theorem. It tends to... trivialize otherwise non-trivial problems. Let $f(x) = (x+d_1)(x+d_2) \cdots (x+d_9)$. We claim that there does not exist an infinite sequence of positive integers $a_1,a_2,...$ where the set of prime divisors of $f(a_i)$ (say, $P$) is finite for all $a_i$. Assume for the sake of contradiction such a sequence does exist. Clearly, the set prime divisors of the elements in the set $A = \{ a_i+b_1: i \in \mathbb{N} \}$ is a subset $P$ so must be finite. Thus, by Kobayashi's theorem, the set of prime numbers which divide an element in the set $A' =\{ a_i+b_1-(b_1-b_2): i \in \mathbb{N} \}$ (denoted as $Q$) is infinite. But, note that $a_i+b_1-(b_1-b_2) = a_i + b_2$. Thus, the set $Q$ is infinite and $Q \subset P$. Implying $P$ is infinite. Contradiction.

For the sake of contradiction assume that all the factors of $P(x) \in [2,3,5,7,11,13,17,19]$ This implies that $(x+d_1),.........,(x+d_j)$ has all it's factors in the set $[2,3,5,7,11,13,17,19]$ Choose $x \ge 9699690^N$ for a sufficiently large power $N$ with $\nu_{p_{j_i}}(x+d_1)>N$ with $j_i \in [1,2,3......,8,9]$ and $p_k \in [2,3,5,7,11,13,17,19]$ Hence,two of $p_{j_1}=p_{j_2}$,so $p_{j_1}^N||d_1-d_2|$,a contradiction for large enough $N$

Same as #14; posting for storage. Suppose the contrary, assuming that $P(x)$ only has prime factors in $[1,20].$ Notice that there are $8 $ such primes. Let $D=\prod_{i>j}(d_i-d_j)$ and we see that $\gcd(x+d_i,x+d_j)\mid D.$ Hence, $$\min(\nu_p(x+d_i),\nu_p(x+d_j))\le\nu_p(D)$$and $\nu_p(x+d_i)>\nu_p(D)$ for one or zero $i$ for all primes $p\in[1,20].$ By the Pigeonhole Principle, there must at least $i$ such that $\nu_p(x+d_i)\le\nu_p(D)$ for all $p,$ meaning $x+d_i\le D,$ a contradiction. $\square$

FTSOC, assume not and that all prime factors are in the set $\{2,3,5,7,11,13,17,19\}$. Add the constraint that $x+d_i > 1$ for all $i$. If $x+d_i=2^{e_1}3^{e_2} \cdots 19^{e_8}$, then assign to $x+d_i$ the number $a_i=\max(2^{e_1},3^{e_2}, \dots ,19^{e_8})=p_i^{b_i}$ for some prime $p_i$ such that $a_i|x+d_i$ and $a_i \ge \sqrt[8]{x+d_i}$. Then there exists $i,j$ such that $p_i=p_j=p$. Then we have that $$|d_j-d_i| \ge \gcd(d_j-d_i, x+ d_i)= \gcd(x+d_i,x+d_j) \ge \min(p^{b_i},p^{b_j}) =\min(a_i,a_j) \ge \min_{1 \le i \le 9} (\sqrt[8]{x+d_i}),$$a contradiction for big enough values of $x$.

Pick the $x+d_i$ with the highest power of $2$, the highest power of $3$, the highest power of $5$ and so on until the highest power of $19$. There are eight primes less than $20$ so WLOG $x+d_1\mid (x+d_2)(x+d_3)\dots(x+d_9).$ Now, we can subtract multiples of $(x+d_1)$ from the right side to get $x+d_1\mid r$ for some constant $r$ which depends only on $d_i.$ Thus, picking $x> r-d_1$ and we win

When I say "the nine factors" in this problem, I mean the nine $x+d_j$. The main idea of the problem is that these nine factors have a bounded $\gcd$ between every pair(because $d_i-d_j$ is bounded). Let $a_j$ be $x+d_j$ divided by the $\operatorname{lcm}$ of the eight $\gcd$s with the other eight factors. Each of these is greater than $1$ and pairwise coprime, so one of these has a prime factor greater than the eighth prime $19$, as desired. $\blacksquare$

Suppose otherwise. Call $x$ special if $P(x)$ has no prime divisors greater than $20$. Let $p_1, p_2, \ldots, p_8$ be the first primes, with $p_1 = 2$ and $p_8= 19$. Claim: For each $k$, there exists $M$ such that all special $x \ge M$ satisfy that there exists $i,j$ and a prime $0< p < 20$ with $p^k$ dividing $x+ d_i$ and $x + d_j$. Proof: Consider choosing $x > (p_1 p_2 \cdots p_8)^k$. Notice that each of the $x + d_j$ factors has some prime factor $p<20$ with $\nu_p(x + d_j) > k$ (since otherwise $x + d_j$ is bounded by $(p_1p_2 \cdots p_8)^k$). Since there are $9$ values of $x + d_1, x + d_2 , \ldots, x + d_9$, two of them must have the same prime $p^k$ dividing them, as desired. $\square$ Therefore, for each $k$, there exists $p^k$ that divides $(x + d_i) - (x + d_j) = d_i - d_j$. Choosing $k$ sufficiently large gives $d_i = d_j$, contradiction.

Suppose there exist arbitrarily large $x$ so that the prime factorization of $P(x)$ contains only primes in $\{2,3,\dots,19\}$. Then each of the nine factors $x+d_j$ has a maximal $\nu_p$ for $p\in \{2,3,\dots,19\}$ in the factorization which grows arbitrarily large. By Pigeonhole, then, the GCD of some two $x+d_i$ and $x+d_j$ would grow arbitrarily large; since it must divide $d_i-d_j$ this is a contradiction.

There are $8$ primes under $20.$ FTSOC assume there exits some $x$ such that the only factors of $P(x)$ are the primes under $20.$ We define the "best prime divisor" of a number $n$ to be the prime number with the highest $\nu_p(n)$ over all $p.$ A number can have multiple "best prime divisors". By pigeonhole, two numbers $x+a_i$ and $x+a_j$ must have the same "best prime divisor". Therefore, their GCF will be quite large. The GCF depends on $N.$ However, their GCF by Euclidean algorithm must divide $a_j-a_i$ which is already determined. Therefore, by making N very large, we get a contradiction as some increasing value must always divide a fixed value. Q.E.D.