Primes congruent to $k \pmod p$ between $p$ and $p^2$?

Question

Is it true that for any prime $p$, there are primes $< p^2$ which are congruent to every $k<p$?

For example,

$$ \begin{align} 11 &\equiv 1 \pmod 5 \\ 7 &\equiv 2 \pmod 5 \\ 13 &\equiv 3 \pmod 5 \\ 19 &\equiv 4 \pmod 5 \\ \end{align} $$

Answer 1

This might be true. But it seems very hard to prove. In this paper by Bach and Sorenson, they show that assuming the generalized Riemann Hypothesis, one can show that for each $k \bmod p$, there will be a prime $q \equiv k \bmod p$ with $q \leq 2 (p \log p)^2$, which is a bit weaker than what you hoped to show.

It's unlikely to find a counterexample, and also somewhat unlikely to produce a proof. The best currently known unconditional results are have bounds more like $q \ll p^5$ or so --- these problems are sometimes called Linnik Problems.