# Show that m has to be even if for every integer $a$, $a^m\equiv1\pmod{n}$.

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?

• Well, just take $a=n-1$. – lulu Apr 10 at 15:05
• it's supposed to be true for every $a\ \epsilon\ (\mathbb Z/n\mathbb Z)$ – joseph Apr 10 at 15:06
• 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$.). – lulu Apr 10 at 15:07
• @lulu Same concept, I just think using $-1$ as the coset representative is more intuitive. – Don Thousand Apr 10 at 15:08
• @DonThousand You are probably right about that...not sure why I went for $n-1$ instead. So, I agree. Just take $a=-1$. – 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.
• But $m$ can be odd if $\,n = 2,\,$ e.g. $\,a^1\equiv 1\pmod{\!2}\,$ for all $\,a\,$ coprime to $2$ $\ \$ – Bill Dubuque Apr 10 at 17:56
• okay yes mod 2 is a special case, because $1\equiv -1$ – Roddy MacPhee Apr 10 at 18:18