login
The number of 8th powers in the multiplicative group modulo n.
5

%I #32 Aug 10 2023 02:20:50

%S 1,1,1,1,1,1,3,1,3,1,5,1,3,3,1,1,2,3,9,1,3,5,11,1,5,3,9,3,7,1,15,1,5,

%T 2,3,3,9,9,3,1,5,3,21,5,3,11,23,1,21,5,2,3,13,9,5,3,9,7,29,1,15,15,9,

%U 2,3,5,33,2,11,3,35,3,9,9,5,9,15,3,39,1,27,5,41,3,2

%N The number of 8th powers in the multiplicative group modulo n.

%C The size of the set of numbers j^8 mod n, gcd(j,n)=1, 1<=j<=n.

%H Antti Karttunen, <a href="/A293485/b293485.txt">Table of n, a(n) for n = 1..16384</a>

%H Richard J. Mathar, <a href="/A293482/a293482.pdf">Size of the Set of Residues of Integer Powers of Fixed Exponent</a>, research paper, 2017.

%F A000010(n) / a(n) = A247257(n).

%F Multiplicative with a(2^e) = 1 for e<=4, a(2^e) = 2^(e-5) for e>=5; a(p^e) = (p-1)*p^(e-1)/8 for p == 1 (mod 8); a(p^e) = (p-1)*p^(e-1)/4 for p == 5 (mod 8); a(p^e) = (p-1)*p^(e-1)/2 for p == {3,7} (mod 8). - _R. J. Mathar_, Oct 15 2017 [corrected by _Georg Fischer_, Jul 21 2022]

%p A293485 := proc(n)

%p local r,j;

%p r := {} ;

%p for j from 1 to n do

%p if igcd(j,n)= 1 then

%p r := r union { modp(j &^ 8,n) } ;

%p end if;

%p end do:

%p nops(r) ;

%p end proc:

%p seq(A293485(n),n=1..120) ;

%t a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^8 - 1, k_ /; Divisible[k, n]];

%t Array[a, 100] (* _Jean-François Alcover_, May 24 2023 *)

%t f[p_, e_] := (p - 1)*p^(e - 1)/Switch[Mod[p, 8], 1, 8, 5, 4, _, 2]; f[2, e_] := If[e <= 4, 1, 2^(e - 5)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Aug 10 2023 *)

%o (PARI)

%o \\ The following two functions by _Charles R Greathouse IV_, from A247257:

%o g(p, e) = if(p==2, 2^min(e-1, 4), if(p%4==3, 2, if(p%8==5, 4, 8)));

%o A247257(n) = my(f=factor(n)); prod(i=1, #f~, g(f[i, 1], f[i, 2]));

%o A293485(n) = (eulerphi(n)/A247257(n)); \\ _Antti Karttunen_, Dec 05 2017

%Y The number of k-th powers in the multiplicative group modulo n: A046073 (k=2), A087692 (k=3), A250207 (k=4), A293482 (k=5), A293483 (k=6), A293484 (k=7), this sequence (k=8).

%Y Cf. A085311, A247257 (order of the kernel isomorphism of Z/nZ to this group), A000010.

%K nonn,mult

%O 1,7

%A _R. J. Mathar_, Oct 10 2017