Is every sequence that looks like an AP really an AP?

Caveat: I am not at all a number theorist, and I randomly came up with the following question while I was hiking. But I already asked two serious number theorists, and since they did not know the answer to my question, I decided to pose it here.

Let $c > 0$ be given. Suppose $a_1,a_2,a_3,\dots$ is a sequence of positive integers such that for all primes $p > c$, we have $a_i \equiv a_j \ (\text{mod}. p)$ if and only if $i \equiv j \ (\text{mod}. p)$. Does it follow that $(a_i)$ is an arithmetic progression, i.e. there are integers $a$ and $b$ such that $a_k = a + kb$?

• A minor comment, but , since only the gaps count, you can adjust the indexing , weaken to non-negative, and assume $a_0=0$ then for $k > c$ we have that $a_k$ has all the prime factors of $k$ with the possible inclusion or exclusion of primes less than $c+1$ – Aaron Meyerowitz May 1 '17 at 0:56
• The answer already given below, a next natural question is whether it would be enough to require the same conditions but, instead of all primes $>c$, only for some infinite set of primes. – მამუკა ჯიბლაძე May 1 '17 at 6:19

For each $n$, the differences $a_{n+1}-a_n$, $a_{n+2}-a_{n+1}$, and $a_{n+2}-a_n$ can only be divisible by powers of $2$ and primes less than or equal to $c$. Since $$\frac{a_{n+2}-a_{n+1}}{a_{n+2}-a_n}+\frac{a_{n+1}-a_n}{a_{n+2}-a_n}=1,$$ this is a solution to the S-unit equation, where $S=\{2\}\cup\{p:p\leq c\}$. This means the sequence $x_n:=(a_{n+1}-a_n)/(a_{n+2}-a_n)$ can only take on finitely many values as $n$ varies.
Let $p$, $p'>c$ be distinct primes each not dividing the numerator of any of the finitely many distinct non-zero values of $x_n - x_{n'}$. Then the sequence $x_n$ has period dividing $p$ and $p'$, hence is constant. Say $x_n=k$ for all $n$. This implies $$a_{n+2}-a_{n+1}=\frac{1-k}{k}(a_{n+1}-a_n),$$ i.e. the differences $a_{n+1}-a_n$ form a geometric progression. Hence either $a_n$ is an arithmetic progression (if the common ratio $(1-k)/k$ is $1$), or $a_n$ has the form $$a_n = bc^n+d,$$ with $b$, $c$, $d\in\mathbb{Z}$. The latter case cannot happen, as Fermat's Little Theorem would imply $a_{n+p-1}\equiv a_n\mod p$ for $p$ sufficiently large.
• It seems to me that the S-unit equation only implies that the fraction $(a_{n+2}-a_{n+1})/(a_{n+1}-a_n)$ takes finitely many values. But this is enough for your argument to go through. One just has to rule out sequences of the form $ab^n+c$. – Gjergji Zaimi May 1 '17 at 0:18