Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Note: $\text{ord}_ma = k$ here is the smallest $k$ such that $a^k \equiv 1 \pmod m$, not the highest power of $m$ that divides $a$.

Is it always that case that if $\text{ord}_ma=k$ and if $\text{ord}_mb=l$ then $\text{ord}_m(ab)=kl$ should be the $\text{lcm}(k,l)$ of which is true if $\gcd(k,l)=1$?

How would I prove this?

Perhaps I could consider the case where $b$ is a multiplicative inverse of $a$?

So, $ab \equiv 1\pmod{m}$

share|cite|improve this question
This seems false in general. $\mathrm{ord}_5(3) = \mathrm{ord}_5(2) = 4$ but $\mathrm{ord}_5(2\cdot 3) = 1$. – EuYu Oct 25 '12 at 15:23
@EuYu This isn't what I said. The example you used has the order being the same, $4$, but I need the order to be different. Perhaps, I read it wrong and it should be $\gcd(a,b)=1$. Maybe that is what's giving me so much trouble. – student.llama Oct 25 '12 at 15:46
Could you clarify your question? Especially as your idea of $b=a^{-1}$ leads to order 0. – Hagen von Eitzen Oct 25 '12 at 16:03

You should find the answers you need in the following lemma which I took straight from this question. All credit goes to Arturo Magidin, I'm only responsible for digging it up.

Lemma. Let $x$ and $y$ be commuting elements of a group $G$, and assume $x$ and $y$ are of finite orders $n$ and $m$, respectively. Suppose that for every prime $p$ that divides $nm$, the largest power of $p$ that divides $n$ is different from the largest power of $p$ that divides $m$. Then the order of $xy$ in $G$ is $\mathrm{lcm}(n,m)$.

Proof. Let $\ell=\mathrm{lcm}(n,m)$. It is easy to verify that $(xy)^{\ell}=1$, so we just need to show that $\ell$ is the smallest positive integer $k$ such that $(xy)^k=1$. Suppose that $(xy)^k = 1$, with $0\lt k\leq \ell$.

Since $(xy)^k = x^ky^k = 1$, then $x^k = y^{-k}$, and in particular $x^k$ has the same order as $y^k$. The order of $x^k$ is $n/\gcd(n,k)$, and the order of $y^k$ is $m/\gcd(n,k)$. Let $p$ be a prime that divides $\ell$, and let $a=\mathrm{ord}_p(n)$, $b=\mathrm{ord}_p(m)$, and $c=\mathrm{ord}_p(k)$. Assume $b\lt a$. If $c\lt a$, then $\mathrm{ord}_p(n/\gcd(n,k)) = a-c$, and $\mathrm{ord}_p(m/\gcd(m,k))=\max(0,b-c)\lt a-c$, which is impossible. Thus, $c=a$. A symmetric argument shows that if $a\lt b$, then $c=b$. That is, for all primes $p$ that divide $\ell$, we have $\mathrm{ord}_p(k) = \max(\mathrm{ord}_p(n),\mathrm{ord}_p(n)) = \mathrm{ord}_p(\ell)$. Hence $k=\ell$. QED

share|cite|improve this answer

Your Answer


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.