A105222 Smallest integer m > 1 such that m^(n-1) == 1 (mod n).

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, 16, 9, 2, 55, 21, 57, 20, 59, 2, 61, 2, 63, 8, 65, 8, 25, 2, 69, 22, 11, 2, 73, 2, 75, 26

Offset

1,1

Comments

Composite n are Fermat pseudoprimes to base a(n).

For n > 1; (5+(-1)^n)/2 <= a(n) <= n+(-1)^n. If n > 2 and a(n) > 2 then n is composite. - Thomas Ordowski, Dec 01 2013

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Fermat Pseudoprime

Wikipedia, Fermat pseudoprime

Formula

a(p) = 2 for odd prime p.

Example

We have 2^(2-1) == 0, 3^(2-1) == 1 (mod 2), so a(2) = 3.

Mathematica

Table[k = 2; While[PowerMod[k, n - 1, n] != 1, k++]; k, {n, 2, 100}] (* T. D. Noe, Dec 07 2013 *)

Prog

(PARI) a(n) = {m = 2; while ((m^(n-1) % n) !=  lift(Mod(1, n)), m++); m; } \\ Michel Marcus, Dec 01 2013
(PARI) a(n) = my(m=2); while(Mod(m, n)^(n-1)!=1, m++); m \\ Charles R Greathouse IV, Dec 01 2013

Crossrefs

Cf. A007535, A181780, A239452.

Sequence in context: A348846 A057815 A007387 * A280503 A094757 A095171

Adjacent sequences: A105219 A105220 A105221 * A105223 A105224 A105225

Keyword

easy,nonn

Author

Max Alekseyev, Apr 14 2005

Status

approved