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

Author

Max Alekseyev, Apr 14 2005

Keywords

• easy
• nonn

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

Examples

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

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Fermat Pseudoprime
• Wikipedia, Fermat pseudoprime

Crossrefs

Cf. A007535, A181780, A239452.

Programs

Mathematica

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

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

Formula

a(p) = 2 for odd prime p.