The following question came up in the discussion at [How small can a group with an n-dimensional irreducible complex representation be?](https://mathoverflow.net/questions/530/how-small-can-a-group-with-an-n-dimensional-irreducible-complex-representation-be) :


Is it known that there are infinitely many primes p for which the least prime q which is 1 mod p is > c p^2 (for some positive constant c, independent of p)?


Wikipedia's article on primes in arithmetic progressions says that the expected bound for the least prime is p^{2 + \epsilon}, given various strengthenings of the Riemann Hypothesis, but it doesn't say much about lower bounds.


By the way, for the applications in the linked post, it would be even better if the same lower bound applied to finding a prime power q which is 1 mod p.



Arithmetic progressions without small primes
It is firmly expected that for every \epsilon > 0 each aritmetic progression with difference q and terms coprime with q will contain a prime <<{\epsilon} q^{1 + \epsilon}. 
This is a direct consequence of a conjecture of H. L. Montgomery (not the one on pair correlations, another one), which implies both the GRH and the Elliott-Halberstam conjecture. But the upper bound $\ll {\epsilon} q^{1 + \epsilon}$ for the least prime in an arithmetic progression was conjectured by S. Chowla (in his book "The Riemann Hypothesis and Hilbert's tenth problem"), and probably by others independently of him, years before Montgomery made his conjecture, and presumably on the basis of the same kind of heuristic argument that moonface advances. In fact, I think that even an upper bound as strong as qlog(q)^2 has been conjectured, though I won't swear to that. But it is definitely known that qlog(q) won't work. The Montgomery conjecture seems reasonable, because it rests on the assumption that there is square root cancellation in a certain sum with D-characters as coefficients in an explicit formula - this ties in with moonface's comment about the proof that GRH implies L \leq 2 being "lossy". On the other hand, one cannot expect to get q^{1 + \epsilon} out of the Elliott-Halberstam conjecture in any direct way, because that is an averaging kind of statement. You would not expect to get L \leq 2 out of the Bombieri-A. I. Vinogradov theorem either, for that is an averaged version of GRH. The point is that information is needed about every single one of the arithmetic progressions individually.


