Smallest prime in arithmetic progressions: upper bounds?Given N &gt; 2, find a prime p such that (1) p ≡ 1 ( mod N ) . (Of course, Dirichlet's theorem assures us that infinitely many such p exist.)Now, I do not know of a clever way to find such a p, so I suggested simply iterating through the arithmetic progression 1 + k N for k = 0 , 1 , 2 , …, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime p satisfying (1) is at most N O ( 1 ) . (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.More generally,Given an integer N, what upper bound do we know on the smallest prime satisfying (1)?I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.

Question

Smallest prime in arithmetic progressions: upper bounds?Given   N  &amp;gt;  2, find a prime p such that                    (1)                    p        ≡        1                (        mod                N        )        .            (Of course, Dirichlet&#039;s theorem assures us that infinitely many such p exist.)Now, I do not know of a clever way to find such a p, so I suggested simply iterating through the arithmetic progression   1  +  k  N for   k  =  0  ,  1  ,  2  ,  …, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime p satisfying (1) is at most       N          O      (      1      )      . (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.More generally,Given an integer N, what upper bound do we know on the smallest prime satisfying (1)?I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.

Cindy Mercer · Accepted Answer

Step 1The relevant results are found under the heading, Linnik&#039;s Theorem. Linnik proved that the least prime congruent to a mod d is at most   c      d    L   for some absolute constants c and L. The current best bound is   L  ≤  5.2.Step 2On the Generalized Riemann Hypothesis, you can show there&#039;s a prime less than   (  ϕ  (  d  )  log  ⁡  d      )    2  , where that&#039;s Euler&#039;s phi-function. It is conjectured there&#039;s always a prime less than       d    2  .

Humberto Campbell · Accepted Answer

Step 1Gerry Myerson has answered your main question, so I&#039;ll address the other part. I don&#039;t think that the claim is false, though certainly it&#039;s not proven. In any case I wouldn&#039;t say it&#039;s &quot;very unlikely&quot;.In fact it seems quite likely to me that the smallest k with   k  n  +  1 prime will be   O  (  (  log  ⁡  n      )    3    ) - indeed, probably even   O  (  (  log  ⁡  n      )    2    (  log  ⁡  log  ⁡  n      )    e    ) for some e.Step 2Disregarding   n  &amp;lt;  20,   e  =  0.18 works up to 30 million with a constant of 1. A braver mathematician might conjecture that it holds for   e  =  0 and a somewhat larger constant.

Given N>2, find a prime p such that p equiv 1(mod N).(1)

Answered question

Answer & Explanation

New Questions in Algebra II