2
$\begingroup$

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

  • 0
    $\overline{a}$ is confusing notation in the context of residue classes.2012-06-19

5 Answers 5

2

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

  • 1
    @Benjamin: I agree that it’s a bit odd, but I’m just using the notation in the question.2012-06-19
1

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

  • 0
    Whoops, I answered before you edited the question (and, incidentally, overwrote my edit of the question).2012-06-19
0

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

  • 1
    @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 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?2012-06-19
0

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

0

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 $