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



Is every sequence that looks like an AP really an AP?
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](https://en.wikipedia.org/wiki/S-unit#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.


