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

%I #47 Aug 10 2023 02:22:29

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

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

%U 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

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

%C 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]

%H T. D. Noe, <a href="/A060839/b060839.txt">Table of n, a(n) for n = 1..1000</a>

%H Steven Finch, Greg Martin and Pascal Sebah, <a href="https://doi.org/10.1090/S0002-9939-10-10341-4">Roots of unity and nullity modulo n</a>, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.

%H Steven Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.

%F 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.

%F 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]

%F 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

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

%p A060839 := proc(n)

%p local a,pf,p,r;

%p a := 1 ;

%p for pf in ifactors(n)[2] do

%p p := op(1,pf);

%p r := op(2,pf);

%p if p = 2 then

%p ;

%p elif p =3 then

%p if r >= 2 then

%p a := a*3 ;

%p end if;

%p else

%p if modp(p,3) = 2 then

%p ;

%p else

%p a := 3*a ;

%p end if;

%p end if;

%p end do:

%p a ;

%p end proc:

%p seq(A060839(n),n=1..40) ; # _R. J. Mathar_, Mar 02 2015

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

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

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

%o (Python)

%o from math import prod

%o from sympy import factorint

%o 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

%o (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

%Y Cf. A005088, A357905 (base-3 logarithm).

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

%Y Column 3 of A354057.

%K nonn,nice,easy,mult

%O 1,7

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