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,1

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

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.

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

Example

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

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

Prog

(PARI) a(n)=if(n<0, 0, s=1; while((prime(s)-1)%n>0, s++); prime(s))
(Haskell)
a034694 n = until ((== 1) . a010051) (+ n) (n + 1)
-- Reinhard Zumkeller, Dec 17 2013

Crossrefs

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

Records: A120856, A120857.

Sequence in context: A358242 A241082 A219789 * A050921 A087386 A110359

Adjacent sequences: A034691 A034692 A034693 * A034695 A034696 A034697

Keyword

nonn,nice,easy

Author

Labos Elemer, David W. Wilson, Spring 1998

Status

approved