A316940 Smallest "anti-Carmichael pseudoprime" to base n.

35, 7957, 16531, 1247, 17767, 35, 817, 2501, 697, 4141, 2257, 143, 9577, 2257, 4187, 1247, 3991, 221, 7957, 2059, 55, 161, 1027, 115, 403, 475, 247, 4553, 35, 247, 6289, 697, 1853, 35, 1247, 35, 589, 221, 95, 533, 35, 559, 77, 215, 253, 235, 221, 329, 247, 119

Offset: 1

Author

Thomas Ordowski, Jul 17 2018

Keywords

• nonn

Comments

a(n) is the smallest k such that n^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

All listed terms are semiprime and squarefree, except a(26) = 475 = 5^2*19.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A121707 (probably "anti-Carmichael numbers": n such that p-1 does not divide n-1 for every prime p dividing n).

Cf. A316907 ("anti-Carmichael pseudoprimes" to base 2).

Programs

Mathematica

Table[Block[{k = 2}, While[Nand[PowerMod[n, k - 1, k] == 1, AllTrue[FactorInteger[k][[All, 1]] - 1, Mod[k - 1, #] != 0 &]], k++]; k], {n, 50}] (* Michael De Vlieger, Jul 20 2018 *)

PARI

isok(k, n) = {if (!isprime(k) && Mod(n, k)^(k-1) == 1, f = factor(k)[,1]; for (j=1, #f~, if (!((k-1) % (f[j]-1)), return (0));); return (1);); return (0);}
a(n) = {my(k=2); while(!isok(k, n), k++); k;} \\ Michel Marcus, Jul 17 2018

Extensions

More terms from Michel Marcus, Jul 17 2018