Number Theory: Show that $o_n(a)=m$ odd implies $o_n(-a)=2m$. I have this homework problem assigned but I'm confused as to how to solve it:
For $n>2$ and $a\in\mathbb{Z}$ with $\gcd(a,n)=1$, show that $o_n(a)=m$ is odd $\implies o_n(-a)=2m$.
(where $o_n(a)=m$ means that $a$ has order $m$ modulo $n$).
We were also given this hint: Helpful to consider when $o_p(-a)$ is odd and when it is even.
Thanks for any help!
 A: Since $a$ has order $m$, by definition $a^m\equiv 1\pmod{n}$, but $a^i\not\equiv 1\pmod{n}$  if $1\le i\lt m$.  
Note that $(-a)^{2m}\equiv 1\pmod{n}$. We show that no smaller positive power of $-a$ is congruent to $1$ modulo $n$.
Suppose to the contrary that there is a positive $k\lt 2m$ such that $(-a)^k\equiv 1\pmod{n}$. Note that $k$ divides $2m$. We cannot have $k=2m/3$, for then we would have $(-a)^{2m/3}=a^{2m/3}\equiv 1\pmod{n}$. But $m$ does not divide $2m/3$. Also, we cannot have $k\ne m$, since $(-a)^m=-(a^m)\equiv -1\pmod{m}$, and $-1\not\equiv 1\pmod{n}$m because $n\gt 2$.
So $k\lt m/2$. But then $a^{2k}=(-a)^{2k}\equiv 1\pmod{n}$. Since $2k\lt m$, this contradicts the fact that $a$ has order $m$.
A: Well, we have $a^m\equiv1\pmod{n}$.
Let the order of $-a$ be $k$, then $(-a)^k\equiv1\pmod{n}$
Then $(-a)^{2k}\equiv1\pmod{n}$ which means $a^{2k}\equiv1\pmod{n}$ so $m\mid2k$.
(1) $k={m\over2}$ is not possible since $m$ is odd.
(2) $k=m$, in this case $(-a)^k\equiv1\pmod{n}$ where $k$ is odd which means $a^k\equiv-1\pmod{n}$ contradicts $a^m\equiv1\pmod{n}$
(3) $k={3m\over2}$ is not possible since $m$ is odd.
(4) $k=2m$. This works and is the smallest.
