A327817 Number of irreducible factors in the factorization of the n-th cyclotomic polynomial over GF(9) (counted with multiplicity).

1, 1, 2, 2, 2, 2, 2, 4, 6, 2, 2, 4, 4, 2, 4, 4, 2, 6, 2, 4, 4, 2, 2, 8, 2, 4, 18, 4, 2, 4, 2, 4, 4, 2, 4, 12, 4, 2, 8, 8, 10, 4, 2, 4, 12, 2, 2, 8, 2, 2, 4, 8, 2, 18, 4, 8, 4, 2, 2, 8, 12, 2, 12, 4, 8, 4, 6, 4, 4, 4, 2, 24, 12, 4, 4, 4, 4, 8, 2, 16, 54, 10, 2, 8, 8, 2, 4, 8, 2, 12

Offset: 1

Author

Jianing Song, Sep 26 2019

Keywords

• nonn
• easy

Examples

			Let GF(9) = GF(3)[i], where i^2 = -1. Factorizations of the n-th cyclotomic polynomial over GF(9) for n <= 10:
n = 1: x - 1;
n = 2: x + 1;
n = 3: (x - 1)^2;
n = 4: (x + i)*(x - i);
n = 5: (x^2 + (-1+i)*x + 1)*(x^2 + (-1-i)*x + 1);
n = 6: (x + 1)^2;
n = 7: (x^3 + (-1+i)*x^2 + (1+i)*x - 1)*(x^3 + (-1-i)*x^2 + (1-i)*x - 1);
n = 8: (x + (1+i))*(x + (1-i))*(x + (-1+i))*(x + (-1-i));
n = 9: (x - 1)^6;
n = 10: (x^2 + (1+i)*x + 1)*(x^2 + (1-i)*x + 1).
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010.

Row 7 of A327818.

Programs

Mathematica

a[n_] := EulerPhi[n] / MultiplicativeOrder[9, n / 3^IntegerExponent[n, 3]]; Array[a, 100] (* Amiram Eldar, Jul 21 2024 *)

PARI

a(n) = my(s=n/3^valuation(n, 3)); eulerphi(n)/znorder(Mod(9, s))

Formula

Let n = 3^e*s, gcd(3,s) = 1, then a(n) = phi(n)/ord(9,s), where phi = A000010, ord(k,s) is the multiplicative order of k modulo s. See A327818 for further information.