Let $o(x)$ denote the order of an element $x \in \mathbb{Z} / m \mathbb{Z}$. Show that if $ab \equiv 1 \mod m$ then $o(a) = o(b)$
Here's my attempt:
Proof. Since $ab \equiv 1 \mod m$, it follows that $a \equiv b^{-1} \mod m$ $\left(\text{by right multiplication of } b^{-1}\right)$. We need to show that $b$ and it's multiplicative inverse $a \mod m$ have the same order. Suppose to the contrary that $\text{ord}(a) \ne \text{ord}(b)$ with $\text{ord}(a) = m$ and $\text{ord}(b) = n$ where $m$ and $n$ are positive integers such that $m < n$. Then $1 = 1 \cdot 1 = (b^n)(a^m) = (b^n)((b^{-1})^m) = b^{n-m} = 1,$ but this implies that $\text{ord}(b) = n – m \ne n$, which contradicts the initial hypothesis. Hence $\text{ord}(a) = \text{ord}(b)$. $\text{ } \Box$
Is the proof correct?
Best Answer
It is enough to prove that $\operatorname{ord}(a)\le\operatorname{ord}(b)$. As the hypothesis is symmetric in $a$ and $b$, it will also prove $\operatorname{ord}(b)\le\operatorname{ord}(a)$.
Let $r=\operatorname{ord}(b)$. Then $1^r=(ab)^r=a^r b^r=a^r$ hence $\operatorname{ord}(a)\le r$.