Can we prove the "Bertrand postulate" for primes $a \pmod q$, namely: there is always a prime number $p\equiv a \pmod q$ betwen $nq$ and $nq^2$ for every $n>0$ and $(a,q)=1$. (This would mean that between $nq$ and $nq^2$ there are always at least $\varphi(q)$ primes, each belonging to a different residue class modulo $q$.)



Primes in arithmetic progression $a \pmod q$
This question appears to have been addressed by P. Moree in [this paper](https://www.sciencedirect.com/science/article/pii/0898122193900713). In the notation of that paper, he defines


$$\displaystyle B\_m(z,d) = \liminf \{c : \forall x \geq c, (x,zx) \text{ contains at least } m \text{ primes} $$
$$\displaystyle \text{ congruent to } a \pmod{d} \text{ for all } \gcd(a,d) = 1\}.$$


In particular, he proves that provided the quantity $\sigma(d)$ defined to be


$$\displaystyle \sigma(d) = \sum\_{\substack{p \leq d \\ p \nmid d}} \frac{1}{p}$$


is strictly less than one, then one can obtain an explicit estimate for $B\_m(z,d)$ whenever


$$\displaystyle z > \frac{d}{(d-1)(1 - \sigma(d))}.$$


His methods generalize an elementary argument of Erdos (who gave an elementary proof of the original Bertrand's postulate), and so do not run into the problems that one encounters when attempting to use the known analytic theorems to attack the problem (i.e., possible existence of Siegel zeroes, etc.). Unfortunately, by Mertens' theorem the hypothesis that $\sigma(d) < 1$ is extremely strict: indeed, Moree shows that $\sigma(d) < 1$ implies that $d \leq 840$.


In principle, one can approach the problem by obtaining a reasonably explicit lower bound for the number of primes in an arithmetic progression, up to some bound $x$. For each pair $(a,q)$ with $\gcd(a,q) = 1$ define $N(a,q)$ to be a positive number with the property that whenever $x > N(a,q)$ we have


$$\pi(x; a,q) > \frac{2x}{3 \phi(q) \log x},$$


say. Then for $q \geq 2$ and $nq > N(a,q)$ there will always be a prime congruent to $a \pmod{q}$ in the interval $(nq, nq^2)$, since by the Brun-Titchmarsh theorem we have


$$\displaystyle \pi(x; a,q) \leq \frac{2x}{\phi(q) \log (x/q)}$$


for all $x \geq q \geq 2$. In particular,


$$\displaystyle \pi(nq^2; a, q) - \pi(nq; a, q) > \frac{2nq^2}{3\phi(q) \log(nq^2)} - \frac{2nq}{\phi(q) \log(n)}$$
$$ = \frac{2nq}{3\phi(q)} \left(\frac{(2q -3) \log n - 6 \log q}{\log n(\log n + \log q^2)} \right)$$


which is positive. Calculating $N(a,q)$ however seems to be a very hard problem.


