cp's OEIS Frontend

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

%I A318622 #31 Mar 17 2025 05:36:48
%S A318622 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,
%T A318622 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,
%U A318622 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
%N A318622 Number of irreducible factors in the factorization of the n-th cyclotomic polynomial over GF(2) (counted with multiplicity).
%C A318622 From _Jianing Song_, Sep 13 2022: (Start)
%C A318622 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.
%C A318622 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.
%C A318622 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.
%C A318622 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)
%H A318622 Robert Israel, <a href="/A318622/b318622.txt">Table of n, a(n) for n = 1..10000</a>
%H A318622 Jürgen Neukirch, <a href="http://www.math.toronto.edu/~ila/Neukirch_Algebraic_number_theory.pdf">Algebraic_number_theory</a>
%H A318622 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%F A318622 a(n) = A000010(n)/A002326((A000265(n)-1)/2).
%F A318622 A091248(n) = Sum_{d|n} a(d).
%p A318622 f:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2, n/2^padic:-ordp(n, 2)) end proc:
%p A318622 map(f, [$1..200]);
%t A318622 a[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* _Jean-François Alcover_, Apr 27 2019 *)
%o A318622 (PARI) a(n) = eulerphi(n)/znorder(Mod(2, (n >> valuation(n, 2)))); \\ _Michel Marcus_, Apr 27 2019
%Y A318622 Cf. A000010, A000265, A002326, A091248, A129832 (a(n)=1).
%Y A318622 Row 1 of A327818.
%K A318622 nonn
%O A318622 1,4
%A A318622 _Robert Israel_, Aug 30 2018