[seqfan] Re: Primes modulo primes

[Richard Mathar]

Concerning the arithmetic progressions in
http://list.seqfan.eu/pipermail/seqfan/2010-June/005071.html 

ftaw> A sufficient condition for them to be correct is that the sequence kp+1 
ftaw> (resp. kp-1) always has a prime element for some k <= 2p. It appears 
ftaw> that there is in fact always a prime element for some k <= p. Is this a 
ftaw> known result? If so, is there a suitable link or reference that can be 
ftaw> added?

The associated conjecture is that in the arithmetic progression
1, p+1, 2p+1, 3p+1, 4p+1,... at most p composites can appear; the first
prime appears not later than at p^2+1. The article by S. S. Wagstaff, Jr,
in Math. Comp. 33 (147) (1979) p 1073-1080
http://www.jstor.org/stable/2006082
starts


"
Greatest of the Least Primes in Arithmetic Progressions Having a given
Modulus (Title)

Abstract: We give a heuristic argument, supported by numerical evidence,
which suggests that the maximum, taken over the reduced residue classes
modulo k, of the least prime in the class, is usually about
phi(k)*log(k)*log phi(k) where phi is Euler's phi-function.

1. Introduction. When (k,l)=1, let P(k,l) denote the least prime in the
arithmetic progression l+kn, n>=0. Let P(k) = max_l P(k,l), where the 
maximum is taken over all l for with 0<l<k and (k,l)=1.

In 1944 Linnik [5] proved that P(k,l) < k^A for some large absolute constant A.
Since then, several authors have found successively smaller, but still larger,
explicit values for A. Titchmarsh showed (Theorem 6 of [11]) that the
extended Riemann Hypothesis (ERH) for L-functions of characters modulo k implies
that P(i,l)<< (phi(k))^2*(log k)^4. Kanold [3] conjectured that P(k,l)<k^2 always.
"
   (R Mathar: that's basically what we're looking for)

"
Heath-Brown [2] remarked that presumably P(k,l)<<k*(log k)^2. Turan [12],
also assuming the ERH, proved that for each delta >0, we have
(1) P(k,l) < phi(k)*log^(2+delta) k
for almost all residue classes l, ie, the inequality fails for at most o(phi(k))
of the l's as k-> infinity.
<snip>

[1] P. Erdos, "On some application of Brun's method," Acta Sci. Math (Szeged), v. 13, 1949 pp 57-63
[2] D. R. Heath-Brown, "almost-primes in arithmetic progressions i short
 intervals, Math Proc Cambr. Phil Soc v 83 (1978) pp 357-375
[3] H.-J. Kanold, "Uber Primzahlen in arithmetischen Folgne," Math. Ann. v 156
  (1964) pp 393-395
[4] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953)
[5] U. V. Linnik, "On the least prime in an arithmetic progression. I. The
  basic theorem," Rec. Math (N.S.) v 15 (57) (1944), pp139-178
[6]...
[7] C. Pomerance, "A note on the least prime in an arithmetic progression (to appear)
[8] K. Prachar, "Uber die kleinste Primzahl in einer arithmetischen Reihe" J Reine Angew Math. 206 (1961) p 3-4
[10] A. Schinzel, "Remark on the paper of K. Prachar "Uber die kleinste..", J. Reine Angew Math. v 210 (1962) pp 122-122
[11] E. C. Titmarsh, "A divisor problem" Renc Circ Math Palermo v 54 (1930) pp 414-429
[12] P. Turan, "Uber Primzahlen der arithmetischen Progression," Acta Sci Math. (Szeged) v8 (1936/37) pp 226-235
[13] S. S. Wagstaff, Jr. "The irregular priems to 125000," Math. Comp. v 32 (1978) pp 583-591.
"

See also
D. R. Heath-Brown in the Quart. J. of Math 41 (49) (1990) 405-418
http://dx.doi.org/10.1093/qmath/41.4.405

A Granville and C Pomerance, "On the least prime in certain arithmetic
progressions", J. Lond Math Soc http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5520&rep=rep1&type=pdf