The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A327818 Square array read by ascending diagonals: 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). 8
 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, 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, 2, 2, 4, 2, 6, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 4, 2, 4, 2, 2, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,9 COMMENTS T(n,m) = 1 if and only if (let k = A246655(n)): (a) gcd(m,k) = 1, and k is a primitive root modulo m; (b) k is a power of 2, m == 2 (mod 4), and k is a primitive root modulo m/2. As a result, T(n,m) > 1 if at least one of the following holds: (i) There is no primitive root modulo m, that is, m is in A033949; (ii) k is a square number and m > 2. 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 LINKS Table of n, a(n) for n=1..91. Jianing Song, My notes on the factorization of cyclotomic polynomials over finite fields Jürgen Neukirch, Algebraic_number_theory Hongfeng Wu, Li Zhu, Rongquan Feng, Siman Yang, Explicit factorizations of cyclotomic polynomials over finite fields, Des. Codes Cryptogr. 83, 197-217 (2017). FORMULA 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: (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. 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); (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). 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. EXAMPLE Table starts n A246655(n) m=1 2 3 4 5 6 7 8 9 10 1 2 1 1 1 2 1 1 2 4 1 1 2 3 1 1 2 1 1 2 1 2 6 1 3 4 1 1 2 2 2 2 2 4 2 2 4 5 1 1 1 2 4 1 1 2 1 4 5 7 1 1 2 1 1 2 6 2 2 1 6 8 1 1 1 2 1 1 6 4 3 1 7 9 1 1 2 2 2 2 2 4 6 2 8 11 1 1 1 1 4 1 2 2 1 4 PROG (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))) A246655(n) = my(i=0); for(t=1, oo, if(isprimepower(t), i++); if(i==n, return(t))) a(n, m) = f(A246655(n), m) CROSSREFS Cf. A246655, A000010, A033949. Rows 1..7 give: A318622, A327812, A327813, A327814, A327815, A327816, A327817. Sequence in context: A037810 A335211 A038769 * A255481 A241418 A330348 Adjacent sequences: A327815 A327816 A327817 * A327819 A327820 A327821 KEYWORD nonn,easy,tabl AUTHOR Jianing Song, Sep 26 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 30 15:15 EDT 2023. Contains 365792 sequences. (Running on oeis4.)