# How to show that $\mathrm{ord}_m a = \mathrm{ord}_m \overline{a}$?

Let $a \in Z$ and $m \in N$ such that $\gcd(a,m)=1$. How to show that $\mathrm{ord}_m a = \mathrm{ord}_m \overline{a}$, where $\overline{a}$ is the inverse of a modulo m?

Hint: Solution starts as follows: $1 \equiv (a \overline{a})^{ord_m a} \equiv a^{ord_m a} \overline{a}^{ord_m a}\pmod m$... Problem: I don't understand why they don't just start with $1 \equiv a \overline{a}\pmod m$...

-
The do implicitly start with $a\bar{a}\equiv1$. This is taken to the $\mathrm{ord}_ma$-th power... – anon Jun 19 '12 at 10:23
$\overline{a}$ is confusing notation in the context of residue classes. – lhf Jun 19 '12 at 10:51

HINT: $a^k\bar a^k=(a\bar a)^k$

Added: (That was written before you edited the question.) For any integer $k$ you have $$a^k\bar a^k=(a\bar a)^k=1^k=1\;.\tag{1}$$ Take $k=\operatorname{ord}_m(a)$: $(1)$ becomes $$\bar a^{\operatorname{ord}_ma}=a^{\operatorname{ord}_ma}\bar a^{\operatorname{ord}_ma}=1\;;\tag{2}$$ take $k=\operatorname{ord}_m\bar a$ instead, and it becomes $$a^{\operatorname{ord}_m\bar a}=a^{\operatorname{ord}_m\bar a}\bar a^{\operatorname{ord}_m\bar a}=1\;.\tag{3}$$

I expect that you know that if $a^n=1$, then $\operatorname{ord}_ma\mid n$, i.e., $n$ is a multiple of $\operatorname{ord}_ma$. (If not, that’s the first thing that you need to prove.) If you combine that fact with $(2)$ and $(3)$, it’s not hard to prove that $\operatorname{ord}_ma=\operatorname{ord}_m\bar a$.

-
So, what then. I have reached the same level, but how to continue with that? – alvoutila Jun 19 '12 at 10:31
@alvoutila: See the material that I’ve added to my answer. – Brian M. Scott Jun 19 '12 at 10:40
Do you really mean = or $\equiv$? – alvoutila Jun 19 '12 at 10:46
@alvoutila: I mean $=$ as residue classes, which is the same as $\equiv$ as integers. – Brian M. Scott Jun 19 '12 at 10:50
@Benjamin: I agree that it’s a bit odd, but I’m just using the notation in the question. – Brian M. Scott Jun 19 '12 at 11:15

Here is a tip: How are $\overline a^n$ and $\overline{a^n}$ related?

-
Whoops, I answered before you edited the question (and, incidentally, overwrote my edit of the question). – Harald Hanche-Olsen Jun 19 '12 at 10:13

If you know some ring theory this should be pretty easy. Let us call the order of $a$ in the quotient $\Bbb{Z}/m\Bbb{Z}$ $d$ say. We can speak of the multiplicative inverse of $a$ in the quotient because $(a,m) = 1$. Also, you should know that the order of $\overline{a}^{-1}$ must divide the order of $d$.

Suppose that there is $n < d$ such that $((\overline{a})^{-1})^n = 1$. Then.....

-
Shoudn't it be $((\overline{a})^{-1})^n \equiv 1 \pmod m$. And if not then how do you proceed from that. May I get little more help? – alvoutila Jun 19 '12 at 10:37
@alvoutila No it is not that, because when we put the bar over $a$ we are already talking about residues mod $m$. Now recall that $(\overline{a}^{-1})^n = (\overline{a}^{n})^{-1}$. Since $n <d$ and $d$ is the order of $a$, it is not possible for $\overline{a}^n = 1$. Now what does this mean next? What does this give us? – user38268 Jun 19 '12 at 10:40

Let $b=\overline{a}$ and $n=ord_m(a)$. Then $1=ab$ implies $1=1^n=(ab)^n=a^n b^n = b^n$ and so $ord_m(b)\le n=ord_m(a)$. Since $a=\overline{b}$, we get $ord_m(a)\le ord_m(b)$ and so $ord_m(a)=ord_m(b)$.

-

Hint $\rm\ \ a\,\bar a = 1\ \Rightarrow\ a^n\,\bar a^n = 1\ \Rightarrow\ [\, \color{#C00}{a^n=1}\iff\color{green}{\bar a^n = 1}\,]$

Hence $\rm\displaystyle\ ord\ a = \min\,\{n\in \mathbb N_1 :\color{#C00}{ a^n = 1}\} = min\,\{n\in \mathbb N_1 : \color{green}{\bar a^n = 1}\} = ord\ \bar a$

-