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

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

Offset: 1

Author

Jianing Song, Sep 10 2018

Keywords

• nonn
• easy
• mult

Comments

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

Examples

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

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. 2729-2743.

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.

Programs

PARI

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

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