# A positive integer $x$ is a solution of the congruence $m^x\equiv 1$ mod $n$ if and only if $ord_nm|x$

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$.
• This helped out a lot but just a quick question about the "Let the order of $m$ be $d$" part. Would that be written as $ord_dm$? If that's the case, why couldn't I just keep it as $n$? – CBsmith90 Apr 18 '18 at 1:56
• Typically, we have that $\text{ord}_nm$ is read "the order of $m\bmod n$. I only named this quantity $d$ for brevity when writing up the answer. – thesmallprint Apr 18 '18 at 2:22
• Ah that makes sense. Another quick question but can I conclude that $ord_nm|\phi(n)$ from this answer? Since I'm assuming $m$ and $n$ are relatively prime I know that $m^{\phi(n)} \equiv 1 mod n$. Since we got that $x$ is a solution of $m^x \equiv mod n$ and proved it, I'd think that it would be okay to conclude this. – CBsmith90 Apr 18 '18 at 2:30