cp's OEIS Frontend

A034694 Smallest prime == 1 (mod n).

%I A034694 #73 Dec 17 2023 18:16:49
%S A034694 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 A034694 101,53,109,29,59,31,311,97,67,103,71,37,149,191,79,41,83,43,173,89,
%U A034694 181,47,283,97,197,101,103,53,107,109,331,113,229,59,709,61,367,311
%N A034694 Smallest prime == 1 (mod n).
%C A034694 Thangadurai and Vatwani prove that a(n) <= 2^(phi(n)+1)-1. - _T. D. Noe_, Oct 12 2011
%C A034694 Conjecture: a(n) < n^2 for n > 1. - _Thomas Ordowski_, Dec 19 2016
%C A034694 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 A034694 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 A034694 Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.
%D A034694 P. Ribenboim, The Book of Prime Number Records. Chapter 4,IV.B.: The Smallest Prime In Arithmetic Progressions, 1989, pp. 217-223.
%H A034694 T. D. Noe, <a href="/A034694/b034694.txt">Table of n, a(n) for n = 1..10000</a>
%H A034694 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 A034694 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 A034694 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 A034694 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 A034694 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 A034694 a(n) = min{m: m = k*n + 1 with k > 0 and A010051(m) = 1}. - _Reinhard Zumkeller_, Dec 17 2013
%F A034694 a(n) = n * A034693(n) + 1. - _Joerg Arndt_, Oct 18 2020
%e A034694 If n = 7, the smallest prime in the sequence 8, 15, 22, 29, ... is 29, so a(7) = 29.
%t A034694 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 A034694 With[{prs=Prime[Range[200]]},Flatten[Table[Select[prs,Mod[#-1,n]==0&,1],{n,70}]]] (* _Harvey P. Dale_, Sep 22 2021 *)
%o A034694 (PARI) a(n)=if(n<0,0,s=1; while((prime(s)-1)%n>0,s++); prime(s))
%o A034694 (Haskell)
%o A034694 a034694 n = until ((== 1) . a010051) (+ n) (n + 1)
%o A034694 -- _Reinhard Zumkeller_, Dec 17 2013
%Y A034694 Cf. A034693, A034780, A034782, A034783, A034784, A034785, A034846, A034847, A034848, A034849, A038700, A085420.
%Y A034694 Records: A120856, A120857.
%K A034694 nonn,nice,easy
%O A034694 1,1
%A A034694 _Labos Elemer_, _David W. Wilson_, Spring 1998