$\mathbb F_9$ is the $8^{th}$ cyclotomic field over $\mathbb F_3$. My problem is, that the $8^{th}$ cyclotomic polynomial factors into $2$ (distinct) factors $f$ and $g$, which means, that there is no $\mathbb F_3$-automorphism of $\mathbb F_9$ which maps a zero of $f$ to a zero of $g$.
My question is, why does this happen? From first sight I would have guessed that we could map a primitive $8^{th}$ root of unity to another, just by $\zeta\mapsto\zeta^{k}$. What is the problem with this mapping? (I'm not asking why the order of 3 in $\mathbb Z/8\mathbb Z$ is not $\phi(8)$ :), I just hope to get some intuition).
Let $\zeta$ be a primitive $8$-th root of unity in an extension of $\Bbb F_3$, and let $K=\Bbb F_3(\zeta)$ (so $K=\Bbb F_9$). The Frobenius automorphism $\phi$ maps $x\mapsto x^3$ in $K$. The primitive $8$-th roots of unity in $K$ are $\zeta$, $\zeta^3$, $\zeta^5$ and $\zeta^7$, and $\phi(\zeta)=\zeta^3$, $\phi(\zeta^3)=\zeta$, $\phi(\zeta^5)=\zeta^7$ and $\phi(\zeta^7)=\zeta^5$. They fall into two orbits under the action of $\phi$. Consider $$f_1(X)=(X-\zeta)(X-\zeta^3)=X^2-(\zeta+\phi(\zeta))X+\zeta\phi(\zeta).$$ Its coefficients are stable under $\phi$ so lie in $\Bbb F_3$. Likewise with $$f_2(X)=(X-\zeta^5)(X-\zeta^7).$$ Then the $8$-th cyclotomic polynomial is $$\Phi_8(X)=(X-\zeta)(X-\zeta^3)(X-\zeta^5)(X-\zeta^7)=f_1(X)f_2(X)$$ and is a product of two irreducible quadratics over $\Bbb F_3$.
For there to be an automorphism of $K$ with $\zeta\mapsto\zeta^m$, it is necessary that $\zeta^m=\zeta^{3^l}$ for some $l$, but this can't happen for $m=5$ or $7$. There is no "map" $\zeta\to\zeta^5$ in $K$.
In general, consider $\Phi_n(X)$ over $\Bbb F_p$ with $p\nmid n$. The minimal polynomial of $\zeta$, a primitive $n$-th root of unity, will have order $k$, where $k$ is the order of $p$ in $(\Bbb Z/n\Bbb Z)^*$.