A354057 -id:A354057 - 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

A354058 Square array read by ascending antidiagonals: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 3, 0, 1, 0, 1, 0, 2, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 2, 2, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 5, 0, 3, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 1

Offset: 1

Jianing Song, May 16 2022

Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354061.
Each column is multiplicative.
The n-th rows contains entirely 0's if and only if n == 2 (mod 4).
For n !== 2 (mod 4), T(n,psi(n)) > T(n,k) if k is not divisible by psi(n).
Proof: this is true if n is a prime power (see the formula below). Now suppose that n = Product_{i=1..r} (p_i)^(e_i). Since n !== 2 (mod 4), (p_i)^(e_i) != 2, so T((p_i)^(e_i),psi((p_i)^(e_i))) > 0 for each i. If k is not divisible by psi(n), then it is not divisible by some psi((p_{i_0})^(e_{i_0})), so T(n,psi(n)) = Product_{i=1..r} T((p_i)^(e_i),psi(n)) = Product_{i=1..r} T((p_i)^(e_i),psi((p_i)^(e_i))) > T((p_{i_0})^(e_{i_0}),k) * Product_{i!=i_0} T((p_i)^(e_i),psi((p_i)^(e_i))) >= Product_{i=1..r} T((p_i)^(e_i),k) = T(n,k).

			  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   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   3   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
   4   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
   5   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3
   6   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   7   0  1  2  1  0  5  0  1  2  1  0  5  0  1  2  1  0  5  0  1
   8   0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2
   9   0  0  2  0  0  4  0  0  2  0  0  4  0  0  2  0  0  4  0  0
  10   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  11   0  1  0  1  4  1  0  1  0  9  0  1  0  1  4  1  0  1  0  9
  12   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
  13   0  1  2  3  0  5  0  3  2  1  0 11  0  1  2  3  0  5  0  3
  14   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  15   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3
  16   0  0  0  4  0  0  0  4  0  0  0  4  0  0  0  4  0  0  0  4
  17   0  1  0  3  0  1  0  7  0  1  0  3  0  1  0 15  0  1  0  3
  18   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  19   0  1  2  1  0  5  0  1  8  1  0  5  0  1  2  1  0 17  0  1
  20   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3

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

k-th column: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), A307381 (k=6), A307382 (k=7), A329272 (k=8).
Moebius transform of A354057 applied to each column.
A354257 gives the smallest index for the nonzero terms in each row.
Cf. A007431.

b(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]));
T(n,k) = sumdiv(n, d, moebius(n/d)*b(d,k))

For odd primes p: T(p,k) = gcd(p-1,k)-1, T(p^e,k*p^(e-1)) = p^(e-2)*(p-1)*gcd(k,p-1), T(p^e,k) = 0 if k is not divisible by p^(e-1). T(2,k) = 0, T(4,k) = 1 for even k and 0 for odd k, T(2^e,k) = 2^(e-2) if k is divisible by 2^(e-2) and 0 otherwise.

T(n,psi(n)) = A007431(n). - Jianing Song, May 24 2022

A354060 Irregular table read by rows: T(n,k) is the number of solutions to x^k == 1 (mod n), 1 <= k <= psi(n), psi = A002322.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 6, 1, 4, 1, 2, 3, 2, 1, 6, 1, 2, 1, 4, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 4, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 2, 1, 6, 1, 4, 1, 8, 1, 4, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16

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

Given n, T(n,k) only depends on gcd(k,psi(n)).

			Table starts
n = 1: 1;
n = 2: 1;
n = 3: 1, 2;
n = 4: 1, 2;
n = 5: 1, 2, 1, 4;
n = 6: 1, 2;
n = 7: 1, 2, 3, 2, 1, 6;
n = 8: 1, 4;
n = 9: 1, 2, 3, 2, 1, 6;
n = 10: 1, 2, 1, 4;
n = 11: 1, 2, 1, 2, 5, 2, 1, 2, 1, 10;
n = 12: 1, 4;
n = 13: 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12;
n = 14: 1, 2, 3, 2, 1, 6;
n = 15: 1, 4, 1, 8;
n = 16: 1, 4, 1, 8;
n = 17: 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16;
n = 18: 1, 2, 3, 2, 1, 6;
n = 19: 1, 2, 3, 2, 1, 6, 1, 2, 9, 2, 1, 6, 1, 2, 3, 2, 1, 18;
n = 20: 1, 4, 1, 8;
...

Jianing Song, Table of n, a(n) for n = 1..8346 (the first 200 rows)

Cf. A354057, A002322, A354061.

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.

A354059 Square array read by ascending antidiagonals: T(n,k) is the number of elements in the multiplicative group of integers modulo n that have order k.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 0, 0, 0, 1, 3, 2, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0

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.

For the truncated version see A252911.

			The 7th, 9th, 14th and 18th rows of A354047 are {1,2,3,2,1,6,1,2,3,2,1,6,...}, so applying the Moebius transform gives {1,1,2,0,0,2,0,0,0,0,0,0,...}.

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

Moebius transform of A354057 applied to each row.

Cf. A327924.

b(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]));
T(n,k) = sumdiv(k, d, moebius(k/d)*b(n,d))

A327924(n,k) = Sum_{d|k} T(n,k)/phi(d).

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

A354058 Square array read by ascending antidiagonals: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354060 Irregular table read by rows: T(n,k) is the number of solutions to x^k == 1 (mod n), 1 <= k <= psi(n), psi = A002322.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354059 Square array read by ascending antidiagonals: T(n,k) is the number of elements in the multiplicative group of integers modulo n that have order k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula