Consider the sequence of prime numbers: $2,3,5,7, \cdots$. Now reduce this sequence modulo $k$ for some integer $k > 2$. Show the resulting sequence is not periodic. :
EDIT: As noted in the comments, what I really mean is that the sequence is not pre-periodic; i.e. it is not periodic with some prefix attached. So Jeff Strom's argument doesn't work; and I said that $k>2$ which rules out that case.
Dirichlet's theorem on primes would imply that if it was periodic, then the period would contain each admissible residue class (mod $k$) with equal frequency.
For $k=4$, I think there's some result that the quantity $\pi_{1,4}(n) – \pi_{3,4}(n)$ alternates between positive and negative values infinitely often. (Here $\pi_{i,j}(n)$ counts the number of primes less than $n$, congruent to $i$ (mod $j$).) This result settles the question for $k=4$; and perhaps there are generalizations of this to $k>4$. But maybe there's an easier, more elementary approach.
Re Comments: Lucia, thanks for your answers! Your second proof seems elementary (and the result in the first proof is very interesting); but you can include more details? Why does periodicity imply that $\text{log} L(s, \chi)$ is analytic; and why does the corresponding $L$-function have no non-trivial zeros?
Best Answer
Here is an elaboration of my comment to the question. Suppose that the primes are (pre)-periodic $\pmod k$ (with $k>2$). Let $\chi$ be a non-trivial character $\pmod k$. Then the assumption on the primes implies that $$ S(x,\chi) = \sum_{p\le x} \chi(p), $$ is bounded.
Now consider $$ \log L(s,\chi) = \sum_{j=1}^{\infty} \frac{1}{j} \sum_{p} \frac{\chi(p)^j}{p^{js}}. $$ A priori this is well defined and analytic in Re$(s)>1$. The terms with $j\ge 2$ are analytic in Re$(s)>1/2$. The assumption on the periodicity of the primes gives that $$ \sum_{p} \frac{\chi(p)}{p^s} = \int_{1}^{\infty} S(x,\chi) \frac{s}{x^{s+1}} dx, $$ is analytic in Re$(s)>0$. Thus we conclude that $\log L(s,\chi)$ is analytic in Re$(s)>1/2$ (this is the Riemann Hypothesis, but of course a false assumption implies many things!).
Now suppose that $\chi$ is a non-trivial quadratic character. Then from above we see that for Re$(s)>1/2$ we have $$ \log L(s,\chi) = O(1)+ \frac{1}{2} \sum_{p} \frac{\chi(p)^2}{p^{2s}} = O(1) + \frac{1}{2} \sum_{p} \frac{1}{p^{2s}}, $$ since $\chi$ is quadratic. If we let $s$ take real values tending to $1/2$ from above, this gives a contradiction (as $L(1/2,\chi)$ is bounded, whereas exponentiating the above would imply that it goes to infinity).
Alternatively take $\chi$ to be a complex character (this works for $k\neq 3, 4, 6, 8$) and then the prime square terms above are also bounded (for Re$(s)>0$) and we conclude that $\log L(s,\chi)$ is analytic in Re$(s)>1/3$. Hence the $L$-function is non-zero in that region, and by the functional equation (say $\chi$ is primitive) we conclude that the $L$-function can only have trivial zeros. This is a contradiction.
Thirdly, as noted before Daniel Shiu's result on Strings of Congruent primes (JLMS 2000) also gives the result (although this is harder than the proof above). Nowadays the Maynard(-Tao) machinery gives relatively easy access to such results (and in a stronger form).
Finally, as Terry Tao observes in the comments, Gowers's question on why the Riemann zeta function has zeros is certainly relevant here, and see also my answer to that question. In that spirit, one may say that the primes are not periodic $\pmod k$, because the integers are!