Let $p$ be prime and let $f \in \mathbb{F}_p[X]$ with no repeated roots. Let $k \in \mathbb{N}^*$ such that $\deg(f) > p^k$. Show that $f$ has an irreducible divisor of degree $> k$.
My work so far: $f$ can not split over $\mathbb{F}_{p^k}$. Now I'm stuck already.
On
For every $l\in\mathbb{N}$, the extension $\mathbb{F}_{p^l}/\mathbb{F}_p$ is normal, thus every irreducible polynomial of degree $l$ over $\mathbb{F}_p$ splits in $\mathbb{F}_{p^l}$. Assume that all irreducible components of $f$ are of degree $\leq k$, then each one of them splits in $\mathbb{F}_{p^k}$, thus $f$ splits in $\mathbb{F}_{p^k}$, which is impossible, as you observed yourself.
Correct me if I am wrong, but I think the proposition is actually not correct. As a counterexample, consider $$f = (x^8 - x) \cdot (x^2 + x + 1) = x (x-1) (x^2 + x + 1) (x^3 + x + 1) (x^3 + x^2 + 1)$$ over $\Bbb F_2$. It has degree $10 > 2^3$ and no repeated roots, yet all irreducible factors have degree $\le 3$ (the problem is that $x^2 + x + 1$ does not split in $\Bbb F_8$).
One proof strategy (for a salvage) would be the following: Consider all algebraic elements over $\Bbb F_p$ whose minimal polynomial (over $\Bbb F_p$) has degree $\le k$. If $f$ has no irreducible factor of degree $> k$ then all the roots of $f$ are among these algebraic elements. The worst-case clearly is when $f$ has all of these elements as its roots. Thus we must replace $p^k$ by the number of these algebraic elements. Clearly, $p + p^2 + \dots + p^k$ would work but the bound can definitely be made better (should not be too hard if you think a while about it, I don't have the time right now). In particular, $p^{k+1}$ is sufficient.