Krdytkyu

I will try to rephrase the essence of answer by Paramanand Singh so as to somewhat better isolate the arguments used (though probably less faithful to what Gauss wrote*), for the sake of transparency.

The starting point is that $defZ{Bbb Z}Phi_ninZ[X]$ are inductively defined for $n>0$ by the recurrence relation $prod_{kmid n}Phi_k=X^n-1$ (just like the numbers $phi(n)$, which ar their degrees, are defined by $sum_{kmid n}phi_k=n$); one can compute $Phi_n$ in $defQ{Bbb Q}Q[X]$ by polynomial exact division starting from $X^n-1$, and since (by induction) all divisions are by monic polynomials with integer coefficients, $Phi_n$ is monic and has integer coefficients.

If $Phi_n$ were reducible over$~Q$, this would partition the primitive $n$-th roots of unity (in $defC{Bbb C}C$) into more than one subset, each characterised as the roots of a different rational polynomial. To show that this is impossible, one argues that for any irreducible factor $F$ of $Phi_n$ in $Q[X]$, and for any prime$~p$ not dividing$~n$, the set of roots of $F$ is closed under the operation $zetamapstozeta^p$. Since (by consideration of the cyclic group of $n$-th roots of unity) this operation maps primitive $n$-th roots to primitive $n$-th roots, and compositions of such operations for different primes$~p$ allow going from any one of the $phi(n)$ primitive $n$-th roots to any other, this will show that $F$ has $phi(n)$ distinct roots in$~C$, and therefore equals $Phi_n$.

Now fix such $F$ and $p$. The operation $zetamapstozeta^p$ in $C$ on roots gives rise to an operation on irreducible polynomials in $Q[X]$: the minimal polynomial$~G$ over$~Q$ of the image of $X^p$ in the field $Q[X]/(F)$ is a monic irreducible polynomial in $Q[X]$ determined by$~F$, and by construction $F$ divides $G[X^p]$, the result of substituting $X^p$ for $X$ in $G$. Whenever $zetainC$ is a root of$~F$ it is clear that $zeta^p$ is a root of$~G$, and since $deg Gleq[Q[X]/(F):Q]=deg F$ one gets all roots of $G$ this way. One must show that $F=G$.

A key point is that $F$ and $G$, both of which divide $Phi_n$ in $Q[X]$ since their (distinct) roots in$~C$ are among the roots of the latter, have integer coefficients. This is because of Gauss's lemma stating that the product of primitive polynomials in $Z[X]$ (i.e., those not divsible by any prime number) is again primitive. (A detailed argument goes: $FinQ[X]$ is a monic divisor of the monic $Phi_ninZ[X]$, so the quotient $QinQ[X]$ with $FQ=Phi_n$ is monic; then some positive integer multiples $aF,bQinZ[X]$ are primitive (namely the minimal such multiples with all integer coefficients), and by the lemma $aFbQ=abPhi_n$ is primitive, but since $Phi_ninZ[X]$ this forces $a=b=1$.)

So one can apply modular reduction $defFp{Bbb F_p}Z[X]toFp[X]$ to our polynomials, which I shall write $Pmapstooverline P$. Being a morphism of rings, it preserves divisibility of polynomials. An important point is that $overline{X^n-1}$ is still square-free over$~Fp$ (it has no multiple roots in an extension field), since it is coprime with its derivative $overline{nX^{n-1}}$ (as $overline nneq0$ in$~Fp$ by hypothesis). Now if $F$ and $G$, which are both irreducible factors of$~X^n-1$, were distinct, then $defoF{overline F}oF$ and $defoG{overline G}oG$ would (also) be coprime in$~Fp[X]$. We will show this to be false.

Since in any ring of characteristic$~p$ the map $eta:xmapsto x^p$ is a morphism of rings (called the Frobenius endomorphism), and $eta$ fixes all elements of$~Fp$, one has in $Fp[X]$ that $oG^p=eta(oG)=oG[X^p]$, which is also clearly equal to $overline{G[X^p]}$ and therefore divisible by $oF$. This contradicts that $oF$ and $oG$ are coprime, and this contradiction finishes the proof.

*Googling around a bit I found evidence that the result is not due to Gauss at all for general $n$, but only for prime$~n$ (where $Phi_n=1+X+ldots,X^{n-1}$). See this note and this one. Apparently the general case was first proved by Dedekind, and the simplification leading to above proof is due to van der Waerden.

According to the Book Algebra of Serge Lang, the "fact that $Phi_n$ is an irreducible polynomial of degree $varphi(n)$ in the ring $mathbb{Z}[x]$ is a nontrivial result due to Gauss".
So there is no short answer to your question.

Anyway, just open your favorite book on abstract algebra, and find the proof there. (If not, maybe it's time to change your "favorite" book...)

Also, google brought up this document where several different proofs are given.

There is also a non-elementary proof that perhaps is more explanatory than the "elementary" argument, using some (but not too much) algebraic number theory, and primes in arithmetic progressions. To prove that $mathbb Q(zeta_{p^kN})$ has the expected degree over $mathbb Q$ (where $p$ does not divide $N$), it suffices to do an induction, namely, that $mathbb Q(zeta_{p^kN})$ has the expected degree over $mathbb Q(zeta_N)$. For this, it suffices to find a prime $q$ so that the degree of $mathbb Q_p(zeta_{p^kN})$ has the expected degree over $mathbb Q_p(zeta_N)$. By Dirichlet's theorem on primes in an arithmetic progress, there is a prime $q$ such that $q=1mod N$, while $q$ is congruent to a primitive root mod $p^k$. Then the extension of $mathbb Q_p$ by an $N$th root of unity is just $mathbb Q_p$, while (without necessarily knowing the precise ring of integers in cyclotomic fields, only that the degree is at least the residue class field extension degree) $mathbb Q_p(zeta_{p^k})$ is of the expected (maximal possible) degree.

Here is my version of the argument that does not use complex numbers (explicitly).
It is based on the proofs presented by Paramanand Singh and by Marc van Leeuwen.

Let it be taken for granted that the cyclotomic polynomials $Phi_ninmathbf{Z}[X]$ can be defined recursively using the formulae
$$
prod_{d:,d|n}Phi_d = X^n - 1
$$
(where $n$ and $d$ are assumed to be positive integers).
It follows in particular that each $Phi_n$ is monic.

Since the Euler's function $phi$ can be recursively defined using the formulae
$$
sum_{d:,d|n}phi(d) = n,
$$
it follows by induction on $n$ that the degree of $Phi_n$ is $phi(n)$.

If $mathbf{k}$ is a field, two polynomials $P$ and $Q$ in $mathbf{k}[X]$ shall be called coprime if and only if $(P) + (Q) = (1) = mathbf{k}[X]$ or, equivalently,¹ if and only if they have no common non-unit (i.e., in this case, non-constant) factors in $mathbf{k}[X]$.

¹_{These two properties are not equivalent in general in an arbitrary commutative ring.}

Lemma 1.
$X^n - 1$ is square-free in $mathbf{Q}[X]$, and also in $(mathbf{Z}/(p))[X]$ for every prime $p$ that does not divide $n$.

Proof idea.
The derivative of $X^n - 1$ is $nX^{n-1}$; it is coprime with $X^n - 1$ in $mathbf{Q}[X]$, and also in $(mathbf{Z}/(p))[X]$ for every prime $p$ that does not divide $n$.
$square$

Lemma 2.
$Phi_m$ and $Phi_n$ are coprime in $mathbf{Q}[X]$ for all positive integers $m$ and $n$ such that $mne n$.

Proof.
Let $k$ be a positive integer divisible by both $m$ and $n$ (for example: $k = mn$).
Then $Phi_mPhi_n$ divides $X^k - 1$ in $mathbf{Q}[X]$.
Since $X^k - 1$ is square-free in $mathbf{Q}[X]$, $Phi_m$ and $Phi_n$ are coprime in $mathbf{Q}[X]$.
Q.E.D.
$square$

Lemma 2'.
$Phi_m$ and $X^n - 1$ are coprime in $mathbf{Q}[X]$ for all positive integers $m$ and $n$ such that $m$ does not divide $n$.

Proof idea.
This is an easy corollary of lemma 2.
It can also be proved analogously to lemma 2.
$square$

Lemma 3.
Let $F$ be a non-unit (i.e., in this case, non-constant) factor of $Phi_n$ in $mathbf{Q}[X]$.
If $s$ and $t$ are non-negative integers such that $X^s = X^t$ in $mathbf{Q}[X]/(F)$, then $s = t$ in $mathbf{Z}/(n)$.

Proof.
Let $s$ and $t$ be non-negative integers such that $X^s = X^t$ in $mathbf{Q}[X]/(F)$.
Without loss of generality, assume that $sge t$.
Then $F$ divides $(X^{s-t} - 1)X^t$ in $mathbf{Q}[X]$.

$F$ is coprime with $X^t$ in $mathbf{Q}[X]$ since so is $X^n - 1$.
Therefore, $F$ divides $X^{s-t} - 1$ in $mathbf{Q}[X]$.
Therefore, $X^{s-t} - 1$ and $Phi_n$ are not coprime in $mathbf{Q}[X]$.
By lemma 2', this implies that $n$ divides $s - t$ (though the case $s - t = 0$ needs to be treated separately).

Thus, $s = t$ in $mathbf{Z}/(n)$.
Q.E.D.
$square$

The following lemma seems to be the central part of the argument.

Lemma 4.
Suppose $FG = X^n - 1$ in $mathbf{Z}[X]$.
Let $p$ be a positive prime that does not divide $n$.
Then $F$ has no common non-unit factors with $G(X^p)$ and divides $F(X^p)$ in $mathbf{Z}[X]$.

Proof.
Clearly, either $F$ and $G$ are monic, or $-F$ and $-G$ are monic.
Without loss of generality, assume that $F$ and $G$ are monic.

First of all, observe that $FG = X^n - 1$ divides $F(X^p)G(X^p) = X^{pn} - 1$ in $mathbf{Z}[X]$.
Since $mathbf{Z}[X]$ is a unique factorisation domain, in order to prove that $F$ divides $F(X^p)$ in $mathbf{Z}[X]$, it shall be enough to show that $F$ has no common non-unit factors with $G(X^p)$ in $mathbf{Z}[X]$.

Recall that the reduction of coefficients modulo $p$ defines an epimorphism $mathbf{Z}[X]to(mathbf{Z}/(p))[X]$.

Recall that the application $(mathbf{Z}/(p))[X]to(mathbf{Z}/(p))[X]$ that maps $Pmapsto P^p$ is the so-called Frobenius endomorphism of $(mathbf{Z}/(p))[X]$, and that it fixes all constant polynomials.
Therefore, for every $Pinmathbf{Z}[X]$, $P(X^p) = P^p$ in $(mathbf{Z}/(p))[X]$.
In particular, $F$ divides $F(X^p) = F^p$ in $(mathbf{Z}/(p))[X]$.

Since $p$ does not divide $n$, $X^n - 1$ is square-free in $(mathbf{Z}/(p))[X]$ (by lemma 1).
Therefore, $F$ is coprime with $G$ in $(mathbf{Z}/(p))[X]$.
It follows that for every polynomial $Sin(mathbf{Z}/(p))[X]$, $F(S)$ is coprime with $G(S)$ in $(mathbf{Z}/(p))[X]$, and in particular $F^p = F(X^p)$ is coprime with $G(X^p)$ in $(mathbf{Z}/(p))[X]$.
Hence, $F$ is coprime with $G(X^p)$ in $(mathbf{Z}/(p))[X]$.

Let $D$ be an arbitrary common divisor of $F$ and $G(X^p)$ in $mathbf{Z}[X]$.
Since $F$ and $G(X^p)$ are both monic, either $D$ or $-D$ is monic.
Since $F$ and $G(X^p)$ are coprime in $(mathbf{Z}/(p))[X]$, $D$ is constant in $(mathbf{Z}/(p))[X]$.
Since $D$ or $-D$ is monic, it follows easily that $D =pm1$ in $mathbf{Z}[X]$.

Thus $F$ has no non-unit common divisors with $G(X^p)$ in $mathbf{Z}[X]$, and hence $F$ divides $F(X^p)$ in $mathbf{Z}[X]$.
Q.E.D.
$square$

Lemma 5.
Suppose $mathbf{r}$ is a commutative ring, $P,S_1,S_2inmathbf{r}[X]$, and $P$ divides both $P(S_1)$ and $P(S_2)$ in $mathbf{r}[X]$.
Then $P$ divides $P(S_1(S_2))$ in $mathbf{r}[X]$.

(In particular, if $P$ divides both $P(X^m)$ and $P(X^n)$, then $P$ divides $P(X^{mn})$.)

Proof.
Let $P(S_1) = PQ_1$ and $P(S_2) = PQ_2$ in $mathbf{r}[X]$.
Then $P(S_1(S_2)) = (P(S_1))(S_2) = (PQ_1)(S_2) = P(S_2)Q_1(S_2) = PQ_2Q_1(S_2)$ in $mathbf{r}[X]$.
$square$

Lemma 6.
Let $F$ be a factor of $X^n - 1$ in $mathbf{Q}[X]$ and $m$ be a positive integer coprime with $n$.
Then $F$ divides $F(X^m)$ in $mathbf{Q}[X]$.

Proof idea.
Using Gauss's lemma about polynomial content, it can be easily shown that $F$ is a rational multiple of a monic polynomial with integer coefficients.
Without loss of generality, assume that $F$ is monic with integer coefficients itself.
Then $F$ divides $X^n - 1$ in $mathbf{Z}[X]$.

Let $m = p_1p_2dotsb p_k$, where $p_1,dotsc,p_k$ are positive primes (not pairwise distinct in general).
By lemma 4, $F$ is divides each of the polynomials $F(X^{p_1}),dotsc,F(X^{p_k})$ in $mathbf{Z}[X]$.
Now lemma 5 can be used to show that $F$ divides $F(X^m)$ in $mathbf{Z}[X]$.
It follows that $F$ divides $F(X^m)$ in $mathbf{Q}[X]$.
Q.E.D.
$square$

Lemma 7.
Let $F$ be a non-unit factor of $Phi_n$ in $mathbf{Q}[X]$.
Then $F$ has at least $phi(n)$ distinct roots in $mathbf{Q}[X]/(F)$.
($F$ can be viewed as an element of $(mathbf{Q}[X]/(F))[X]$.)

Proof idea.
If $m$ is an integer coprime with $n$ and satisfying $0 < mle n$, then, by lemma 6, $F$ divides $F(X^m)$ in $mathbf{Q}[X]$, and, therefore, $X^m$ is a root of $F$ in $mathbf{Q}[X]/(F)$.
($F$ is viewed here as an element of $(mathbf{Q}[X]/(F))[X]$ and $X^m$ -- as an element of $mathbf{Q}[X]/(F)$.)

If $m_1$ and $m_2$ are distinct positive integers $le n$ coprime with $n$, then $X^{m_1}$ and $X^{m_2}$ are distinct elements of $mathbf{Q}[X]/(F)$ by lemma 3.

There are $phi(n)$ distinct positive integers $m$ that are coprime with $n$ and satisfy $0 < mle n$.
$square$

Theorem.
$Phi_n$ is irreducible in $mathbf{Q}[X]$.

Proof.
Let $F$ be an irreducible factor of $Phi_n$ in $mathbf{Q}[X]$.
Then $mathbf{Q}[X]/(F)$ is a field extension of $mathbf{Q}$.

By lemma 7, $F$ has at least $phi(n)$ distinct roots in $mathbf{Q}[X]/(F)$.
Therefore, $deg Fgephi(n) =degPhi_n$ in $(mathbf{Q}[X]/(F))[X]$, as well as in $mathbf{Q}[X]$, and hence $F$ is a rational multiple of $Phi_n$ in $mathbf{Q}[X]$.
Thus $Phi_n$ is irreducible itself in $mathbf{Q}[X]$.
Q.E.D.
$square$

I think it's worthy to mention the proof in Washington's cyclotomic fields book, Proposition 2.4.

This proof is really easy to remember when the basic ramification theory is established, but there is also something nontrivial. That is, if $K$ is a number field, then $|d(K)|>1$ if $Kneq mathbb{Q}$, where $d(K)$ is the discriminant of $K$. This is due to Minkowski.

Since we know the irreducibility for prime power cases. Then the irreducibility is equivalent to $K:=mathbb{Q}(zeta_n)cap mathbb{Q}(zeta_m)=mathbb{Q}$ when $(n,m)=1$. By consider ramify condition, we know $K$ is unramify for every prime numbers, then by the above theorem, $K=mathbb{Q}$.