|
| |
|
|
A318622
|
|
Number of irreducible factors in the factorization of the n-th cyclotomic polynomial over GF(2) (counted with multiplicity).
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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
|
|
|
|
FORMULA
|
|
|
|
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 *)
|
|
|
PROG
|
(PARI) a(n) = eulerphi(n)/znorder(Mod(2, (n >> valuation(n, 2)))); \\ Michel Marcus, Apr 27 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
