Does there exist a strictly increasing sequence $\{a_n\}_{n=1}^\infty$ of natural numbers with the following property: for $\forall$ $c\in \mathbb{Z}$ the sequence $c+a_1,c+a_2,...,c+a_n...$ has finite number of primes? Explain your answer.
Problem
Source: II International Festival of Young Mathematicians Sozopol 2011, Theme for 10-12 grade
Tags: number theory, prime numbers, Sequence
11.12.2019 00:12
By Kobayashi's Theorm we get a contradiction immediately.$\square$.But since this is an olympiad problem so i think an elementary solution will exist
11.12.2019 00:50
Kobayashi's theorem is about prime divisors of the elements of a set, this is about prime elements of a set, so you can't use Kobayashi. There actually exists such a sequence: We will construct it inductively, first noticing this fact: Lemma. $\quad$ If $n!|a_n$ and $a_n>0$ for every $n\in\mathbb{N}$, then $(a_n+c)_{n\in\mathbb{N}}$ has only finitely many prime terms for all $c\ne {-1, 1}$. Proof. $\quad$ Since $a_n\ge n!$, there exists a large $n>c$ such that all the terms of $(a_n)$ after $a_n$ are larger than $-2c$ (remember $c$ might be negative). For such $m>n$ we have $c!|a_m$, and so $c|a_n+c$, and since $a_n+c>|c|$ thus if only $|c|>1$, $a_m$ has a proper divisor $c$, and so isn't prime. Now we construct recursively the sequence $(a_n)$ so that it is strictly increasing, $n!|a_n$ for all $n$ and $a_n+1$, $a_n-1$ are composite for all $n$. Let $a_1=5$, as the base of the recursion. Now assume we have picked the terms $a_1, a_2, \ldots, a_{n-1}$ already. Take any primes $p, q>n$ and notice that there exist $x_1, x_2\in\mathbb{N}$ such that $p|xn!+1$ and $q|yn!-1$. From the Chinese Remainder Theorem there exist arbitrarily large $x\in\mathbb{N}$ such that $p|xn!+1$ and $q|xn!-1$. We can pick $x$ greater than $a_{n-1}, p, q$. Then, if we define $a_n=xn!$, we get that $a_n>a_{n-1}$, and $n!|a_n$, and $a_n\pm1$ has a proper divisor $p$ or $q$, so is composite. That finishes the construction.