showing that $n$th cyclotomic polynomial $\Phi_n(x)$ is irreducible over $\mathbb{Q}$ I studied the cyclotomic extension using Fraleigh's text. 

To prove that Galois group of the $n$th cyclotomic extension has order $\phi(n)$( $\phi$ is the Euler's phi function.), the writer assumed, without proof, that $n$th cyclotomic polynomial $\Phi_n(x)$ is irreducible over $\mathbb{Q}$.

I know that for n=p, p is prime, $\Phi_n(x)$ is irreducible over $\mathbb{Q}$ by Eisenstein's criterion.

But I don't know how $\Phi_n(x)$ is irreducible over $\mathbb{Q}$ when n is not prime.
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.
The simple proof, is to show that a span $\mathbb{S}$ of a finite set closed to multiplication, when intersected with $\mathbb{Q}$ gives $\mathbb{Z}$.  Since cyclotomic numbers are of this form, one can show that the span of such a set contains no fractions.

The proof is based on an attempt to construct a set $S$ whose span includes a fraction.  Since one can show that some $\frac 1{z^n}$ can not belong to $S$, then the intersection between $S$ and $Q$ is the same as between $S$ and $Z$.

Since the cyclotomic numbers form a span closed to multiplication, and the base set is finite, the intersection of any cyclotomic set and the rationals is the same as that of the integers.

Since also, one can show that the chords of a polygon $\{p\}$, which can be constructed from the cyclotomic numbers, are governed by this rule, and since this contains the chords of every rational angle, ditto.

If one takes the product of $a-\operatorname{cis}(x/n)$ for x=1 to n, it gives an algebraic equation of the form $a^n-1$, which has a unique factor for every $m \mid n$.  If the GCD of $x, n$, is greater than 1, then the particular root occurs at a lesser n.  It only gives the unique factor for $n$, if the GCD is 1.  Since the Euler totient gives the number of co-primes to n between $0$ and $n$, this is the order of the equation.

The second stage of the proof is to show that the equation is irreducable.  This is done by a process of automorphism: that the set $\operatorname{cis}(x/n)$ (where the gcd of x, n is 1), is identical to the set $\operatorname{cis}(xy,n)$.  This particular process has the effect that if a function $F(x) = F(xy)$, where F is some element in the span of $\operatorname{cis}(x,n)$, for all y, then F(x) must belong in the set $Z$.  

The span is then a reduction of a sparse array in $\phi(n)$D onto  $2$D, which means that the equations are irreducable.