[seqfan] Re: Primes modulo primes
mathar at strw.leidenuniv.nl
Thu Jun 17 19:59:37 CEST 2010
Concerning the arithmetic progressions in
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
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
Greatest of the Least Primes in Arithmetic Progressions Having a given
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  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 ) 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  conjectured that P(k,l)<k^2 always.
(R Mathar: that's basically what we're looking for)
Heath-Brown  remarked that presumably P(k,l)<<k*(log k)^2. Turan ,
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.
 P. Erdos, "On some application of Brun's method," Acta Sci. Math (Szeged), v. 13, 1949 pp 57-63
 D. R. Heath-Brown, "almost-primes in arithmetic progressions i short
intervals, Math Proc Cambr. Phil Soc v 83 (1978) pp 357-375
 H.-J. Kanold, "Uber Primzahlen in arithmetischen Folgne," Math. Ann. v 156
(1964) pp 393-395
 E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953)
 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
 C. Pomerance, "A note on the least prime in an arithmetic progression (to appear)
 K. Prachar, "Uber die kleinste Primzahl in einer arithmetischen Reihe" J Reine Angew Math. 206 (1961) p 3-4
 A. Schinzel, "Remark on the paper of K. Prachar "Uber die kleinste..", J. Reine Angew Math. v 210 (1962) pp 122-122
 E. C. Titmarsh, "A divisor problem" Renc Circ Math Palermo v 54 (1930) pp 414-429
 P. Turan, "Uber Primzahlen der arithmetischen Progression," Acta Sci Math. (Szeged) v8 (1936/37) pp 226-235
 S. S. Wagstaff, Jr. "The irregular priems to 125000," Math. Comp. v 32 (1978) pp 583-591.
D. R. Heath-Brown in the Quart. J. of Math 41 (49) (1990) 405-418
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
More information about the SeqFan