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