  We prove that for monic polynomials $f, g \in \mathbb{C}[x]$ such that $g$
divides $f$, the $\ell_2$-norm of the quotient polynomial $f/g$ is bounded by
$\lVert f \rVert_1 \cdot \tilde{O}(\lVert{g}\rVert_0^3\text{deg}^2{
f})^{\lVert{g}\rVert_0 - 1}$. This improves upon the previously known
exponential (in $\text{deg}{ f}$) bounds for general polynomials. Our results
implies that the trivial long division algorithm runs in quasi-linear time
relative to the input size and number of terms of the quotient polynomial
$f/g$, thus solving a long-standing problem on exact divisibility of sparse
polynomials.
  We also study the problem of bounding the number of terms of $f/g$ in some
special cases. When $f, g \in \mathbb{Z}[x]$ and $g$ is a cyclotomic-free
(i.e., it has no cyclotomic factors) trinomial, we prove that
$\lVert{f/g}\rVert_0 \leq O(\lVert{f}\rVert_0 \text{size}({f})^2 \cdot
\log^6{\text{deg}{ g}})$. When $g$ is a binomial with $g(\pm 1) \neq 0$, we
prove that the sparsity is at most $O(\lVert{f}\rVert_0 (
\log{\lVert{f}\rVert_0} + \log{\lVert{f}\rVert_{\infty}}))$. Both upper bounds
are polynomial in the input-size. We leverage these results and give a
polynomial time algorithm for deciding whether a cyclotomic-free trinomial
divides a sparse polynomial over the integers.
  As our last result, we present a polynomial time algorithm for testing
divisibility by pentanomials over small finite fields when $\text{deg}{ f} =
\tilde{O}(\text{deg}{ g})$.
