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