Maximum runs of composites in arithmetic progressions

Question

Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$?

Put another way, can you prove the following:

For all primes $p$, and all integers $0 \le m <p$, there exists $n\in\Bbb{Z}$ with $1\le n < p$ such that $np+m$ is prime.

I think I have a proof sketch but it's fiddly and I don't want to reinvent the wheel (likely badly).

To illustrate, here's the result checked for $p = 5$:

Arithmetic progressions with gaps $5$ from $5$ to $24$ ($p$ to $p^2-1$):

$\boldsymbol{5},10,15,20$
$6,\boldsymbol{11},16,21$
$\boldsymbol{7},12,\boldsymbol{17},22$
$8,\boldsymbol{13},18,\boldsymbol{23}$
$9,14,\boldsymbol{19},24$

As you can see, in bold, all of these arithmetic progressions have at least one prime. If one of these sequences didn't have a prime the theorem would be disproven for $p = 5$.

Note that proving that every arithmetic progression of gap $p$ and length $(p-1)$ has at least one number coprime to $(p-1)!$ should also prove the above, and indeed is more general, as if $n$ is coprime to $(p-1)!$ and is less than $p^2$ then it has to be prime.

Answer 1

This is unfortunately hopeless. The best bound as of now is that there exists an absolute constant $c$ such that for all integers $m$ with $0 \le m < p$, there is a prime of the form $np+m$ in the interval $[p, cp^5)$. The Generalized Riemann Hypothesis would imply a prime in the interval $[p, p^2 (\log (p))^2)$. You can read more here.

Answer 2

Some comments too long for the comment area; NOT A FULL ANSWER

The notion of arithmetic progressions in this question can be recast as residue classes. Each progression can be expressed as $np+a$, or numbers $k_i$ such that $k_i\equiv a \mod{p}$. Plainly, $a\in \{0,1,\dots p-1\}$, so there will be exactly $p$ such arithmetic progressions, and if each contains at least on prime, then there must be at least $p$ primes (including $p$ itself) in the interval $[p,p^2)$.

This is a reasonable expectation, but saying that is different from a proving that it will be the case with regard to every $p$. By the Prime Number Theorem, the number of primes less than $p^2$ will be approximately $\frac{p^2}{\ln p^2}=\frac{p^2}{2\ln p}$, and the number of primes less than $p$ will be approximately $\frac{p}{\ln p}$. The number of primes in the interval will be the difference of those two, or $\frac{p^2-2p}{2\ln p}$, which is greater than $p$ for all but the few smallest primes. So in general, there should be a sufficient number of primes in the interval to support the conclusion. Proving that there is at least one prime in each residue class would be the next task.