A247257 -id:A247257 - cp's OEIS frontend

A060839 Number of solutions to x^3 == 1 (mod n).

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 1, 3, 3, 3, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 3, 9, 1, 3, 1, 3, 1, 1, 3, 1, 3, 3, 3, 1, 3, 3, 3, 3, 1, 3, 1, 1, 3, 1, 3, 1, 1, 1, 3, 9, 1, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), May 02 2001

Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.4... - Benoit Cloitre, Aug 19 2002 [C = (11/(6*Pi*sqrt(3))) * Product_{p prime == 1 (mod 3)} (1 - 2/(p*(p+1))) = 0.3170565167... (Finch and Sebah, 2006). - Amiram Eldar, Mar 26 2021]

			a(7) = 3 because the three solutions to x^3 == 1 (mod 7) are x = 1,2,4.

T. D. Noe, Table of n, a(n) for n = 1..1000
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.
Steven Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A005088, A357905 (base-3 logarithm).
Number of solutions to x^k == 1 (mod n): A060594 (k=2), this sequence (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Column 3 of A354057.

A060839 := proc(n)
    local a,pf,p,r;
    a := 1 ;
    for pf in ifactors(n)[2] do
        p := op(1,pf);
        r := op(2,pf);
        if p = 2 then
            ;
        elif p =3 then
            if r >= 2 then
                a := a*3 ;
            end if;
        else
            if modp(p,3) = 2 then
                ;
            else
                a := 3*a ;
            end if;
        end if;
    end do:
    a ;
end proc:
seq(A060839(n),n=1..40) ; # R. J. Mathar, Mar 02 2015

a[n_] := Sum[ If[ Mod[k^3-1, n] == 0, 1, 0], {k, 1, n}]; Table[ a[n], {n, 1, 105}](* Jean-François Alcover, Nov 14 2011, after PARI *)
f[p_, e_] := If[Mod[p, 3] == 1, 3, 1]; f[3, 1] = 1; f[3, e_] := 3; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

PARI
```
a(n)=sum(i=1,n,if((i^3-1)%n,0,1))
```

a(n)=my(f=factor(n)); prod(i=1, #f~, if(f[i, 1]==3, 3^min(f[i, 2]-1, 1), if(f[i, 1]%3==1, 3, 1))) \\ Jianing Song, Oct 21 2022

from math import prod
from sympy import factorint
def A060839(n): return prod(3 for p, e in factorint(n).items() if (p!=3 or e!=1) and p%3!=2) # Chai Wah Wu, Oct 19 2022

Let b(n) be the number of primes dividing n which are congruent to 1 (mod 3) (sequence A005088); then a(n) is 3^b(n) if n is not divisible by 9 and 3^(b(n) + 1) if n is divisible by 9.
Multiplicative with a(3) = 1, a(3^e) = 3, e >= 2, a(p^e) = 3 for primes p of the form 3k+1, a(p^e) = 1 for primes p of the form 3k+2. - David W. Wilson, May 22 2005 [Corrected by Jianing Song, Oct 21 2022]
If the multiplicative group of integers modulo n has (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then a(n) = Product_{i=1..r} gcd(3,k_r). - Jianing Song, Oct 21 2022

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

Original entry on oeis.org

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

A319099 Number of solutions to x^5 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1

Offset: 1

Jianing Song, Sep 10 2018

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

			Solutions to x^5 == 1 (mod 11): x == 1, 3, 4, 5, 9 (mod 11).
Solutions to x^5 == 1 (mod 25): x == 1, 6, 11, 16, 21 (mod 25) (x == 1 (mod 5)).
Solutions to x^5 == 1 (mod 31): x == 1, 2, 4, 8, 16 (mod 31).

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), this sequence (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Cf. A030430, A066500, A293482, A000010.
Mobius transform gives A307380.

f[p_, e_] := If[Mod[p, 5] == 1, 5, 1]; f[5, 1] = 1; f[5, e_] := 5; 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(5,Z[i]));

Multiplicative with a(5) = 1, a(5^e) = 5 if e >= 2; for other primes p, a(p^e) = 5 if p == 1 (mod 5), 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(5, k_i).
a(n) = A000010(n)/A293482(n). - 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

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]

A329272 Number of octic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 1, 1, 3, 0, 1, 2, 0, 0, 1, 1, 3, 0, 3, 4, 7, 0, 1, 3, 1, 0, 1, 2, 0, 0, 0, 1, 3, 0, 1, 8, 1, 0, 3, 0, 3, 0, 3, 6, 7, 0, 1, 1, 0, 0, 1, 4, 0, 0, 7, 3, 3, 0, 3, 2, 1, 0, 1, 3, 3, 0, 0, 0, 9, 0, 1, 7, 1, 0, 1, 0, 7, 0, 0, 1, 1, 0, 1, 12, 0, 0, 1, 1, 21, 0, 3, 2, 7, 0, 3

Offset: 1

Jianing Song, Nov 10 2019

a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a eighth-power root of unity (+-1, +-i, +-sqrt(2)/2 +- sqrt(2)/2*i, i = sqrt(-1)).

Mobius transform of A247257.

			Let w = exp(2*Pi*i/8) = sqrt(2)/2 + i*sqrt(2)/2. For n = 17, the 7 octic primitive Dirichlet characters modulo n are:
  Chi_1 = [0, 1, -i, w, -1, -w, -w^3, w^3, i, i, w^3, -w^3, -w, -1, w, -i, 1];
  Chi_2 = [0, 1, -1, i, 1, i, -i, -i, -1, -1, -i, -i, i, 1, i, -1, 1];
  Chi_3 = [0, 1, i, w^3, -1, -w^3, -w, w, -i, -i, w, -w, -w^3, -1, w^3, i, 1];
  Chi_4 = [0, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1];
  Chi_5 = [0, 1, -i, -w, -1, w, w^3, -w^3, i, i, -w^3, w^3, w, -1, -w, -i, 1];
  Chi_6 = [0, 1, -1, -i, 1, -i, i, i, -1, -1, i, i, -i, 1, -i, -1, 1];
  Chi_7 = [0, 1, i, -w^3, -1, w^3, w, -w, -i, -i, -w, w, w^3, -1, -w^3, i, 1],
so a(17) = 7.

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

Number of k-th power primitive Dirichlet characters modulo n: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), A307381 (k=6), A307382 (k=7), this sequence (k=8).

Cf. A247257 (number of solutions to x^8 == 1 (mod n)).

f[2, e_] := If[2 <= e <= 5, 2^(e-2), 0]; f[p_, e_] := If[e == 1, GCD[p-1, 8] - 1, 0];  a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)={
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2, if(e>=2&&e<=5, r*=2^(e-2), r=0; return(r)));
        if(p>2, if(e==1, r*=gcd(p-1,8)-1, r=0; return(r)));
    );
    return(r);
}

Multiplicative with a(2^e) = 2^(e-2) for 2 <= e <= 5, a(2^e) = 0 for e = 1 or e >= 6; a(p^e) = gcd(p-1, 8)-1 if p > 2 and e = 1, a(p^e) = 0 if p > 2 and e >= 2.

A354057 Square array read by ascending antidiagonals: T(n,k) is the number of solutions to x^k == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 4, 3, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 3, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 6, 1, 4, 1, 2, 1, 1, 1, 4, 1, 4, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Jianing Song, May 16 2022

Row n and Row n' are the same if and only if (Z/nZ)* = (Z/n'Z)*, where (Z/nZ)* is the multiplicative group of integers modulo n.
Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354060.
Each column is multiplicative.

			  n/k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  10   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
  11   1  2  1  2  5  2  1  2  1 10  1  2  1  2  5  2  1  2  1 10
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  3  4  1  6  1  4  3  2  1 12  1  2  3  4  1  6  1  4
  14   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  15   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  16   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  17   1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 16  1  2  1  4
  18   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  19   1  2  3  2  1  6  1  2  9  2  1  6  1  2  3  2  1 18  1  2
  20   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)

k-th column: A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Applying Moebius transform to the rows gives A354059.
Applying Moebius transform to the columns gives A354058.
Cf. A327924.

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

If (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then T(n,k) = Product_{i=1..r} gcd(k,k_r).
T(p^e,k) = gcd((p-1)*p^(e-1),k) for odd primes p. T(2,k) = 1, T(2^e,k) = 2*gcd(2^(e-2),k) if k is even and 1 if k is odd.
A327924(n,k) = Sum_{q|n} T(n,k) * (Sum_{s|n/q} mu(s)/phi(s*q)).

A327924 Square array read by ascending antidiagonals: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 4, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 3, 1, 2, 1, 1, 1, 4, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Jianing Song, Sep 30 2019

The semidirect product of C_m and C_n has group representation G = , where r is any number such that r^n == 1 (mod m). Two groups G =  and G' =  are isomorphic if and only if there exists some k, gcd(k,n) = 1 such that r^k == s (mod m), in which case f(x^i*y^j) = x^i*y^(k*j) is an isomorphic mapping from G to G'.
Given m, T(m,n) only depends on the value of gcd(n,psi(m)), psi = A002322 (Carmichael lambda). So each row is periodic with period psi(m). See A327925 for an alternative version.
Every number k occurs in the table. By Dirichlet's theorem on arithmetic progressions, there exists a prime p such that p == 1 (mod 2^(k-1)), then T(p,2^(k-1)) = d(gcd(2^(k-1),p-1)) = k (see the formula below). For example, T(5,4) = 3, T(17,8) = 4, T(17,16) = 5, T(97,32) = 6, T(193,64) = 7, ...
Row m and Row m' are the same if and only if (Z/mZ)* = (Z/m'Z)*, where (Z/mZ)* is the multiplicative group of integers modulo m. The if part is clear; for the only if part, note that the two sequences {(number of x in (Z/mZ)* such that x^n = 1)}{n>=1} and {T(m,n)}{n>=1} determine each other, and the structure of a finite abelian group G is uniquely determined by the sequence {(number of x in G such that x^n = 1)}{n>=1}. - _Jianing Song, May 16 2022

			  m/n  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  10   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
  11   1  2  1  2  2  2  1  2  1  4  1  2  1  2  2  2  1  2  1  4
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  2  3  1  4  1  3  2  2  1  6  1  2  2  3  1  4  1  3
  14   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  15   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  16   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  17   1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3
  18   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  19   1  2  2  2  1  4  1  2  3  2  1  4  1  2  2  2  1  6  1  2
  20   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
Example shows that T(16,4) = 6: The semidirect product of C_16 and C_4 has group representation G = <x, y|x^16 = y^4 = 1, yxy^(-1) = x^r>, where r = 1, 3, 5, 7, 9, 11, 13, 15. Since 3^3 == 11 (mod 16), 5^3 == 13 (mod 16), <x, y|x^16 = y^4 = 1, yxy^(-1) = x^3> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^11> are isomorphic, <x, y|x^16 = y^4 = 1, yxy^(-1) = x^5> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^13> are isomorphic, giving a total of 6 non-isomorphic groups.

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)
Math Overflow, When are two semidirect products of two cyclic groups isomorphic.
Jianing Song, An equivalent formula.

Cf. A327925, A002322, A000010, A000005.

Cf. also A060594, A060839, A073103, A319099, A319100, A319101, A247257.

numord(n,q) = my(v=divisors(q),r=znstar(n)[2]); sum(i=1,#v,prod(j=1,#r,gcd(v[i],r[j]))*moebius(q/v[i]))
T(m,n) = my(u=divisors(n)); sum(i=1,#u,numord(m,u[i])/eulerphi(u[i]))

T(m,n) = Sum_{d|n} (number of elements x such that ord(x,m) = d)/phi(d), where ord(x,m) is the multiplicative order of x modulo m, phi = A000010. There is a version to compute the terms more conveniently, see the links section. [Proof: let (Z/mZ)* denote the multiplicative group modulo m. For every d|n, the elements in (Z/mZ)* having order d are put into different equivalence classes, where each class is of the form {a^k: gcd(k,n)=1}. The size of each equivalence class is the number of different residues modulo d of the numbers that are coprime to n, which is phi(d). - Jianing Song, Sep 17 2022]
Equivalently, T(m,n) = Sum_{d|gcd(n,psi(m))} (number of elements x such that ord(x,m) = d)/phi(d). - Jianing Song, May 16 2022 [This is because the order of elements in (Z/mZ)* must divide psi(m). - Jianing Song, Sep 17 2022]
Let U(m,q) be the number of solutions to x^q == 1 (mod m):
T(m,1) = U(m,1) = 1;
T(m,2) = U(m,2) = A060594(m);
T(m,3) = (1/2)*U(m,3) + (1/2)*U(m,1) = (1/2)*A060839(m) + 1/2;
T(m,4) = (1/2)*U(m,4) + (1/2)*U(m,2) = (1/2)*A073103(m) + 1/2;
T(m,5) = (1/4)*U(m,5) + (3/4)*U(m,1) = (1/4)*A319099(m) + 3/4;
T(m,6) = (1/2)*U(m,6) + (1/2)*U(m,2) = (1/2)*A319100(m) + 1/2;
T(m,7) = (1/6)*U(m,7) + (5/6)*U(m,1) = (1/6)*A319101(m) + 5/6;
T(m,8) = (1/4)*U(m,8) + (1/4)*U(m,4) + (1/2)*U(m,2) = (1/4)*A247257(m) + (1/4)*A073103(m) + (1/2)*A060594(m);
T(m,9) = (1/6)*U(m,9) + (1/3)*U(m,3) + (1/2)*U(m,1);
T(m,10) = (1/4)*U(m,10) + (3/4)*U(m,2).
For odd primes p, T(p^e,n) = d(gcd(n,(p-1)*p^(e-1))), d = A000005; for e >= 3, T(2^e,n) = 2*(min{v2(n),e-2}+1) for even n and 1 for odd n, where v2 is the 2-adic valuation.

cp's OEIS Frontend

A060839 Number of solutions to x^3 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A319099 Number of solutions to x^5 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A329272 Number of octic primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A354057 Square array read by ascending antidiagonals: T(n,k) is the number of solutions to x^k == 1 (mod n).

Views

Author

Keywords

Comments