Show that a positive integer $x$ is a solution of the congruence $m^x\equiv 1$ mod $n$ if and only if $ord_nm|x$
Assuming that $(m, n) =1$ with both $m$ and $n$ being positive non-zero integers, is it safe to use Wilson's theorem to solve this? A friend of mine is using fermat's little theorem but I don't have the confidence to tell him he's wrong without making sure Wilson's theorem is the correct choice here (or possibly niether).
Let the order of $m$ be $d$. Now, let $q$ and $r$ be the quotient and remainder when $x$ is divided by $d$; that is $x= dq+r$. Now $$1=m^x=m^{dq+r}=(m^d)^q\cdot m^r=m^r.$$ But $d$ is the smallest integer such that $x^d=1$ and $0\leq r\leq d-1$ so it must follow that $r=0$.
So $d$ divides $x$.
Conversely, suppose $d$ divides $x$. So, there exists an integer $t$ such that $td=x$. Then $$m^x=m^{td}=(m^d)^t=1.$$
So, $m^x=1$.