A293484 -id:A293484 - cp's OEIS frontend

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

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, 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, 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

Offset: 1

R. J. Mathar, Oct 10 2017

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

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

R. J. Mathar, Table of n, a(n) for n = 1..7548
R. J. Mathar, Size of the set of residues of integer powers of fixed exponent, 2017.
Samer Seraj, Counting general power residues, Not. Numb. Th. Discr. Math. 28 (4) (2022) 730-743.
Samer Seraj, Resolution of Mathar's conjectures on counting power residues, INTEGERS 23 (2023) #A62.

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).

Cf. A052274, A319099, A000010.

A293482 := proc(n)
    local r,j;
    r := {} ;
    for j from 1 to n do
        if igcd(j,n)= 1 then
            r := r union { modp(j &^ 5,n) } ;
        end if;
    end do:
    nops(r) ;
end proc:
seq(A293482(n),n=1..120) ;

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]];
Table[a[n], {n, 1, 120}] (* Jean-François Alcover, Feb 14 2023, after R. J. Mathar *)
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 *)

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

a(n) = A000010(n)/A319099(n). This implies that the conjecture above is true. - Jianing Song, Nov 10 2019

A319101 Number of solutions to x^7 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 7. Those n such that a(n) > 1 are in A066502.

			Solutions to x^7 == 1 (mod 29): x == 1, 7, 16, 20, 23, 24, 25 (mod 29).
Solutions to x^7 == 1 (mod 43): x == 1, 4, 11, 16, 21, 35, 41 (mod 43).
Solutions to x^7 == 1 (mod 49): x == 1, 8, 15, 22, 29, 36, 43 (mod 49) (x == 1 (mod 7)).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), this sequence (k=7), A247257 (k=8).
Cf. A066502, A140444, A293484, A000010.
Mobius transform gives A307382.

f[p_, e_] := If[Mod[p, 7] == 1, 7, 1]; f[7, 1] = 1; f[7, e_] := 7; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(7, Z[i]))

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).
a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

A293483 The number of 6th powers in the multiplicative group modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 5, 1, 2, 1, 2, 2, 8, 1, 3, 2, 1, 5, 11, 1, 10, 2, 3, 1, 14, 2, 5, 4, 5, 8, 2, 1, 6, 3, 2, 2, 20, 1, 7, 5, 2, 11, 23, 2, 7, 10, 8, 2, 26, 3, 10, 1, 3, 14, 29, 2, 10, 5, 1, 8, 4, 5, 11, 8, 11, 2, 35, 1, 12, 6, 10, 3, 5, 2, 13, 4, 9, 20

Offset: 1

R. J. Mathar, Oct 10 2017

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

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

R. J. Mathar, Table of n, a(n) for n = 1..10132
Richard J. Mathar, Size of the Set of Residues of Integer Powers of Fixed Exponent, 2017.

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

Cf. A052275, A319100, A000010.

A293483 := proc(n)
    local r,j;
    r := {} ;
    for j from 1 to n do
        if igcd(j,n)= 1 then
            r := r union { modp(j &^ 6,n) } ;
        end if;
    end do:
    nops(r) ;
end proc:
seq(A293483(n),n=1..120) ;

a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^6 - 1, k_ /; Divisible[k, n]];
Array[a, 100] (* Jean-François Alcover, May 24 2023 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 6] == 1, 6, 2]; f[2, e_] := If[e <= 3, 1, 2^(e - 3)]; f[3, e_] := If[e <= 2, 1, 3^(e - 2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

Conjecture: a(2^e) = 1 for e <= 3; a(2^e) = 2^(e-3) for e >= 3; a(3^e) = 1 for e <= 2; a(3^e) = 3^(e-2) for e >= 2; a(p^e) = (p-1)*p^(e-1)/2 for p == 5 (mod 6); a(p^e) = (p-1)*p^(e-1)/6 for p == 1 (mod 6). - R. J. Mathar, Oct 13 2017

a(n) = A000010(n)/A319100(n). This implies that the conjecture above is true. - Jianing Song, Nov 10 2019

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

Original entry on oeis.org

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, 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, 2, 3, 5, 33, 2, 11, 3, 35, 3, 9, 9, 5, 9, 15, 3, 39, 1, 27, 5, 41, 3, 2

Offset: 1

R. J. Mathar, Oct 10 2017

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

Antti Karttunen, Table of n, a(n) for n = 1..16384
Richard J. Mathar, Size of the Set of Residues of Integer Powers of Fixed Exponent, research paper, 2017.

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).

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

A293485 := proc(n)
    local r,j;
    r := {} ;
    for j from 1 to n do
        if igcd(j,n)= 1 then
            r := r union { modp(j &^ 8,n) } ;
        end if;
    end do:
    nops(r) ;
end proc:
seq(A293485(n),n=1..120) ;

a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^8 - 1, k_ /; Divisible[k, n]];
Array[a, 100] (* Jean-François Alcover, May 24 2023 *)
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 *)

\\ The following two functions by Charles R Greathouse IV, from A247257:
g(p, e) = if(p==2, 2^min(e-1, 4), if(p%4==3, 2, if(p%8==5, 4, 8)));
A247257(n) = my(f=factor(n)); prod(i=1, #f~, g(f[i, 1], f[i, 2]));
A293485(n) = (eulerphi(n)/A247257(n)); \\ Antti Karttunen, Dec 05 2017

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

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]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A319101 Number of solutions to x^7 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A293483 The number of 6th powers in the multiplicative group modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula