1
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Short and simple. $\endgroup$ – St Vincent Mar 1 '15 at 2:05
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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