I know that $\varphi (n)\geq \sqrt{\frac{n}{2}}$ for natural numbers $n$, and that the cyclotomic polynomials are irreducible in $\mathbb{Q}[X]$. Let $f\in\mathbb{Q}[X]$ be a polynomial of degree $m$ with root $\alpha\in\mathbb{C}$, where $\alpha ^k=1$ for some $k\in\mathbb{N}\backslash \{ 0\}$. I must show that there is an $l\leq 2m^2$ s.t. $\Phi_l\mid f$.
I understand that if $\Phi_l\mid f$ then $l\leq 2m^2$, but I can't show that $\Phi_l\mid f$. Do you have any hints?
You've pretty much got all the right ingredients -- all you need to do is put them together in the right order.
Since $\mathbb Q[X]$ is a unique factorization domain (well, all we need is that it's a GCD domain), we can find $\gcd(f,\Phi_\ell)$ for various $\ell$. Since $\Phi_\ell$ is irreducible, this is either $\Phi_\ell$ or a constant: what happens if it's a constant for all $\ell$?