Let $\Phi_n(x)$ denote the minimal polynomial of $\zeta_n = e^{2\pi i/n}$ over $\mathbb{Q}$. Now it's clear that $\Phi_n$ is irreducible, so the difficulty is showing that it has degree $\phi(n)$, where $\phi$ is Euler's phi function. $\mathbb{Q}(\zeta_n)/\mathbb{Q}$ is the splitting field of $x^n-1$, so the extension is Galois. Every automorphism $\sigma$ of $\mathbb{Q}(\zeta_n)$ over $\mathbb{Q}$ is determined by the image of $\zeta_n$, which must also be a primitive $n$-th root of unity, i.e. $\sigma(\zeta_n)=\zeta_n^k$ for some $k$ that is coprime to n. This gives a well-defined homomorphism $Gal(\mathbb{Q}(\zeta_n)/\mathbb{Q})\rightarrow (\mathbb{Z}/n\mathbb{Z})^*$, which is easily seen to be injective. My question is this: why isn't this map "obviously" surjective? Given any $k$ coprime to $n$, simply consider the map you get by sending $\zeta_n$ to $\zeta_n^k$.
Surely the proof can't be this easy: irreducibility of the cyclotomic polynomials (or equivalently, cyclotomic polynomials having the correct degree) is a serious mathematical result. If the proof was this easy, someone would have written it down by now! If someone could kindly point out the flaw in thinking this map is "obviously" surjective in the way I've indicated, I'd be eternally grateful.
When you "simply" consider the map given by $\zeta_n\mapsto\zeta_n^k$ how do you know this is a field automorphism? Can you check directly that it is additive and multiplicative? With fields we don't always have the luxury that we often have with rings where we can say things like "there's a homomorphism defined by sending blah to blah", for instance you can't define $\mathbb Q(\sqrt2,\sqrt3)\to\mathbb Q(\sqrt2,\sqrt3)$ by $\sqrt2\mapsto\sqrt3$ and $\sqrt3\mapsto\sqrt2$ (edit: Jyrki gives a better example above).
To say you have an isomorphism $\mathbb Q(\alpha)\to\mathbb Q(\beta)$ sending $\alpha\mapsto\beta$ it is necessary and sufficient that $\alpha$ and $\beta$ have the same minimal polynomial over $\mathbb Q$ (call it $m$), and then this is done by passing through the isomorphisms $\mathbb Q(\alpha)\simeq \mathbb Q[x]/(m)\simeq\mathbb Q(\beta)$. So in the situation you've presented, you need to know that $\zeta_n$ and $\zeta_n^k$ have the same minimal polynomial, which is not obvious.