The proof which follows is the one provided by Gauss and it uses modular arithmetic in very ingenious way. We will summarize the results needed as follows:
1) For a given prime $ p$, the numbers $ 0, 1, 2, \ldots, (p - 1)$ form a finite field under the operations of addition and multiplication modulo $ p$.
2) Since these numbers form a field, say $ F_{p}$, we can talk about polynomials $ f(z)$ whose coefficients are in $ F_{p}$. The set of all such polynomials, say $ F_{p}[z]$, has the unique factorization property i.e. any such polynomial can be factored as a product of irreducible polynomials in $ F_{p}[z]$ in a unique way apart from the order of the factors. The proof is same as that used for normal polynomials with rational coefficients.
3) If $ f(z)$ is a polynomial in $ F_{p}[z]$ then $ \{f(z)\}^{p} = f(z^{p})$. This is true for constant polynomials by Fermat's theorem which says that $ a^{p} \equiv a\,\,\text{mod} (p)$. For higher degree polynomials this is achieved by induction by writing $ f(z) = az^{n} + g(z)$ and using binomial theorem to raise both sides to power $ p$. In so doing we only need to note that the binomial coefficients involved are divisible by $ p$.
The proof of irreducibility of $ \Phi_{n}(z)$ is done in two stages:
Stage 1:
Let $ \zeta$ be a primitive $ n^{th}$ root of unity and let $ f(z)$ be its minimal polynomial i.e. $ f(z)$ is monic (leading coefficient $ 1$), has rational coefficients and irreducible and $ f(\zeta) = 0$. Since $ \zeta$ is also a root of $ z^{n} - 1 = 0$, it follows that $ f(z)$ divides $ (z^{n} - 1)$ and by Gauss Lemma $ f(z)$ has integer coefficients as well. We now establish the following:
If $ p$ is any prime which does not divide $ n$ then $ \zeta^{p}$ is a root of $ f(z) = 0$.
Proof: Since $ \zeta$ is also a root of $ \Phi_{n}(z) = 0$ it follows that $ f(z)$ divides $ \Phi_{n}(z)$. Thus we have $ \Phi_{n}(z) = f(z)g(z)$ where $ g(z)$ is also monic and has integer coefficients (by Gauss Lemma). Since $ p$ is coprime to $ n$ it follows that $ \zeta^{p}$ is also a primitive $ n^{th}$ root. And therefore $ \Phi_{n}(\zeta^{p}) = 0$.
Assuming that $ \zeta^{p}$ is not a root of $ f(z) = 0$ (otherwise there is nothing to prove), we see that it must be a root of $ g(z) = 0$. Therefore $ \zeta$ is a root of $ g(z^{p}) = 0$. Since $ f(z)$ is the minimal polynomial of $ \zeta$, it follows that $ f(z)$ divides $ g(z^{p})$ so that $ g(z^{p}) = f(z)h(z)$ where $ h(z)$ is monic with integer coefficients. Also since $ \Phi_{n}(z)$ is a factor of $ (z^n - 1)$ so that we have $ z^{n} - 1 = \Phi_{n}(z)d(z)$ where $ d(z)$ is again monic with integer coefficients. We thus have the following equations:
$$z^{n} - 1 = f(z)g(z)d(z)\tag{1}$$
$$g(z^{p}) = f(z)h(z)\tag{2}$$
We now apply the modulo $ p$ operation to each of the equations above, i.e. we replace each coefficient in the polynomials involved with its remainder when it is divided by $ p$. The resulting polynomials are all in $ F_{p}[z]$ and we will use the same letters to denote them. So the above equations are now to be interpreted as relations between some polynomials in $ F_{p}[z]$. The equation $(2)$ can now be equivalently written as
$$\{g(z)\}^{p} = f(z)h(z)\tag{3}$$
Let $ k(z)$ in $ F_{p}[z]$ be an irreducible factor of $ f(z)$. Then from the above equation $(3)$, $ k(z)$ divides $ \{g(z)\}^{p}$ and so divides $ g(z)$. Thus from equation $(1)$ the polynomial $ \{k(z)\}^{2}$ divides $ (z^{n} - 1)$. Thus $ (z^n - 1)$ has repeated factors and therefore $ (z^{n} - 1)$ and its derivative $ nz^{n - 1}$ must have a common factor. Since $ n$ is coprime to $ p$, therefore the derivative $ nz^{n - 1}$ is non-zero polynomial and it clearly does not have any common factor with $ (z^{n} - 1)$.
We have reached a contradiction and therefore the initial assumption that $ \zeta^{p}$ is not the root of $ f(z) = 0$ is wrong. The result is now proved.
Stage 2:
We have thus established that if $ f(z)$ is the minimal polynomial for any primitive $ n^{th}$ root of unity then for any prime $ p$ not dividing $ n$, $ \zeta^{p}$ (which is again a primitive $ n^{th}$ root) is also a root of $ f(z) = 0$. And since $ f(z)$ is irreducible and monic, it will act as minimal polynomial for the primitive root $ \zeta^{p}$.
The same logic can be applied repeatedly and we will get the result that $ f(z)$ is the minimal polynomial for $ \zeta^{p_{1}p_{2}\ldots p_{m}}$ where $ p_{1}, p_{2}, \ldots, p_{m}$ are any primes not dividing $ n$. It follows that $ \zeta^{k}$ where $ k$ is coprime to $ n$ is also a root of $ f(z)$. Thus all the primitive $ n^{th}$ roots of unity are roots of $ f(z) = 0$. Hence $ \Phi_{n}(z)$ divides $ f(z)$. Since $ f(z)$ is irreducible it follows that $ f(z) = \Phi_{n}(z)$ (both $ f(z)$ and $ \Phi_{n}(z)$ are monic). We thus have established that $ \Phi_{n}(z)$ is irreducible.
Update: User Vik78 points out in comments that Gauss had proved the irreducibility of $\Phi_{n}(z)$ for prime values of $n$ only and it was Dedekind who established it for non-prime values of $n$. Note that the problem is far simpler when $n$ is prime (one easy proof is via Eisenstein's criterion of irreducibility) and the crux of the argument presented above is essentially due to Gauss. I came to know of this proof from the wonderful book Galois Theory of Algebraic Equations by Jean Pierre Tignol.
Tignol mentions in his book that Gauss proved the irreducibility of $\Phi_{n}(z)$ over $\mathbb{Q}$ for non-prime values of $n$ in 1808 (see section 12.6 titled Irreducibility of cyclotomic polynomials on page 196 in the book mentioned in last paragraph). Dedekind on the other hand proved an even more powerful theorem:
Theorem: Let $\zeta_{m}$ denote a primitive $m^{\text{th}}$ root of unity. If $m, n$ are relatively prime then $\Phi_{n}(z)$ is irreducible over the field $\mathbb{Q}(\zeta_{m})$.
And Gauss used this result implicitly (thinking that it could be proved in similar manner as irreducibility of $\Phi_{n}(z)$ over $\mathbb{Q}$) in obtaining solution to $\Phi_{n}(z) = 0$ via radicals.
Let $\alpha = \zeta_7 + \zeta_7^{2} + \zeta_7^{4} \in \mathbb{Q}(\zeta_7)$.
What is $\alpha$? Well, observe $\alpha^2 + \alpha + 2 = 0$.
By the quadratic equation, we find:
$$\alpha = \frac{-1 \pm \sqrt{-7}}{2}$$
whence $\sqrt{-7} \in \mathbb{Q}(\zeta_7)$ as desired. QED.
(In particular, the $\pm$ should be $+$ although either case yields $\sqrt{-7} \in \mathbb{Q}(\zeta_7)$ as desired.)
Best Answer
To make things easy for myself, I'm going to call a primitive $17$-th root of unity $z$ instead of $\zeta$. Then $K=\mathbb{Q}(z)$ is of degree $16$ over $\mathbb Q$, and its Galois group is naturally isomorphic to $(\mathbb Z/17\mathbb Z)^*$, which is cyclic, and we can choose $6$ for a generator. We have $6^2\equiv 2\pmod{17}$ and $6^4\equiv 4\pmod{17}$. Applying this to our field extension, the corresponding generator of the Galois group sends $z$ to $z^6$. The (unique) subgroup of order $8$ is generated by $z\mapsto z^2$, and the subgroup of order $4$ is generated by $z\mapsto z^4$. These groups are of index $2$ and $4$, respectively, and their fixed fields are the (unique) quadratic and quartic extensions of $\mathbb Q$ contained in $K$.
Now comes the messy computational part. You hope (and it usually seems to work) that the trace of $z$ down to each subfield will actually be a generator of the field in question. So you hope that $r=z+z^2+z^4+z^8+z^{-1}+z^{-2}+z^{-4}+z^{-8}$ will generate the quadratic extension and $x=z+z^4+z^{-1}+z^{-4}$ will generate the quartic extension. I confess that I used machine computation, but it shouldn’t be beyond handwork to see what I found: $r^2+r-4=0$. So $r=(-1\pm\sqrt{17})/2$. Yay! Next I calculated $x^2$ and $rx$, and it’s a stroke of luck that $x^2=rx+1$ !! So $x=(r\pm\sqrt{8-r})/2$.
If we take $r=(-1-\sqrt{17})/2$, then $8-r=(17+\sqrt{17})/2$, so the above computation shows that the quartic cyclic extension is $\mathbb Q\left(\sqrt{\frac{17+\sqrt{17}}2}\;\right)$, but I have to confess that I’ve run out of steam in the business of describing the action of the Galois group.