%I #73 Dec 17 2023 18:16:49

%S 2,3,7,5,11,7,29,17,19,11,23,13,53,29,31,17,103,19,191,41,43,23,47,73,

%T 101,53,109,29,59,31,311,97,67,103,71,37,149,191,79,41,83,43,173,89,

%U 181,47,283,97,197,101,103,53,107,109,331,113,229,59,709,61,367,311

%N Smallest prime == 1 (mod n).

%C Thangadurai and Vatwani prove that a(n) <= 2^(phi(n)+1)-1. - _T. D. Noe_, Oct 12 2011

%C Conjecture: a(n) < n^2 for n > 1. - _Thomas Ordowski_, Dec 19 2016

%C 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

%C 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

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.

%D P. Ribenboim, The Book of Prime Number Records. Chapter 4,IV.B.: The Smallest Prime In Arithmetic Progressions, 1989, pp. 217-223.

%H T. D. Noe, <a href="/A034694/b034694.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Bach and Jonathan Sorenson, <a href="https://doi.org/10.1090/S0025-5718-96-00763-6">Explicit bounds for primes in residue classes</a>, Mathematics of Computation, 65(216) (1996), 1717-1735.

%H Steven R. Finch, <a href="http://web.archive.org/web/20010207193039/http://www.mathsoft.com/asolve/constant/linnik/linnik.html">Linnik's Constant</a>

%H S. Graham, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3926.pdf">On Linnik's Constant</a>, Acta Arithm. 39, 1981, pp. 163-179.

%H I. Niven and B. Powell, <a href="http://www.jstor.org/stable/2318341">Primes in Certain Arithmetic Progressions</a>, Amer. Math. Monthly 83(6) (1976), 467-469.

%H R. Thangadurai and A. Vatwani, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.118.08.737">The least prime congruent to one modulo n</a>, Amer. Math. Monthly 118(8) (2011), 737-742.

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

%F a(n) = n * A034693(n) + 1. - _Joerg Arndt_, Oct 18 2020

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

%t 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 *)

%t With[{prs=Prime[Range[200]]},Flatten[Table[Select[prs,Mod[#-1,n]==0&,1],{n,70}]]] (* _Harvey P. Dale_, Sep 22 2021 *)

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

%o (Haskell)

%o a034694 n = until ((== 1) . a010051) (+ n) (n + 1)

%o -- _Reinhard Zumkeller_, Dec 17 2013

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

%Y Records: A120856, A120857.

%K nonn,nice,easy

%O 1,1

%A _Labos Elemer_, _David W. Wilson_, Spring 1998