# Prove that $a$ and $a^{-1}$ inverse have the same order in $Z_n$

So there is a question in my lecture notes that I'm not too sure how to approach. It reads as follows:

Suppose $a$ is invertible modulo $n$. Prove that $a$ and $a^{-1}$ have the same order in $\mathbb Z_n$.

• How can you express the order of $a$ – alkabary May 22 '15 at 2:58
• $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ is an abelian group, so $x \mapsto x^{-1}$ is an isomorphism. Orders are preserved under isomorphisms. – Prahlad Vaidyanathan May 22 '15 at 3:49
• @Prahlad: +1. Taking your argument one step further, the map $a \mapsto a^{-1}$ is an isomorphism between a group and its opposite for any group and consequently, the order of $a$ and $a^{-1}$ are equal. Another consequence is that $ab$ and $ba$ have the same order (in this case, one usually argues that $ab$ and $ba$ are conjugates!) in a group... – knsam May 22 '15 at 7:22

$$(a^{-1})^r = 1 (a^{-1})^r = a^r (a^{-1})^r = (a^{r-1})aa^{-1}(a^{-1})^{r-1} = a^{r-1}(a^{-1})^{r-1} = \cdots = 1.$$ Therefore, $|a^{-1}| \le r$. Now, for all $0 < s < r$, $a^r(a^{-1})^s = a^{r-s} \neq 1$, so $|a^{-1}| \ge r$.

You can think about this as such: Consider $a$ as an element of $\mathbb{Z}^{\times}_{n}$. Then the cyclic subgroup generated by $a$ is the same as the subgroup generated by its inverse (why?). Therefore, the order of $a$ is the same as the order of $a^{-1}$.

To start you off, suppose that the order of $a$ is $r$. This means that $r$ is the smallest positive integer for which $a^r = 1$. Multiplying both sides by $a^{-r}$, we see that $1 = a^{-r}$; that is, $1 = (a^{-1})^r$. This shows that the order of $a^{-1}$ is at most $r$. It remains to show that no smaller integer will suffice; can you show this by contradiction?

• Yeah, I can use contradiction. – Karl May 22 '15 at 3:37
• @Karl To be clear, I didn't mean "are you allowed to use contradiction", but rather, "can you take it from here?" – Théophile May 22 '15 at 4:08

First of all suppose

$|a| = n$

$|a^{-1}| = m$

$(a^{-1})^n = a^{-n} = (a^{n})^{-1}$

so m | n now all we need to prove is that n | m and we will be done

$a = (a^{-1})^{-1}$ $\rightarrow$ $a^m = (a^{-1})^{-1})^m = (a^{-1})^{m})^{-1}$ = 1, so n | m and we are done.