%I #26 Mar 26 2021 08:39:04
%S 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,
%T 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,
%U 4,12,4,6,4,4,12,2,24,6,6,4,12,12,12,6,8,6,2
%N Number of solutions to x^6 == 1 (mod n).
%C All terms are 3-smooth. a(n) is even for n > 2. Those n such that a(n) = 2 are in A066501.
%H Jianing Song, <a href="/A319100/b319100.txt">Table of n, a(n) for n = 1..10000</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.
%F 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).
%F 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).
%F a(n) = A060594(n)*A060839(n).
%F For n > 2, a(n) = A060839(n)*2^A046072(n).
%F 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.
%F a(n) = A000010(n)/A293483(n). - _Jianing Song_, Nov 10 2019
%F 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
%e Solutions to x^6 == 1 (mod 13): x == 1, 3, 4, 9, 10, 12 (mod 13).
%e Solutions to x^6 == 1 (mod 27): x == 1, 8, 10, 17, 19, 26 (mod 27) (x == 1, 8 (mod 9)).
%e Solutions to x^6 == 1 (mod 37): x == 1, 10, 11, 26, 27, 36 (mod 37).
%o (PARI) a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(6, Z[i]))
%Y 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).
%Y Cf. A046072, A066501, A088232, A293483, A000010.
%Y Mobius transform gives A307381.
%K nonn,easy,mult
%O 1,3
%A _Jianing Song_, Sep 10 2018