The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #52 Jul 21 2024 12:49:12
%S 1,1,1,1,1,1,1,1,2,2,1,1,2,1,1,1,1,1,2,1,1,1,1,2,2,2,2,2,1,1,1,1,4,2,
%T 1,4,1,1,2,2,1,1,2,2,1,1,1,1,2,1,2,1,4,6,1,1,1,2,1,2,1,6,2,2,1,1,1,1,
%U 2,2,4,2,6,2,1,2,2,2,1,1,1,2,1,1,2,4,2,4,2,2,1
%N Square array read by ascending antidiagonals: T(n,m) is the number of irreducible factors in the factorization of the m-th cyclotomic polynomial over GF(k), k = A246655(n) (counted with multiplicity).
%C T(n,m) = 1 if and only if (let k = A246655(n)):
%C (a) gcd(m,k) = 1, and k is a primitive root modulo m;
%C (b) k is a power of 2, m == 2 (mod 4), and k is a primitive root modulo m/2.
%C As a result, T(n,m) > 1 if at least one of the following holds:
%C (i) There is no primitive root modulo m, that is, m is in A033949;
%C (ii) k is a square number and m > 2.
%C If p = A246655(n) is prime, then T(n,m) is also the number of irreducible factors in the factorization of the ideal (p) in Z[zeta_m], zeta_m = exp(2*Pi*i/m). Actually, if the m-th cyclotomic polynomial factors as Product_{i=1..T(n,m)} F_i(x) over GF(p), then the factorization of (p) in Z[zeta_m] is (p) = Product_{i=1..T(n,m)} (p,F_i(zeta_m)). As a result, p remains inert in Q(zeta_m) <=> T(n,m) = 1. See Page 47-48, Proposition 8.3 and Page 61-62, Proposition 10.3 of the Neukirch link for a proof. - _Jianing Song_, Sep 13 2022
%H Amiram Eldar, <a href="/A327818/b327818.txt">Table of n, a(n) for n = 1..10011</a> (antidiagonals n = 1..141, flattened)
%H Jürgen Neukirch, <a href="http://www.math.toronto.edu/~ila/Neukirch_Algebraic_number_theory.pdf">Algebraic_number_theory</a>.
%H Jianing Song, <a href="/A327818/a327818_2.pdf">My notes on the factorization of cyclotomic polynomials over finite fields</a>.
%H Hongfeng Wu, Li Zhu, Rongquan Feng, and Siman Yang, <a href="https://doi.org/10.1007/s10623-016-0224-5">Explicit factorizations of cyclotomic polynomials over finite fields</a>, Des. Codes Cryptogr. 83, 197-217 (2017).
%F Let m = p^e*s, where p is the prime factor of k = A246655(n), gcd(p,s) = 1, then T(n,m) = phi(m)/ord(k,s), where phi = A000010, ord(k,s) is the multiplicative order of k modulo s. Proof:
%F (a) First consider the case e = 0. Let F be the algebraic closure of GF(k), then Phi_s(x) = 0 has solutions in F, where Phi_s(x) is the s-th cyclotomic polynomial. Let a be any of the solution.
%F In F, a belongs to GF(k^d) <=> a^(k^d-1) = 1 <=> s|(k^d-1) (note that in F, s is the smallest integer such that a^s = 1). As a result, a belongs to GF(k^ord(k,s)) but not to GF(k^d) for any d < ord(k,s), that is to say, a has algebraic degree ord(k,s) over GF(k). Because a is any of the roots of Phi_s(x) in F, every irreducible factor of Phi_s(x) over GF(k) is of degree ord(k,s), so the number of irreducible factors is phi(s)/ord(k,s);
%F (b) If e > 0, we can see from the Moebius inversion formula such that Phi_m(x) = (Phi_s(x))^phi(p^e), that the number of irreducible factors is phi(m)/ord(k,s).
%F The Introduction part in Page 2 and Lemma 1 in Page 3 of Hongfeng Wu's paper (see Links section) also mentions part (a) of this result.
%e Table starts
%e n A246655(n) m=1 2 3 4 5 6 7 8 9 10
%e 1 2 1 1 1 2 1 1 2 4 1 1
%e 2 3 1 1 2 1 1 2 1 2 6 1
%e 3 4 1 1 2 2 2 2 2 4 2 2
%e 4 5 1 1 1 2 4 1 1 2 1 4
%e 5 7 1 1 2 1 1 2 6 2 2 1
%e 6 8 1 1 1 2 1 1 6 4 3 1
%e 7 9 1 1 2 2 2 2 2 4 6 2
%e 8 11 1 1 1 1 4 1 2 2 1 4
%t T[max_] := Module[{pp = Select[Range[max], PrimePowerQ], m, t}, m = Length[pp]; t[i_, j_] := Module[{p = FactorInteger[pp[[j]]][[1, 1]]}, EulerPhi[i] / MultiplicativeOrder[pp[[j]], i/p^IntegerExponent[i, p]]]; Table[t[j, i - j + 1], {i, 1, m}, {j, 1, i}] // Flatten]; T[24] (* _Amiram Eldar_, Jul 21 2024 *)
%o (PARI) f(k,m) = if(isprimepower(k), my(p=factor(k)[1,1], s=m/p^valuation(m,p)); eulerphi(m)/znorder(Mod(k,s)))
%o A246655(n) = my(i=0); for(t=1, oo, if(isprimepower(t), i++); if(i==n, return(t)))
%o a(n,m) = f(A246655(n),m)
%Y Cf. A246655, A000010, A033949.
%Y Rows 1..7 give: A318622, A327812, A327813, A327814, A327815, A327816, A327817.
%K nonn,easy,tabl
%O 1,9
%A _Jianing Song_, Sep 26 2019