Prove that if $m\in\mathbb{N}$ and $x^m\equiv 1\;(\mod n)$, then $M\vert m$

Suppose that $n\in\mathbb{N}$, $x\in\mathbb{Z}$ and that $M$ is the order of $x$ modulo $n$. Prove that if $m\in\mathbb{N}$ and $x^m\equiv 1\;(\mathrm{mod}\;n)$, then $M\,\vert\,m$.

We know that $M$ is the order of $x$ modulo $n$, $M$ is the smallest integer such that $x^M\equiv 1\;(\mathrm{mod}\,n)$. Also $x^m\equiv1\;(\mathrm{mod}\;n)$. We have $M<m$. I got stuck at here. Can someone give me a hint or suggestion to continue or start a new proof?

Let $m = qM + r$ for some $q\in \mathbb{Z}_+$, $r \in \{0,1,\dots, M-1\}$. Then $x^m = x^{qM+r}$ is congruent to $1$ modulo $n$. As $x^{qM}$ is $1$ mod $n$, we must have $x^r \equiv 1 \textrm{ mod } n$. But since $r<M$, $r=0$, i.e. $M$ divides $m$.
• Why $x^{qM}\equiv1\;(\mathrm {mod}n)$? – Simple Oct 13 '16 at 5:41
• $x^M \equiv 1 \textrm{ mod } n$, so $x^{qM} \equiv (1)^q \equiv 1 \textrm{ mod } n$ – GiantTortoise1729 Oct 13 '16 at 14:43