Suppose first $p\mid n$. Then, $m^p\equiv m\pmod{p}$ by Fermat, so $m^{p(n-1)}-1 \equiv m^{n-1}-1\pmod{p}$, yielding $(m^{n-1}-1,n)\ge p>1$. In the rest of the proof, we suppose $p\nmid n$. Let $n=\textstyle \prod_{1\le i\le L}p_i^{e_i}$ where $p_1<\cdots<p_L$ are primes and $e_i\ge 1$. Furthermore, suppose $(m^{n-1}-1,n)=1$, and let $u=m^{n-1}$. Then, $p_i\mid u^p-1$ but $p_i\nmid u-1$. So, the order of $u$ modulo $p_i$ is $p$, and moreover $p\mid p_i-1$ as $u^{p_i-1}-1\pmod{p_i}$ by Fermat. In particular, $n\equiv 1\pmod{p}$, since all of its prime divisors are congruent to 1 modulo $p$. Now let $n-1 = p^k n'$ where $p\nmid n'$. We then have \[ m^{p^{k+1}n'}\equiv 1\pmod{p_i^{e_i}}\quad \forall 1\le i\le L. \]Furthermore, $(m^{n-1}-1,n)=1$ assumption gives \[ \left(m^{p^k n'}-1,p_i^{e_i}\right)=1. \]Now let the order of $m$ modulo $p_i^{e_i}$ be $d_i$. Then $d_i\mid p^{k+1}n'$, $d_i\nmid p^k n'$ and $d_i\mid p_i^{e_i-1}(p_i-1)$ by Euler's theorem. The first two yields $p_{k+1}\mid d_i$ and the last, together with $(p_i,p)=1$, yields $p^{k+1}\mid p_i-1$. But then \[ n = p_1^{e_1}\cdots p_L^{e_L}\Rightarrow n-1\equiv 0\pmod{p^{k+1}}, \]contradicting with the fact $v_p(n-1)=k$.

This is from MOP 2001