0
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – CBsmith90 Apr 18 '18 at 1:56
  • $\begingroup$ 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. $\endgroup$ – thesmallprint Apr 18 '18 at 2:22
  • $\begingroup$ 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. $\endgroup$ – CBsmith90 Apr 18 '18 at 2:30
  • $\begingroup$ Yes, that is a perfectly acceptable consequence that can be drawn from our assertion. $\endgroup$ – thesmallprint Apr 18 '18 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.