TheoremStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

For $\gcd (n, q) = 1$ the reduction of $Φ_{n}$ in $F_{q} [t]$ is a product of distinct monic irreducibles, each of degree the order of $[q]$ modulo $n$

Statement

Let $F_{q}$ be a finite field of order $q$ and let $n \geq 1$ with $\gcd (n, q) = 1$ (Coprime integers: $\gcd (a, b) = 1$ ). Put $d : = ord ([q]_{n})$ , the multiplicative order of $[q]_{n}$ in $(Z / n)^{\times}$ (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ). Then the image of $Φ_{n}$ in $F_{q} [t]$ (The cyclotomic polynomials $Φ_{n} \in Z [t]$ , defined by $\prod_{d ∣ n} Φ_{d} = t^{n} - 1$ ) is a product of pairwise distinct monic irreducible polynomials, each of degree $d$ , and there are $φ (n) / d$ of them.

Facts & Assumptions

Given: A finite field $F_{q}$ of order $q$ , of characteristic $p$ with $q$ a power of $p$ (Every finite field has order $p^{n}$ for a unique prime characteristic $p$ and positive integer $n$ , The characteristic of a ring: the least $n \geq 1$ with $n \cdot 1_{R} = 0$ when one exists, and $0$ otherwise), and $n \geq 1$ with $\gcd (n, q) = 1$ ; hence $p ∤ n$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). Write $E : = F_{q} (μ_{n})$ (The cyclotomic extension $K (μ_{n})$ as a splitting field of $t^{n} - 1$ , Finitely generated field extensions $F (a_{1}, \dots, a_{r})$ ) and ${\overset{ˉ}{Φ}}_{n}$ for the image of $Φ_{n}$ in $F_{q} [t]$ .

[L1]

Over a field $K$ with $char K ∤ n$ and a splitting field $E$ of $t^{n} - 1$ , the image of $Φ_{n}$ in $K [t]$ is separable, splits over $E$ , and its roots in $E$ are exactly the $φ (n)$ primitive $n$ -th roots of unity in $E$ (Over a field whose characteristic does not divide $n$ , the roots of $Φ_{n}$ are exactly the primitive roots of unity, The group $μ_{n} (K)$ of $n$ -th roots of unity in a field, and primitive $n$ -th roots of unity).

[L2]

$Φ_{n}$ is monic of degree $φ (n)$ , and reduction into $F_{q} [t]$ preserves both (The recursion defines a unique monic $Φ_{n} \in Z [t]$ , of degree $φ (n)$ , Degree, leading coefficient and monic polynomial, with the zero polynomial having no degree).

[L3]

$[F_{q} (μ_{n}) : F_{q}] = ord ([q]_{n})$ (For $\gcd (n, q) = 1$ the image of $Gal (F_{q} (μ_{n}) / F_{q})$ in $(Z / n)^{\times}$ is generated by $[q]$ , The degree $[K : F] = \dim_{F} K$ of a finite field extension).

[L4]

For $π \in F_{q} [t]$ monic irreducible of degree $e$ with a root $α$ in an extension field, $F_{q} (α)$ is a finite field of order $q^{e}$ and $[F_{q} (α) : F_{q}] = e$ (A monic irreducible of degree $d$ over $F_{q}$ has the $d$ distinct roots $α, α^{q}, \dots, α^{q^{d - 1}}$ ).

[L5]

$F [x]$ is a unique factorisation domain for every field $F$ (For every field $F$ , $F [x]$ is a unique factorisation domain); irreducible elements are as in Irreducible and prime elements of an integral domain.

[L6]

$f$ is separable over $K$ when no extension field contains an $a$ with $(t - a)^{2}$ dividing the image of $f$ (Repeated roots in extension fields and separable polynomials).

[L7]

Over an integral domain, $\deg (f g) = \deg f + \deg g$ for nonzero $f, g$ (Over an integral domain, degrees add under multiplication of nonzero polynomials).

[L8]

In any field $F$ , the group $μ_{n} (F)$ is cyclic of order dividing $n$ ; if it contains a primitive $n$ -th root of unity, then its order is $n$ , and in that case its generators are exactly the primitive $n$ -th roots of unity ( $μ_{n} (K)$ is cyclic of order dividing $n$ , and has a primitive $n$ -th root of unity exactly when its order is $n$ ).

Proof

technique · direct

1.1

Since $q$ is a power of $p$ and $\gcd (n, q) = 1$ , the prime $p$ does not divide $n$ ; so [L1] applies with $K = F_{q}$ and the splitting field $E = F_{q} (μ_{n})$ , and [L3] gives $[E : F_{q}] = d$ .

L1L3given

1.2

By [L2] the polynomial ${\overset{ˉ}{Φ}}_{n}$ is monic of degree $φ (n) \geq 1$ , so by [L5] it is a product of monic irreducible polynomials of $F_{q} [t]$ , say ${\overset{ˉ}{Φ}}_{n} = π_{1} \dots π_{r}$ with each $π_{i}$ monic irreducible.

L2L5

2.1

Each $π_{i}$ has a root in $E$ . By [L1] the polynomial ${\overset{ˉ}{Φ}}_{n}$ splits over $E$ into $φ (n)$ distinct linear factors, and $π_{i}$ divides it; since $E [t]$ is a unique factorisation domain by [L5], $π_{i}$ is, up to a unit, a product of some of those linear factors. Thus it has a root $α_{i} \in E$ , and $α_{i}$ is a primitive $n$ -th root of unity by [L1].

step 1.2L1L5

3.1

No two of the $π_{i}$ coincide. If $π_{i} = π_{j} = π$ for $i \neq j$ , then $π^{2}$ divides ${\overset{ˉ}{Φ}}_{n}$ . By step 2.1 the polynomial $π$ has a linear factor $t - α$ in $E [t]$ , so $(t - α)^{2}$ divides ${\overset{ˉ}{Φ}}_{n}$ there, contradicting the separability supplied by [L1] and [L6].

step 1.2step 2.1L1L5L6

3.2

Every $π_{i}$ has degree $d$ . Writing $e_{i} : = \deg π_{i}$ , [L4] gives $[F_{q} (α_{i}) : F_{q}] = e_{i}$ . Since $α_{i}$ is primitive, [L8] makes $μ_{n} (E)$ a cyclic group of order $n$ with generators exactly the primitive $n$ -th roots, so $α_{i}$ generates $μ_{n} (E)$ . Hence $μ_{n} (E) \subseteq F_{q} (α_{i})$ and therefore $E = F_{q} (μ_{n} (E)) \subseteq F_{q} (α_{i})$ ; and $α_{i} \in E$ gives $F_{q} (α_{i}) \subseteq E$ . Thus $F_{q} (α_{i}) = E$ and $e_{i} = [E : F_{q}] = d$ by step 1.1.

step 1.1step 2.1L4L8

4.1

Comparing degrees with [L7] and [L2], $φ (n) = \deg {\overset{ˉ}{Φ}}_{n} = \sum_{i = 1}^{r} e_{i} = r d$ , so $r = φ (n) / d$ ; with steps 3.1 and 3.2 this is the assertion.

step 1.2step 3.1step 3.2L2L7∎

Remarks

The degree of every factor is the same, and that is the content. A polynomial can factor into irreducibles of different degrees; here it cannot, because adjoining any primitive root produces the same field $F_{q} (μ_{n})$ . The primitive roots need not form a single Frobenius orbit: for $n = 7$ over $F_{2}$ they split into two orbits of size three, one for each irreducible cubic factor on the companion page.

Depends on

Used by

The reduction of Φₙ is irreducible over F_q exactly when [q] generates (ℤ/n)^× Corollary
Φ₅ has four roots in F₁₁ Example
Φ₇ factors over F₂ into the two monic irreducible cubics Example
FALSE: Φₙ is irreducible over every field False statement

Dependency tree · two levels

98 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

K. Conrad, Cyclotomic Extensions (expository blurb), Theorem 5.4 (standard reference, not scraped)
K. Conrad, Finite Fields (expository blurb), Theorem 5.5 (standard reference, not scraped)

For gcd⁡(n,q)=1gcd(n,q)=1 the reduction of ΦnΦn​ in Fq[t]Fq​[t] is a product of distinct monic irreducibles, each of degree the order of [q][q] modulo nn