6 added 68 characters in body

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.

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$

5 added 417 characters in body

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.

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

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$

4 added 561 characters in body

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: 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 < 8000000$ 10000000$and print out only$ p > 0.9 0.8 \, q \, (\log q)^2. $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\$

3 added 779 characters in body