cp's OEIS Frontend

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

%I A271801 #21 Apr 16 2016 20:49:20
%S A271801 341,91,85,217,217,25,9,91,91,133,65,85,15,341,91,9,25,49,21,221,169,
%T A271801 91,25,91,9,121,145,15,49,49,25,85,35,9,403,133,39,341,121,21,529,25,
%U A271801 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
%N A271801 Smallest composite k such that k divides (n^(k-1)-1)/(n-1), n > 1.
%C A271801 Smallest pseudoprime k to base n such that gcd(k,n-1)=1.
%C A271801 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.
%C A271801 From _Robert Israel_, Apr 14 2016: (Start)
%C A271801 a(n) is odd.
%C A271801 If m == n (mod a(n)) then a(m) <= a(n).
%C A271801 a(n) = 9 iff n == -1 (mod 9).
%C A271801 a(n) = 15 iff n == -1 (mod 15) but not (mod 9).
%C A271801 The first case where a(n) is not a semiprime (A001358) is a(383) = 561. (End)
%H A271801 Robert Israel, <a href="/A271801/b271801.txt">Table of n, a(n) for n = 2..10000</a>
%p A271801 Comps:= remove(isprime, [seq(k,k=9..10^6,2)]):
%p A271801 f:= proc(n) local k;
%p A271801    for k in Comps do
%p A271801      if (n^(k-1)-1)/(n-1) mod k = 0 then return k fi
%p A271801    od:
%p A271801    error "ran out of composites"
%p A271801 end proc:
%p A271801 seq(f(n),n=2..100); # _Robert Israel_, Apr 14 2016
%t A271801 Table[SelectFirst[Range[10^3], CompositeQ@ # && Divisible[(n^(# - 1) - 1)/(n - 1), #] &], {n, 2, 73}] (* _Michael De Vlieger_, Apr 14 2016, Version 10 *)
%o A271801 (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
%Y A271801 Cf. A001358.
%K A271801 nonn
%O A271801 2,1
%A A271801 _Thomas Ordowski_, Apr 14 2016
%E A271801 More terms from _Michael De Vlieger_, Apr 14 2016