A293483 -id:A293483 - cp's OEIS frontend

A319100 Number of solutions to x^6 == 1 (mod n).

1, 1, 2, 2, 2, 2, 6, 4, 6, 2, 2, 4, 6, 6, 4, 4, 2, 6, 6, 4, 12, 2, 2, 8, 2, 6, 6, 12, 2, 4, 6, 4, 4, 2, 12, 12, 6, 6, 12, 8, 2, 12, 6, 4, 12, 2, 2, 8, 6, 2, 4, 12, 2, 6, 4, 24, 12, 2, 2, 8, 6, 6, 36, 4, 12, 4, 6, 4, 4, 12, 2, 24, 6, 6, 4, 12, 12, 12, 6, 8, 6, 2

Offset: 1

Jianing Song, Sep 10 2018

All terms are 3-smooth. a(n) is even for n > 2. Those n such that a(n) = 2 are in A066501.

			Solutions to x^6 == 1 (mod 13): x == 1, 3, 4, 9, 10, 12 (mod 13).
Solutions to x^6 == 1 (mod 27): x == 1, 8, 10, 17, 19, 26 (mod 27) (x == 1, 8 (mod 9)).
Solutions to x^6 == 1 (mod 37): x == 1, 10, 11, 26, 27, 36 (mod 37).

Jianing Song, Table of n, a(n) for n = 1..10000
Steven Finch, Greg Martin and Pascal Sebah, Roots of unity and nullity modulo n, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), this sequence (k=6), A319101 (k=7), A247257 (k=8).
Cf. A046072, A066501, A088232, A293483, A000010.
Mobius transform gives A307381.

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

Multiplicative with a(2) = 1, a(4) = 2, a(2^e) = 4 for e >= 3; a(3) = 2, a(3^e) = 6 if e >= 2; for other primes p, a(p^e) = 6 if p == 1 (mod 6), a(p^e) = 2 if p == 5 (mod 6).
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(6, k_i).
a(n) = A060594(n)*A060839(n).
For n > 2, a(n) = A060839(n)*2^A046072(n).
a(n) = A060594(n) iff n is not divisible by 9 and no prime factor of n is congruent to 1 mod 6, that is, n in A088232.
a(n) = A000010(n)/A293483(n). - Jianing Song, Nov 10 2019
Sum_{k=1..n} a(k) ~ c * n * log(n)^3, where c = (1/Pi^4) * Product_{p prime == 1 (mod 6)} (1 - (12*p-4)/(p+1)^3) = 0.0075925601... (Finch et al., 2010). - Amiram Eldar, Mar 26 2021

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

Original entry on oeis.org

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

A293484 The number of 7th powers in the multiplicative group modulo n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 4, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 6, 20, 24, 22, 46, 16, 6, 20, 32, 24, 52, 18, 40, 24, 36, 4, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24, 10, 24, 72, 36, 40, 36

Offset: 1

R. J. Mathar, Oct 10 2017

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

A000010(n) / a(n) is another multiplicative integer sequence (size of the kernel of the isomorphism of the multiplicative group modulo n to the multiplicative group of 7th powers modulo n).

R. J. Mathar, Table of n, a(n) for n = 1..10116
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), A293483 (k=6), this sequence (k=7), A293485 (k=8).

Cf. A085310, A319101, A000010.

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

a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^7 - 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, 7] == 1, 7, 1]; f[2, e_] := 2^(e-1); f[7, 1] = 6; f[7, e_] := 6*7^(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 <= 1; a(2^e) = 2^(e-1) for e >= 1; a(7^e) = 6 for e=1; a(7^e) = 6*7^(e-2) for e >= 2; a(p^e) = (p-1)*p^(e-1) for p == {2,3,4,5,6} (mod 7); a(p^e) = (p-1)*p^(e-1)/7 for p == 1 (mod 7). - R. J. Mathar, Oct 13 2017

a(n) = A000010(n)/A319101(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

A319100 Number of solutions to x^6 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293484 The number of 7th 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