Determining whether $\Phi_7(x)$ is irreducible over $\mathbb{F}_{11}$ The question again for convenience. I want to figure out whether
$$
x^6+x^5+x^4+x^3+x^2+x+1
$$
factors over $\mathbb{F}_{11}$.
My work: I have determined that it has no linear term $q$, by noting that 
$$
\frac{x^7-1}{x-1}=x^6+x^5+x^4+x^3+x^2+x+1
$$
and so quotienting $\mathbb{F}_{11}$ by $q$ would lead to a non trivial element of 
$$
a\in \mathbb{F}_{11},a^7=1
$$
but this is impossible, as the order of $\mathbb{F}_{11}$ as a group is $10$. 
By similar logic, $\Phi_{7}(x)$ cannot factor into a quadratic and a quartic. 
The problem is when I do this with a potential cubic factor, since 
$$
11^3-1\cong 0\mod 7
$$
so I cannot conclude similarly. Indeed, checking in Wolfram, the polynomial does factor into two cubics modulo 11. How do I check in the affirmative that it should? 
My idea is that since $\mathbb{F}_{11^3}^*$ is cyclic, and $7$ divides it's order, there is an element in the group with order $7$. Since this element is not in $\mathbb{F}_{11}\subset \mathbb{F}_{11^3}$, it came from quotienting by an irreducible cubic. However, how do I know this cubic divides $\Phi_{7}(x)$? Do I need to find the irreducible cubics in $\mathbb{F}_{11}$?
 A: You are actually done as soon as you observe that $11^3-1$ is divisible by $7$.  As you observed, this implies that there is a primitive $7$th root of unity $\alpha$ in $\mathbb{F}_{11^3}$, whose minimal polynomial $f(x)$ has degree $3$.  You then wonder why $f(x)$ must divide $\Phi_7(x)$, but this is immediate: $f(x)$ is the minimal polynomial of $\alpha$ over $\mathbb{F}_{11}$, so it divides every polynomial over $\mathbb{F}_{11}$ which has $\alpha$ as a root, and $\Phi_7(x)$ is one such polynomial.  So $f(x)$ divides $\Phi_7(x)$.  (In fact, this argument shows that every irreducible factor of $\Phi_7(x)$ is a cubic, since every irreducible factor is the minimal polynomial of some root of $\Phi_7(x)$.)
A: More generally, the irreducible factorization of any polynomial $f(x) \in \mathbb{F}_q[x]$ can be obtained by considering the orbits of the Frobenius map $x \mapsto x^q$ acting on the roots of $f$ over $\overline{\mathbb{F}_q}$: each irreducible factor is a single orbit. When $f(x) = \Phi_n(x)$ and $\gcd(q, n) = 1$ the roots are the primitive $n^{th}$ roots of unity and so the orbits can be described as follows: if $\zeta$ is such a primitive root, then $\zeta^{q^k} = \zeta$ iff
$$q^k - 1 \equiv 0 \bmod n.$$
The smallest $k$ for which this is true is the multiplicative order of $q$ in $\mathbb{Z}/n\mathbb{Z}$, and $f(x)$ necessarily factors as a product of $\frac{\varphi(n)}{k}$ irreducibles of degree $k$. The irreducible factor containing a primitive root $\zeta^a$ has roots $\zeta^{aq^i}, 0 \le i < k$. 
In this case we get that $\Phi_7(x) \bmod 11$ is a product of two irreducible cubics, namely (if $\zeta$ denotes a primitive $7^{th}$ root of unity in $\overline{\mathbb{F}_{11}}$, and using the fact that $11 \equiv 4 \bmod 7$)
$$(x - \zeta)(x - \zeta^4)(x - \zeta^2)$$
and
$$(x - \zeta^3)(x - \zeta^5)(x - \zeta^6).$$
A: We see that
$$
\Phi_7(x)=(x^3 + 7x^2 + 6x + 10)(x^3 + 5x^2 + 4x + 10),
$$
by writing it as a product of two cubics with coefficients. Then comparing coefficients gives a system of linear equations over $\mathbb{F}_{11}$, which has a solution.
