Let $n = k + l m k!$, where $l$ is an arbitrary nonnegative integer, let $p$ be any prime factor of $m$, and let $p^h$ be the highest power of $p$ that divides $k!$ — that is, $p^h$ divides $k!$ but $p^{h+1}$ does not. Notice that $n \equiv k \pmod{p^{h+1}}$, to deduce that $n(n-1)\cdots(n-k+1) \equiv k! \pmod{p^{h+1}}$, so $p^h$ is also the highest power of $p$ that divides the product $n(n-1)\cdots(n-k+1)$. Consequently, $p$ does not divide $\binom{n}{k}$, so $m$ and $\binom{n}{k}$ are indeed coprime.