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

Comments

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]

Links

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.

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

(PARI) a(n)=sum(i=1, n, if((i^3-1)%n, 0, 1))
(Python)
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
(PARI) 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

Crossrefs

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.

Sequence in context: A370414 A016472 A095346 * A088204 A100375 A353063

Adjacent sequences: A060836 A060837 A060838 * A060840 A060841 A060842

Keyword

nonn,nice,easy,mult

Author

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

Status

approved