A271801 Smallest composite k such that k divides (n^(k-1)-1)/(n-1), n > 1.

341, 91, 85, 217, 217, 25, 9, 91, 91, 133, 65, 85, 15, 341, 91, 9, 25, 49, 21, 221, 169, 91, 25, 91, 9, 121, 145, 15, 49, 49, 25, 85, 35, 9, 403, 133, 39, 341, 121, 21, 529, 25, 9, 133, 133, 65, 49, 25, 51, 91, 265, 9, 55, 91, 57, 25, 341, 15, 341, 91, 9, 481, 65, 33, 469, 49, 25, 35, 169, 9, 85, 65

Offset: 2

Author

Thomas Ordowski, Apr 14 2016

Keywords

• nonn

Comments

Smallest pseudoprime k to base n such that gcd(k,n-1)=1.

Theorem (R. Steuerwald, 1948): if k is a pseudoprime to base b and gcd(k,b-1)=1, then (b^k-1)/(b-1) is a pseudoprime to base b.

From Robert Israel, Apr 14 2016: (Start)

a(n) is odd.

If m == n (mod a(n)) then a(m) <= a(n).

a(n) = 9 iff n == -1 (mod 9).

a(n) = 15 iff n == -1 (mod 15) but not (mod 9).

The first case where a(n) is not a semiprime (A001358) is a(383) = 561. (End)

Links

• Robert Israel, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A001358.

Programs

Maple

Comps:= remove(isprime, [seq(k,k=9..10^6,2)]):
f:= proc(n) local k;
   for k in Comps do
     if (n^(k-1)-1)/(n-1) mod k = 0 then return k fi
   od:
   error "ran out of composites"
end proc:
seq(f(n),n=2..100); # Robert Israel, Apr 14 2016

Mathematica

Table[SelectFirst[Range[10^3], CompositeQ@ # && Divisible[(n^(# - 1) - 1)/(n - 1), #] &], {n, 2, 73}] (* Michael De Vlieger, Apr 14 2016, Version 10 *)

PARI

a(n) = {my(k = 4); while ((n^(k-1)-1)/(n-1) % k, k++; if (isprime(k), k++)); k;} \\ Michel Marcus, Apr 14 2016

Extensions

More terms from Michael De Vlieger, Apr 14 2016