[proofplan] We argue by contradiction. Suppose $\Phi_n$ factors non-trivially in $\mathbb{Q}[t]$ and let $P$ be the minimal polynomial of a fixed primitive $n$-th root of unity $\zeta$ over $\mathbb{Q}$, so that $P \mid \Phi_n$ in $\mathbb{Z}[t]$ with $\deg P < \deg \Phi_n$. We show that for every prime $q \nmid n$, if $\zeta$ is a root of $P$ then so is $\zeta^q$. Since every primitive $n$-th root of unity can be reached from $\zeta$ by iterated multiplication by primes coprime to $n$, this forces $P$ to have all primitive $n$-th roots as roots, contradicting $\deg P < \deg \Phi_n$. The core argument for the $\zeta \mapsto \zeta^q$ step uses reduction modulo $q$: the Frobenius endomorphism of $\mathbb{F}_q[t]$ converts $\bar{R}(t^q)$ into $\bar{R}(t)^q$, forcing $\bar{P}$ and $\bar{R}$ to share a common factor; but $\bar{\Phi}_n$ divides $t^n - 1$ in $\mathbb{F}_q[t]$, and $t^n - 1$ is separable over $\mathbb{F}_q$ when $q \nmid n$, yielding a contradiction. [/proofplan] [step:Factor $\Phi_n$ over $\mathbb{Z}$ and isolate the minimal polynomial of $\zeta$] By Gauss's Lemma, if $\Phi_n$ factors non-trivially over $\mathbb{Q}$, it factors non-trivially over $\mathbb{Z}$. (Gauss's Lemma states that a primitive polynomial in $\mathbb{Z}[t]$ that is reducible in $\mathbb{Q}[t]$ is reducible in $\mathbb{Z}[t]$. The polynomial $\Phi_n$ is monic with integer coefficients, hence primitive.) Suppose for contradiction that $\Phi_n$ is reducible over $\mathbb{Q}$. Let $\zeta \in \mathbb{C}$ be a primitive $n$-th root of unity and let $P := \operatorname{min}_{\mathbb{Q}}(\zeta) \in \mathbb{Z}[t]$ be the minimal polynomial of $\zeta$ over $\mathbb{Q}$. Since $\zeta$ is a root of $\Phi_n$ and $P$ is the minimal polynomial, $P \mid \Phi_n$ in $\mathbb{Q}[t]$, and by Gauss's Lemma the division holds in $\mathbb{Z}[t]$. Write \begin{align*} \Phi_n = P \cdot R \end{align*} in $\mathbb{Z}[t]$, where $R \in \mathbb{Z}[t]$ and $\deg P < \deg \Phi_n$, so $\deg R \ge 1$. Since $\Phi_n$ is monic, both $P$ and $R$ are monic (their leading coefficients multiply to $1$ in $\mathbb{Z}$, so both equal $1$). [guided] Our goal is to reduce the problem to one over $\mathbb{Z}[t]$, where we can exploit reduction modulo primes. The cyclotomic polynomial $\Phi_n$ is defined as \begin{align*} \Phi_n(t) := \prod_{\substack{1 \le k \le n \\ \gcd(k,n) = 1}} (t - \zeta^k), \end{align*} where $\zeta = e^{2\pi i/n}$. It is a standard result that $\Phi_n \in \mathbb{Z}[t]$ and is monic of degree $\varphi(n)$. We assume for contradiction that $\Phi_n$ is reducible over $\mathbb{Q}$. The connection between reducibility over $\mathbb{Q}$ and over $\mathbb{Z}$ is provided by Gauss's Lemma: a primitive polynomial in $\mathbb{Z}[t]$ is irreducible over $\mathbb{Z}$ if and only if it is irreducible over $\mathbb{Q}$. The polynomial $\Phi_n$ is monic, hence primitive (the gcd of its coefficients is $1$ since the leading coefficient is $1$). Therefore reducibility over $\mathbb{Q}$ implies reducibility over $\mathbb{Z}$. Let $P = \operatorname{min}_{\mathbb{Q}}(\zeta)$. Since $P$ is the minimal polynomial of an algebraic integer $\zeta$ (a root of the monic polynomial $t^n - 1 \in \mathbb{Z}[t]$), $P$ is monic with integer coefficients. The divisibility $P \mid \Phi_n$ in $\mathbb{Q}[t]$ then lifts to $P \mid \Phi_n$ in $\mathbb{Z}[t]$ (since $P$ is monic, polynomial long division in $\mathbb{Z}[t]$ produces an integer quotient). We write $\Phi_n = P \cdot R$ with $R \in \mathbb{Z}[t]$ monic and $\deg R \ge 1$. The roots of $P$ are a proper subset of the primitive $n$-th roots of unity (those in the $\operatorname{Gal}(\mathbb{Q}(\zeta)/\mathbb{Q})$-orbit of $\zeta$ corresponding to the factor $P$), and the roots of $R$ are the remaining primitive $n$-th roots of unity. [/guided] [/step] [step:Show that if $\zeta$ is a root of $P$ then $\zeta^q$ is a root of $P$ for every prime $q \nmid n$] Let $q$ be a prime with $q \nmid n$. We prove that $P(\zeta^q) = 0$. Suppose for contradiction that $P(\zeta^q) \ne 0$. Since $\zeta^q$ is also a primitive $n$-th root of unity ($\gcd(q, n) = 1$ ensures that $\zeta^q$ has order $n$), and every root of $\Phi_n$ is either a root of $P$ or a root of $R$, the assumption $P(\zeta^q) \ne 0$ forces $R(\zeta^q) = 0$. Now $\zeta$ is a root of the polynomial $R(t^q) \in \mathbb{Z}[t]$: substituting $t = \zeta$ gives $R(\zeta^q) = 0$. Since $P = \operatorname{min}_{\mathbb{Q}}(\zeta)$, we have $P \mid R(t^q)$ in $\mathbb{Q}[t]$, and since both are monic polynomials in $\mathbb{Z}[t]$, the division holds in $\mathbb{Z}[t]$. Write \begin{align*} R(t^q) = P(t) \cdot S(t) \end{align*} for some $S \in \mathbb{Z}[t]$. Reduce this equation modulo $q$. Let $\bar{f}$ denote the image of $f \in \mathbb{Z}[t]$ in $\mathbb{F}_q[t]$. In $\mathbb{F}_q[t]$, the Frobenius endomorphism gives $\bar{R}(t^q) = \bar{R}(t)^q$: for $\bar{R}(t) = \sum a_i t^i \in \mathbb{F}_q[t]$, we have \begin{align*} \bar{R}(t^q) = \sum a_i t^{iq} = \sum a_i^q t^{iq} = \left(\sum a_i t^i\right)^q = \bar{R}(t)^q, \end{align*} where the second equality uses $a_i^q = a_i$ in $\mathbb{F}_q$ (Fermat's Little Theorem) and the third uses the binomial theorem in characteristic $q$ (all cross-terms have coefficients divisible by $q$, hence vanish in $\mathbb{F}_q$). Therefore in $\mathbb{F}_q[t]$: \begin{align*} \bar{R}(t)^q = \bar{R}(t^q) = \bar{P}(t) \cdot \bar{S}(t). \end{align*} This means $\bar{P}$ divides $\bar{R}(t)^q$ in $\mathbb{F}_q[t]$. Let $\bar{h}$ be an irreducible factor of $\bar{P}$ in $\mathbb{F}_q[t]$. Then $\bar{h} \mid \bar{R}(t)^q$, and since $\bar{h}$ is irreducible over the field $\mathbb{F}_q$, unique factorisation in $\mathbb{F}_q[t]$ gives $\bar{h} \mid \bar{R}$. Therefore $\bar{h}$ divides both $\bar{P}$ and $\bar{R}$, so $\bar{h}^2 \mid \bar{P} \cdot \bar{R} = \bar{\Phi}_n$. Since $\Phi_n \mid t^n - 1$ in $\mathbb{Z}[t]$ (by the factorisation $t^n - 1 = \prod_{d \mid n} \Phi_d$), the reduction gives $\bar{\Phi}_n \mid t^n - 1$ in $\mathbb{F}_q[t]$. Therefore $\bar{h}^2 \mid t^n - 1$ in $\mathbb{F}_q[t]$, meaning $t^n - 1$ has a repeated factor over $\mathbb{F}_q$. We show this is impossible. The formal derivative of $t^n - 1$ is $nt^{n-1}$. Since $q \nmid n$, the element $n$ is a unit in $\mathbb{F}_q$, so $nt^{n-1} \ne 0$ in $\mathbb{F}_q[t]$. The polynomials $t^n - 1$ and $nt^{n-1}$ share a common root in $\overline{\mathbb{F}_q}$ only if some $\alpha$ satisfies both $\alpha^n = 1$ and $n\alpha^{n-1} = 0$. Since $n \ne 0$ in $\mathbb{F}_q$ and $\alpha^{n-1} \ne 0$ (as $\alpha^n = 1$ implies $\alpha \ne 0$), no such $\alpha$ exists. Therefore $\gcd(t^n - 1, nt^{n-1}) = 1$ in $\mathbb{F}_q[t]$, which implies $t^n - 1$ is separable over $\mathbb{F}_q$ — it has no repeated irreducible factors. This contradicts $\bar{h}^2 \mid t^n - 1$. The contradiction arose from assuming $P(\zeta^q) \ne 0$, so $P(\zeta^q) = 0$. [guided] This is the heart of the proof. We want to show that the set of primitive $n$-th roots of unity that are roots of $P$ is closed under the map $\zeta \mapsto \zeta^q$ for every prime $q$ coprime to $n$. The strategy is to assume $\zeta^q$ is NOT a root of $P$, derive an algebraic consequence in $\mathbb{Z}[t]$, and then reduce modulo $q$ to obtain a contradiction with the separability of $t^n - 1$ over $\mathbb{F}_q$. **Setting up the divisibility in $\mathbb{Z}[t]$.** Assume $P(\zeta^q) \ne 0$. Since $\gcd(q, n) = 1$ (as $q$ is prime and $q \nmid n$), the element $\zeta^q$ still has order $n$ in $\mathbb{C}^\times$: if $(\zeta^q)^m = 1$ then $n \mid qm$, and $\gcd(q, n) = 1$ gives $n \mid m$, so $\operatorname{ord}(\zeta^q) = n$. Therefore $\zeta^q$ is a primitive $n$-th root of unity, hence a root of $\Phi_n = P \cdot R$. Since $P(\zeta^q) \ne 0$ by assumption, we must have $R(\zeta^q) = 0$. Consider the polynomial $R(t^q) \in \mathbb{Z}[t]$. Evaluating at $t = \zeta$: $R(\zeta^q) = 0$, so $\zeta$ is a root of $R(t^q)$. Since $P = \operatorname{min}_\mathbb{Q}(\zeta)$ divides every polynomial in $\mathbb{Q}[t]$ that vanishes at $\zeta$, we get $P \mid R(t^q)$ in $\mathbb{Q}[t]$. Since $P$ is monic and both $P, R(t^q) \in \mathbb{Z}[t]$, polynomial long division in $\mathbb{Z}[t]$ (using the monic leading term) shows $R(t^q) = P(t) \cdot S(t)$ for some $S \in \mathbb{Z}[t]$. **Reducing modulo $q$ and applying Frobenius.** We reduce the equation $R(t^q) = P(t) \cdot S(t)$ modulo $q$, working in the polynomial ring $\mathbb{F}_q[t]$. The key algebraic fact is the Frobenius identity: for any polynomial $\bar{R}(t) = \sum_{i} a_i t^i \in \mathbb{F}_q[t]$, \begin{align*} \bar{R}(t^q) &= \sum_i a_i (t^q)^i = \sum_i a_i t^{iq}. \end{align*} We claim this equals $\bar{R}(t)^q = \left(\sum_i a_i t^i\right)^q$. To see why, expand $\left(\sum_i a_i t^i\right)^q$ using the multinomial theorem. In characteristic $q$ (a prime), all cross-terms vanish: the multinomial coefficient $\binom{q}{k_0, k_1, \ldots}$ is divisible by $q$ unless exactly one $k_j = q$ and all others are $0$. The surviving terms are $\sum_i a_i^q t^{iq}$. By Fermat's Little Theorem, $a_i^q = a_i$ in $\mathbb{F}_q$, so $\bar{R}(t)^q = \sum_i a_i t^{iq} = \bar{R}(t^q)$. Applying this to our equation: \begin{align*} \bar{R}(t)^q = \bar{R}(t^q) = \bar{P}(t) \cdot \bar{S}(t). \end{align*} **Extracting the common factor.** Since $\bar{P} \mid \bar{R}(t)^q$ in $\mathbb{F}_q[t]$, every irreducible factor of $\bar{P}$ divides $\bar{R}(t)^q$. Let $\bar{h} \in \mathbb{F}_q[t]$ be an irreducible factor of $\bar{P}$. Since $\mathbb{F}_q[t]$ is a unique factorisation domain and $\bar{h}$ is irreducible, $\bar{h} \mid \bar{R}^q$ implies $\bar{h} \mid \bar{R}$. (This is the analogue of "if a prime divides a product, it divides one of the factors" -- here iterated, since $\bar{R}^q$ is a $q$-fold product of $\bar{R}$ with itself.) Now $\bar{h}$ divides both $\bar{P}$ and $\bar{R}$, so $\bar{h}^2$ divides $\bar{P} \cdot \bar{R} = \bar{\Phi}_n$ in $\mathbb{F}_q[t]$. **Deriving the contradiction via separability.** The identity $t^n - 1 = \prod_{d \mid n} \Phi_d(t)$ holds in $\mathbb{Z}[t]$, so $\Phi_n \mid t^n - 1$ in $\mathbb{Z}[t]$. Reducing modulo $q$: $\bar{\Phi}_n \mid t^n - 1$ in $\mathbb{F}_q[t]$. Combined with $\bar{h}^2 \mid \bar{\Phi}_n$, we get $\bar{h}^2 \mid t^n - 1$ in $\mathbb{F}_q[t]$. This means $t^n - 1$ has a repeated irreducible factor over $\mathbb{F}_q$. We show this is impossible when $q \nmid n$. A polynomial $f$ over a field has a repeated factor if and only if $\gcd(f, f') \ne 1$, where $f'$ is the formal derivative. Here $f = t^n - 1$ and $f' = nt^{n-1}$. Any common root $\alpha$ in $\overline{\mathbb{F}_q}$ must satisfy $\alpha^n = 1$ (from $f$) and $n\alpha^{n-1} = 0$ (from $f'$). From $\alpha^n = 1$ we get $\alpha \ne 0$, so $\alpha^{n-1} \ne 0$. Since $q \nmid n$, the element $n$ is non-zero in $\mathbb{F}_q$, so $n\alpha^{n-1} \ne 0$ -- a contradiction. Therefore $\gcd(t^n - 1, nt^{n-1}) = 1$ in $\mathbb{F}_q[t]$, and $t^n - 1$ has no repeated irreducible factors. This contradicts $\bar{h}^2 \mid t^n - 1$. Since the contradiction arose from the assumption $P(\zeta^q) \ne 0$, we conclude $P(\zeta^q) = 0$. [/guided] [/step] [step:Iterate over primes coprime to $n$ to show every primitive $n$-th root is a root of $P$] We show that every primitive $n$-th root of unity is a root of $P$. Let $\zeta' = \zeta^a$ be an arbitrary primitive $n$-th root of unity, where $\gcd(a, n) = 1$ and $1 \le a \le n$. We must show $P(\zeta') = 0$. Write $a = q_1 q_2 \cdots q_r$ as a product of (not necessarily distinct) primes. Since $\gcd(a, n) = 1$, each prime $q_j$ satisfies $q_j \nmid n$. We apply the result of the previous step iteratively: - $P(\zeta) = 0$ by hypothesis ($\zeta$ is a root of $P$). - Since $q_1 \nmid n$ and $P(\zeta) = 0$, the previous step gives $P(\zeta^{q_1}) = 0$. - Since $q_2 \nmid n$ and $P(\zeta^{q_1}) = 0$, the previous step (applied with $\zeta^{q_1}$ in place of $\zeta$, noting that $\zeta^{q_1}$ is also a primitive $n$-th root of unity and hence a root of $P$) gives $P((\zeta^{q_1})^{q_2}) = P(\zeta^{q_1 q_2}) = 0$. - Continuing, after $r$ applications: $P(\zeta^{q_1 q_2 \cdots q_r}) = P(\zeta^a) = P(\zeta') = 0$. [guided] The previous step established the "lifting" property: for a fixed primitive $n$-th root of unity $\omega$ with $P(\omega) = 0$, and any prime $q \nmid n$, $P(\omega^q) = 0$ as well. To reach an arbitrary primitive $n$-th root $\zeta' = \zeta^a$ with $\gcd(a, n) = 1$, we express $a$ as a product of primes and iterate. A subtlety to verify: at each step, the base of the induction is a primitive $n$-th root of unity. This is guaranteed because if $\omega = \zeta^b$ is a primitive $n$-th root of unity (i.e., $\gcd(b, n) = 1$) and $q$ is a prime with $q \nmid n$, then $\omega^q = \zeta^{bq}$ has $\gcd(bq, n) = \gcd(b, n) \cdot \gcd(q, n) = 1 \cdot 1 = 1$ (using that $q$ is prime and $q \nmid n$, and $\gcd(b, n) = 1$). Actually, the correct identity is: $\gcd(bq, n) = 1$ because $\gcd(b, n) = 1$ and $\gcd(q, n) = 1$ together imply $\gcd(bq, n) = 1$ (if a prime $p$ divides $n$, then $p \nmid b$ and $p \nmid q$, so $p \nmid bq$). Therefore $\omega^q$ is again a primitive $n$-th root of unity, and the previous step applies with $\omega^q$ playing the role of $\zeta$. Since every integer $a$ with $1 \le a \le n$ and $\gcd(a, n) = 1$ can be written as a product of primes $a = q_1 \cdots q_r$ (with each $q_j \nmid n$ since $\gcd(a, n) = 1$), the iteration reaches $\zeta^a$ after $r$ applications of the previous step. Therefore $P(\zeta^a) = 0$ for every $a$ with $\gcd(a, n) = 1$. [/guided] [/step] [step:Conclude that $P = \Phi_n$, contradicting the assumption of reducibility] By the previous step, every primitive $n$-th root of unity $\zeta^a$ (where $\gcd(a, n) = 1$) is a root of $P$. The primitive $n$-th roots of unity are precisely the roots of $\Phi_n$, and there are $\varphi(n)$ of them. Since $P$ is a polynomial of degree $\deg P \le \deg \Phi_n = \varphi(n)$ that vanishes at all $\varphi(n)$ roots of $\Phi_n$, and $P \mid \Phi_n$, we conclude $P = \Phi_n$ (both are monic of degree $\varphi(n)$). This contradicts the assumption that $\deg P < \deg \Phi_n$. Therefore $\Phi_n$ is irreducible over $\mathbb{Q}$. [/step]