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

%I #43 Oct 28 2023 11:41:23

%S 1,1,2,2,4,2,6,4,6,4,2,4,12,6,8,8,16,6,18,8,12,2,22,8,4,12,18,12,28,8,

%T 6,16,4,16,24,12,36,18,24,16,8,12,42,4,24,22,46,16,42,4,32,24,52,18,8,

%U 24,36,28,58,16,12,6,36,32,48,4,66,32,44,24,14,24,72,36,8,36,12,24,78,32,54,8,82,24

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

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

%C A000010(n) / a(n) is another multiplicative integer sequence.

%H R. J. Mathar, <a href="/A293482/b293482.txt">Table of n, a(n) for n = 1..7548</a>

%H R. J. Mathar, <a href="/A293482/a293482.pdf">Size of the set of residues of integer powers of fixed exponent</a>, 2017.

%H Samer Seraj, <a href="https://dx.doi.org/10.7546/nntdm.2022.28.4.730-743">Counting general power residues</a>, Not. Numb. Th. Discr. Math. 28 (4) (2022) 730-743.

%H Samer Seraj, <a href="http://math.colgate.edu/~integers/x62/x62.pdf">Resolution of Mathar's conjectures on counting power residues</a>, INTEGERS 23 (2023) #A62.

%F Conjecture: a(2^e) = 1 for e <= 1; a(2^e) = 2^(e-1) for e >= 1; a(5)=4; a(5^e) = 4*5^(e-2) for e > 1; a(p^e) = (p-1)*p^(e-1) for p == {2,3,4} (mod 5); a(p^e) = (p-1)*p^(e-1)/5 for p == 1 (mod 5). - _R. J. Mathar_, Oct 13 2017

%F a(n) = A000010(n)/A319099(n). This implies that the conjecture above is true. - _Jianing Song_, Nov 10 2019

%p A293482 := 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 &^ 5,n) } ;

%p end if;

%p end do:

%p nops(r) ;

%p end proc:

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

%t a[n_] := Module[{r, j}, r = {}; For[j = 1, j <= n, j++, If[GCD[j, n] == 1, r = r ~Union~ {PowerMod[j, 5, n]}] ]; Length[r]];

%t Table[a[n], {n, 1, 120}] (* _Jean-François Alcover_, Feb 14 2023, after _R. J. Mathar_ *)

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

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

%Y Cf. A052274, A319099, A000010.

%K nonn,mult

%O 1,3

%A _R. J. Mathar_, Oct 10 2017