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

1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 1, 2, 2, 8, 2, 1, 1, 2, 2, 1, 2, 4, 1, 1, 1, 4, 1, 2, 6, 16, 2, 2, 2, 2, 1, 1, 2, 4, 2, 2, 3, 2, 2, 2, 2, 8, 2, 1, 4, 2, 1, 1, 2, 8, 2, 1, 1, 4, 1, 6, 6, 32, 4, 2, 1, 4, 2, 2, 2, 4, 8, 1, 2, 2, 2, 2, 2, 8, 1, 2, 1, 4, 8, 3, 2, 4, 8, 2, 6, 4, 6, 2, 2, 16, 2, 2

Offset: 1

Author

Robert Israel, Aug 30 2018

Keywords

• nonn

Comments

From Jianing Song, Sep 13 2022: (Start)

a(n) is also the number of irreducible factors in the factorization of the ideal (2) in Z[zeta_n], zeta_n = exp(2*Pi*i/n). Actually, if the n-th cyclotomic polynomial factors as Product_{i=1..a(n)} F_i(x) over GF(2), then the factorization of (2) in Z[zeta_m] is (p) = Product_{i=1..T(n,m)} (2,F_i(zeta_m)). See Page 47-48, Proposition 8.3 and Page 61-62, Proposition 10.3 of the Neukirch link for a proof; see also A327818.

As a result, 2 remains inert in Q(zeta_n) <=> a(n) = 1, which happens if and only if either n is odd, 2 is a primitive root modulo n, or n == 2 (mod 4), 2 is a primitive root modulo n/2.

Example 1: Phi_8(x) = x^4+1 == (x+1)^4 (mod 2), so in Z[zeta_8] = Z[i,sqrt(2)] we have (2) = (2,(zeta_8)+1)^4 = ((zeta_8)+1)^4. In fact we have 2 = -i*(3-2*sqrt(2)) * ((zeta_8)+1)^4.

Example 2: Phi_12(x) = x^4-x^2+1 == (x^2+x+1)^2 (mod 2), so in Z[zeta_12] = Z[i,sqrt(3)] we have (2) = (2,(zeta_12)^2+(zeta_12)+1)^2 = ((zeta_12)^2+(zeta_12)+1)^2. In fact we have 2 = (2-sqrt(3)) * (1-sqrt(-3))/2 * ((zeta_12)^2+(zeta_12)+1)^2. (End)

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Jürgen Neukirch, Algebraic_number_theory
• Index entries for sequences operating on GF(2)[X]-polynomials

Crossrefs

Cf. A000010, A000265, A002326, A091248, A129832 (a(n)=1).

Row 1 of A327818.

Programs

Maple

f:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2, n/2^padic:-ordp(n, 2)) end proc:
map(f, [$1..200]);

Mathematica

a[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* Jean-François Alcover, Apr 27 2019 *)

PARI

a(n) = eulerphi(n)/znorder(Mod(2, (n >> valuation(n, 2)))); \\ Michel Marcus, Apr 27 2019

Formula

a(n) = A000010(n)/A002326((A000265(n)-1)/2).

A091248(n) = Sum_{d|n} a(d).