Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. Thangadurai and A. Vatwani. They give an elementary argument to show $$ p \leq 2^{\phi(q) + 1} - 1.$$ The best unconditional result they report is T. Xylouris (2009), $$ p \leq c_1 q^{5.2}$$ which improves a 1992 result of Heath-Brown. Apparently Oesterle showed that GRH implies $$ p \leq 70 q (\log q)^2 $$ which is much better. This was a private communication to the authors, not in the reference list. EDIT TOOOOO: there is some doubt now, [BACH and SORENSEN][1] say, on their page 1718 (second page of the downloadable pdf) that Oesterle proved something different in 1979, also never published it. So perhaps the best GRH bound is theirs, $$ p \leq (1 + o(1)) (\phi(q) \log q)^2.$$ Perhaps Xylouris has also worked on this aspect. Anyway, table of contents at [CONTENTS][2] EDIT: I ran a little computer program for the GRH result, dropping the factor of 70... It certainly appears that the largest prime $q$ for which $ p > q (\log q)^2 $ is $q=5227$ with first prime congruent to $1\pmod q$ being $p=397253 = 1 + 76 \cdot 5227.$ Unprovable. Program run for $q < 10000000$ and print out only $ p > 0.8 \, q \, (\log q)^2. $ Each line is $q, \, p, \, p / \left( q \, (\log q)^2 \right)$ jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./primes_in_progressions 2 3 3.12205 3 7 1.93325 5 11 0.849326 7 29 1.09409 19 191 1.15951 31 311 0.850749 227 5449 0.815642 521 16673 0.817744 3833 229981 0.881247 5227 397253 1.03683 6637 424769 0.82637 138163 15750583 0.813731 170167 24504049 0.992619 177791 22757249 0.875941 218531 27534907 0.833558 325517 44921347 0.856523 326617 42460211 0.806441 707467 110364853 0.859855 1940777 326050537 0.801413 4722079 1104966487 0.99082 8195953 1753933943 0.84445 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ [1]: http://www.ams.org/journals/mcom/1996-65-216/S0025-5718-96-00763-6/home.html [2]: http://www.maa.org/pubs/monthly_oct11_toc.html