David Wilson said:

I would be willing to conjecture that if there are an infinitude of primes == r (mod m), then there is a prime of this form between n and n(1+e) for sufficient n.

Are there any results on the density of such primes relative to all of the primes? If so, then probably the prime number theorem could probably be used to establish the above conjecture.

The Prime Number Theorem for Arithmetic Progressions says that, for any m, the primes are asymptotically evenly distributed among the possible congruence classes mod m. (This is stronger than what Dirichlet proved -- he showed that the primes congruent to a mod m had the right "Dirichlet density", the def of which involves the sum of their reciprocals, but left the same statement about "natural density" as a conjecture, eventually proved by de la Valle'e-Poussin. I should admit that all I know about this proof is that it's too hard for me.) I think this does indeed imply what David wants, right? If the primes congruent to a mod m have a large desert between N and (1+e)N, then the density of such primes up to (1+e)N is 1/(1+e) times what it is up to N, and so those two densities cannot both be arbitrarily close to the asymptotic value 1/phi(m). So such deserts cannot occur for arbitrarily large N. But Adam woke up an extra time last night, so my thinking is not entirely coherent this holiday morning. Someone let me know if I'm being overly optimistic. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.