Return to Answer

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$ 

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$ 

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$ 

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$ 

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

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$ 

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$