Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

5 Answers 5

up vote 2 down vote accepted

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

share|improve this answer
    
So, what then. I have reached the same level, but how to continue with that? –  laovultai 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$? –  laovultai 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
1  
@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?

share|improve this answer
    
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.....

share|improve this answer
    
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? –  laovultai Jun 19 '12 at 10:37
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 <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)$.

share|improve this answer

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 $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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