. For all $i \in\{1, \ldots, k-1\}$, we denote by $\mathscr{P}_{i}$ the set of prime numbers congruent to $i$ modulo $k$. Since there are infinitely many prime numbers and at most one is divisible by $k$, the pigeonhole principle ensures that one of these sets, say $\mathscr{P}_{r}$, is infinite. Let $\left(x_{j}\right)_{j \geqslant 0}$ be the sequence of elements of $\mathscr{P}_{r}$ arranged in increasing order. For all integers $j \geqslant 1$, we have $x_{j}=x_{0} \bmod [k]$ so the number $a_{j}=\frac{x_{j}-x_{0}}{k}$ is a strictly positive integer. The strict increase of the sequence $\left(a_{j}\right)_{j>1}$ follows from that of $\left(x_{j}\right)_{j \geqslant 1}$.

We then set $p=x_{0}$. Since, for all $n \geqslant 1$, we have $p+k a_{n}=x_{n}$, this concludes.