

A319100


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


15



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

All terms are 3smooth. a(n) is even for n > 2. Those n such that a(n) = 2 are in A066501.


LINKS

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


FORMULA

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*p4)/(p+1)^3) = 0.0075925601... (Finch et al., 2010).  Amiram Eldar, Mar 26 2021


EXAMPLE

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


PROG

(PARI) a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(6, Z[i]))


CROSSREFS

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.
Sequence in context: A355192 A260983 A103222 * A304794 A175809 A061033
Adjacent sequences: A319097 A319098 A319099 * A319101 A319102 A319103


KEYWORD

nonn,easy,mult


AUTHOR

Jianing Song, Sep 10 2018


STATUS

approved



