Let $n$ be a positive integer, and let $m$ be an integer such that $a^m\equiv1\pmod{n}$ for every integer $a\ \epsilon\ (\mathbb Z/n\mathbb Z)^*$. Show that $m$ is even.

I know that $a^{\phi(n)}\equiv1\pmod n$ by Euler's Theorem, so is this question then just about showing that $\phi(n)$ is even?

  • 2
    $\begingroup$ Well, just take $a=n-1$. $\endgroup$ – lulu Apr 10 at 15:05
  • $\begingroup$ it's supposed to be true for every $a\ \epsilon\ (\mathbb Z/n\mathbb Z)$ $\endgroup$ – joseph Apr 10 at 15:06
  • $\begingroup$ Right. So in particular it must be true for $n-1$. (note: I think you meant to write "for every $a\in \left(\mathbb Z/n\mathbb Z\right)^*$". it's obviously necessary to stick with $a$ relatively prime to $n$.). $\endgroup$ – lulu Apr 10 at 15:07
  • $\begingroup$ @lulu Same concept, I just think using $-1$ as the coset representative is more intuitive. $\endgroup$ – Don Thousand Apr 10 at 15:08
  • $\begingroup$ @DonThousand You are probably right about that...not sure why I went for $n-1$ instead. So, I agree. Just take $a=-1$. $\endgroup$ – lulu Apr 10 at 15:09

As has been said in the comments, $a\equiv -1$ suffices. Because, modular arithmetic, obeys normal arithmetic rules mostly (otherwise it would be useless in diophantine equation analysis). $$(-1)^{2x+1}=-1$$ is one such rule. So m can't be odd, and work in this case. No need to get anything else involved.

Exception n=2 and n=1 though. Because then 1 and -1 are congruent.

  • $\begingroup$ But $m$ can be odd if $\,n = 2,\,$ e.g. $\,a^1\equiv 1\pmod{\!2}\,$ for all $\,a\,$ coprime to $2$ $\ \ $ $\endgroup$ – Bill Dubuque Apr 10 at 17:56
  • $\begingroup$ okay yes mod 2 is a special case, because $1\equiv -1$ $\endgroup$ – Roddy MacPhee Apr 10 at 18:18

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.