A034694 Smallest prime == 1 (mod n).

2, 3, 7, 5, 11, 7, 29, 17, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 41, 43, 23, 47, 73, 101, 53, 109, 29, 59, 31, 311, 97, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 89, 181, 47, 283, 97, 197, 101, 103, 53, 107, 109, 331, 113, 229, 59, 709, 61, 367, 311

Offset: 1

Author

Labos Elemer, David W. Wilson, Spring 1998

Keywords

• nonn
• nice
• easy

Comments

Thangadurai and Vatwani prove that a(n) <= 2^(phi(n)+1)-1. - T. D. Noe, Oct 12 2011

Conjecture: a(n) < n^2 for n > 1. - Thomas Ordowski, Dec 19 2016

Eric Bach and Jonathan Sorenson show that, assuming GRH, a(n) <= (1 + o(1))*(phi(n)*log(n))^2 for n > 1. See the abstract of their paper in the Links section. - Jianing Song, Nov 10 2019

a(n) is the smallest prime p such that the multiplicative group modulo p has a subgroup of order n. - Joerg Arndt, Oct 18 2020

Examples

			If n = 7, the smallest prime in the sequence 8, 15, 22, 29, ... is 29, so a(7) = 29.
		

References

• Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.
• P. Ribenboim, The Book of Prime Number Records. Chapter 4,IV.B.: The Smallest Prime In Arithmetic Progressions, 1989, pp. 217-223.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Bach and Jonathan Sorenson, Explicit bounds for primes in residue classes, Mathematics of Computation, 65(216) (1996), 1717-1735.
• Steven R. Finch, Linnik's Constant
• S. Graham, On Linnik's Constant, Acta Arithm. 39, 1981, pp. 163-179.
• I. Niven and B. Powell, Primes in Certain Arithmetic Progressions, Amer. Math. Monthly 83(6) (1976), 467-469.
• R. Thangadurai and A. Vatwani, The least prime congruent to one modulo n, Amer. Math. Monthly 118(8) (2011), 737-742.

Crossrefs

Cf. A034693, A034780, A034782, A034783, A034784, A034785, A034846, A034847, A034848, A034849, A038700, A085420.

Records: A120856, A120857.

Programs

Haskell

a034694 n = until ((== 1) . a010051) (+ n) (n + 1)
-- Reinhard Zumkeller, Dec 17 2013

Mathematica

a[n_] := Block[{k = 1}, If[n == 1, 2, While[Mod[Prime@k, n] != 1, k++ ]; Prime@k]]; Array[a, 64] (* Robert G. Wilson v, Jul 08 2006 *)
With[{prs=Prime[Range[200]]},Flatten[Table[Select[prs,Mod[#-1,n]==0&,1],{n,70}]]] (* Harvey P. Dale, Sep 22 2021 *)

PARI

a(n)=if(n<0,0,s=1; while((prime(s)-1)%n>0,s++); prime(s))

Formula

a(n) = min{m: m = k*n + 1 with k > 0 and A010051(m) = 1}. - Reinhard Zumkeller, Dec 17 2013

a(n) = n * A034693(n) + 1. - Joerg Arndt, Oct 18 2020