Saudi Arabian IMO Booklet

Set $\alpha =v_p(n-1)$ and write $n-1=r\cdot p^{\alpha }$. Let $q$ be an arbitrary prime divisor of $n$, and set $d={\text{ord}}_q(m)$. Since $$m^{p(n-1)}=m^{r\cdot p^{\alpha +1}}\equiv 1(\mathrm{mod}q),$$ it follows that $d\mid r\cdot p^{\alpha +1}$. If $v_p(d)\ne \alpha +1$, then clearly $d\mid n-1$, and therefore $q$ is a common divisor of $n$ and $m^{n-1}-1$. Otherwise, suppose that $v_p(d)=\alpha +1$ for all prime divisors of $n$. Together with $m^{q-1}\equiv 1(\mathrm{mod}q)$ by Fermat's Little Theorem, we have $$d\mid q-1⟹v_p(q-1)\ge v_p(d)=\alpha +1.$$ Thus, any prime divisor $q$ of $n$ satisfies $q\equiv 1(\mathrm{mod}{p}^{\alpha +1})$. Because $n$ is a product of these prime divisors, we deduce that $n\equiv 1(\mathrm{mod}{p}^{\alpha +1})$. However, this contradicts to $v_p(n-1)=\alpha$. $\square$