|
| |
|
|
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
|
|
|
|
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)))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
