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$.
3
$\begingroup$
$\endgroup$
-
$\begingroup$ How can you express the order of $a$ $\endgroup$ – alkabary May 22 '15 at 2:58
-
2$\begingroup$ $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ is an abelian group, so $x \mapsto x^{-1}$ is an isomorphism. Orders are preserved under isomorphisms. $\endgroup$ – Prahlad Vaidyanathan May 22 '15 at 3:49
-
$\begingroup$ @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... $\endgroup$ – knsam May 22 '15 at 7:22
2
$\begingroup$
$\endgroup$
$$(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$.
1
$\begingroup$
$\endgroup$
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}$.
1
$\begingroup$
$\endgroup$
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?
-
-
$\begingroup$ @Karl To be clear, I didn't mean "are you allowed to use contradiction", but rather, "can you take it from here?" $\endgroup$ – Théophile May 22 '15 at 4:08
0
$\begingroup$
$\endgroup$
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.
