# Show that if $ab \equiv 1 \mod m$ then $\text{ord}(a) = \text{ord}(b)$

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?

• Be careful: $b$ has an inverse if and only if $(b,m) = 1$. What happens if this is not the case? – William Stagner Mar 1 '15 at 1:38
• @WilliamStagner It is assumed $b$ has an inverse. Namely $a$ is $b$'s inverse. – Eoin Mar 1 '15 at 1:40
• It is not really a proof by contradiction, but a proof by contraposition — as is often the case. – Bernard Mar 1 '15 at 1:42
• Be careful of the variable name for $\operatorname{ord}(a)$, as you are in $\mathbb{Z}/m\mathbb{Z}$. (working modulo $m$) – Eoin Mar 1 '15 at 1:46
• $\langle g\rangle=\langle g^{-1}\rangle$ in any group $G$ – whacka Mar 1 '15 at 1:48

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$.
If $ab\equiv 1$ then clearly $a\in \mathbb Z/n\mathbb Z^*$ and $b\equiv a^{-1}$. And in any group $a$ has the same order as $a^{-1}$ since $e=(aa^{-1})^n=a^na^{-n}$. So if $a^n=e$ we have $e=ea^{-n}=a^{-n}$