EDIT, September 2015. This material has come up again. Note that, in post and comments, i simply report things I found. I also did a computer program because I was curious about what might be the best possible behavior. It is probably time for a follow-up question.

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 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

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$
```