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

Question

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$?

Answer 1

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.