A348259 Number of bases 1<b<n and coprime to n, such that b^n == b (mod n).

0, 0, 1, 0, 3, 0, 5, 0, 1, 0, 9, 0, 11, 0, 3, 0, 15, 0, 17, 0, 3, 0, 21, 0, 3, 0, 1, 2, 27, 0, 29, 0, 3, 0, 3, 0, 35, 0, 3, 0, 39, 0, 41, 0, 7, 0, 45, 0, 5, 0, 3, 2, 51, 0, 3, 0, 3, 0, 57, 0, 59, 0, 3, 0, 15, 4, 65, 0, 3, 2, 69, 0, 71, 0, 3

Offset

1,5

Comments

This is a count of Fermat Pseudoprimes.

Numbers not in the sequence: 13, 25, 33, 37, 43, 49, 53, 61, 67, 73, 75, 83, 85, 89, 91, 93, 97, ..., .

First occurrence of k=0..: 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, -1, 286, 17, 1854, ..., .

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Formula

a(n) = A063994(n)-1.

a(2n) must be even. Those that exceed 0 are A039772.

a(p) = p-2 iff p is a prime (A000040).

a(2n-1) < 2n-3 iff 2n-1 is composite and a(2n-1) is odd.

a(n) = (Product_{primes p|n} gcd(p-1, n-1)) - 1. - Jianing Song, Nov 20 2021

Example

a(3) = 1 since 2^3 = 8 == 2 (mod 3);
a(5) = 2 since {2, 3, 4}^5 = {32, 243, 1024} == {2, 3, 4} (mod 5);
a(9) = 1 since 8^9 = 134217728 == 8;
a(15) = 3 since {4, 11, 14}^15 = {1073741824, 4177248169415651, 155568095557812224} == {4, 11, 14} (mod 15); etc.

Mathematica

a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]

Prog

(PARI) a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ Michel Marcus, Oct 09 2021

Crossrefs

Cf. A000040, A039772, A063994.

Sequence in context: A002656 A234434 A234020 * A276833 A166586 A122274

Adjacent sequences: A348256 A348257 A348258 * A348260 A348261 A348262

Keyword

base,nonn

Author

Robert G. Wilson v, Oct 08 2021

Status

approved