cp's OEIS Frontend

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

%I A348259 #12 Dec 15 2021 17:38:25
%S A348259 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,
%T A348259 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,
%U A348259 3,0,15,4,65,0,3,2,69,0,71,0,3
%N A348259 Number of bases 1<b<n and coprime to n, such that b^n == b (mod n).
%C A348259 This is a count of Fermat Pseudoprimes.
%C A348259 Numbers not in the sequence: 13, 25, 33, 37, 43, 49, 53, 61, 67, 73, 75, 83, 85, 89, 91, 93, 97, ..., .
%C A348259 First occurrence of k=0..: 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, -1, 286, 17, 1854, ..., .
%H A348259 Antti Karttunen, <a href="/A348259/b348259.txt">Table of n, a(n) for n = 1..20000</a>
%F A348259 a(n) = A063994(n)-1.
%F A348259 a(2n) must be even. Those that exceed 0 are A039772.
%F A348259 a(p) = p-2 iff p is a prime (A000040).
%F A348259 a(2n-1) < 2n-3 iff 2n-1 is composite and a(2n-1) is odd.
%F A348259 a(n) = (Product_{primes p|n} gcd(p-1, n-1)) - 1. - _Jianing Song_, Nov 20 2021
%e A348259 a(3) = 1 since 2^3 = 8 == 2 (mod 3);
%e A348259 a(5) = 2 since {2, 3, 4}^5 = {32, 243, 1024} == {2, 3, 4} (mod 5);
%e A348259 a(9) = 1 since 8^9 = 134217728 == 8;
%e A348259 a(15) = 3 since {4, 11, 14}^15 = {1073741824, 4177248169415651, 155568095557812224} == {4, 11, 14} (mod 15); etc.
%t A348259 a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]
%o A348259 (PARI) a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ _Michel Marcus_, Oct 09 2021
%Y A348259 Cf. A000040, A039772, A063994.
%K A348259 base,nonn
%O A348259 1,5
%A A348259 _Robert G. Wilson v_, Oct 08 2021