3
$\begingroup$

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

$\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$

$$(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$.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yeah, I can use contradiction. $\endgroup$ – Karl May 22 '15 at 3:37
  • $\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.