7
$\begingroup$

Standard texts prove that $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ when $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. What if they are not relatively prime? Here $\textrm{ord}_n(b)$ is the multiplicative order of $b$, i.e. the smallest positive integer $m$ such that $b^m=1 (\textrm{mod}\,n)$.

The naive guess that $\textrm{ord}_n(ab)$ is $\textrm{lcm}(\textrm{ord}_n(a),\textrm{ord}_n(b))$ can not be right since it gives $\textrm{ord}_n(b^k)=\textrm{ord}_n(b)$, whereas in fact $\textrm{ord}_n(b^k)=\frac{\textrm{ord}_n(b)}{\textrm{gcd}(\textrm{ord}_n(b),k)}$. So the order of the product must depend on more than just orders of the factors, perhaps on something in their prime factorizations?

What does it depend on exactly? Is there a formula for the general case? If not, are there formulas for some special cases, e.g. when $a,b$ are relatively prime, square-free, prime powers, when $n$ is prime, etc.? Are there useful bounds for it? Since the product of orders is always an upper bound a lower bound would be interesting. References appreciated.

$\endgroup$
5
$\begingroup$

This is a rather long answer, so feel free to skip over to the formula. $\def\ord{\text{ord}}\def\div{\text{ divides }}\def\v#1#2{v_{#1}(#2)}$


Let $G$ be an abelian group with two elements $a,b$. Suppose $a$ has order $m$ and $b$ has order $n$. Denote $l=\text{lcm}(m,n)$ and $g=\text{gcd}(m,n)$. Also define $H=\langle a\rangle,K=\langle b\rangle$ and $s=|H\cap K|$.

Our goal is to determine the order of $ab$.

Since $H\cap K$ is a subgroup of $H$ and $H$ is cyclic, we know $H\cap K$ must be generated by $a^{m/s}$. Similarly $H\cap K$ is generated by $b^{n/s}$. Hence there is some $k_0$ which is relatively prime to $s$ such that $a^{m/s}=b^{nk_0/s}$.


Lemma. $$\frac ls\div\ord(ab)\div l.$$

Proof.

Let $x=\ord(ab)$. Since $(ab)^x=e$, we see $a^x\in H\cap K=\langle a^{m/s}\rangle$, so $m/s\mid x$, i.e. $m\mid xs$. Similarly, $n\mid xs$. Hence $l\mid xs$, namely, $l/s\mid\ord(ab)$.

Also, $(ab)^l=e$, so $\ord(ab)\mid l$.


Theorem. $$\ord(ab)=\frac l{\gcd(s,\frac{m+nk_0}g)}.$$

Proof.

From the above lemma we know $\ord(ab)=lk/s$ for some $k$.

Now we consider $(ab)^{lk/s}=e$. $$ \eqalign{ (ab)^{lk/s}&=(a^{m/s})^{lk/m}b^{lk/s}\cr &=(b^{nk_0/s})^{lk/m}b^{lk/s}\cr &=b^{lk/s(1+nk_0/m)}\cr &=b^{lk(m+nk_0)/ms} } $$ So $(ab)^{lk/s}=e$ is equivalent with $n\mid lk(m+nk_0)/ms$, i.e. $mns\mid lk(m+nk_0)$.

Note that $mns=lgs$, so it is further equivalent with $s$ dividing $k(m+nk_0)/g$.

Let $g_1=\gcd(s,\frac{m+nk_0}g)$. Then it is equivalent with $s/g_1$ dividing $k\frac{m+nk_0}{g}/g_1$. But we know $s/g_1$ and $\frac{m+nk_0}{g}/g_1$ are relatively prime, so this is equivalent with $s/g_1$ dividing $k$, that is to say, the least such $k$ is $s/g_1$.

Therefore $\ord(ab)=lk/s=\frac{l(s/g_1)}s=\frac l{g_1}$ as desired.


From this formula we can derive a necessary and sufficient condition for $\ord(ab)=l$: $\gcd(s,\frac{m+nk_0}g)=1$. A non-trivial special case is when, for every prime divisor $p$ of $s$, $p$ does not divide $\frac{m+nk_0}g$, e.g. when $p$ divides $m$ and $n$ to different degrees.


Hope this helps.

$\endgroup$
4
  • $\begingroup$ Thank you, this is a lot work. Are there references where I can read more about these kinds of calculations? $\endgroup$ – Conifold Aug 30 '18 at 21:07
  • $\begingroup$ I did these calculations exactly because I couldn't find a good reference in the past. XD It is my pleasure to help. :) $\endgroup$ – awllower Aug 31 '18 at 1:07
  • $\begingroup$ @Conifold I have simplified the proof and the notation, and provided a not-so-trivial application. Hope you find this of some value. ;-) $\endgroup$ – awllower Aug 31 '18 at 12:55
  • $\begingroup$ Yes, thank you, it looks much prettier now and suggests that $m+nk_0$ has some invariant significance symmetric in $a$ and $b$. I found it hard to find $s$ directly from $a,b$ and $n$, but I guess this is the heart of the difficulty, if $a$ is a primitive root then $s=n$ and primitive roots are hard to detect. Is there a "strategy" for choosing $a,b$ to keep $s$ as small as possible? I wanted to build a number that has "high" orders modulo "large" primes. $\endgroup$ – Conifold Sep 1 '18 at 3:40
2
$\begingroup$

Note the extreme case $b \equiv 1/a \mod n$, where $\text{ord}_n(a) = \text{ord}_n(b)$ but $\text{ord}_n(ab) = 1$.

What is true is that $\text{ord}_n(ab) \mid \text{lcm}(\text{ord}_n(a), \text{ord}_n(b))$, since if $\text{ord}_n(a) | m$ and $\text{ord}_n(b) | m$ then $(ab)^n = a^n b^n \equiv 1 \mod n$.

Moreover, using $a = b^{-1} (ab)$ we get $\text{ord}_n(a) \mid \text{lcm}(\text{ord}_n(b), \text{ord}_n(ab))$, and similarly $\text{ord}_n(b) \mid \text{lcm}(\text{ord}_n(a), \text{ord}_n(ab))$. Thus if for some prime $p$ and positive integer $k$, $p^k$ divides $\text{ord}_n(a)$ but not $\text{ord}_n(b)$, we must have $p^k | \text{ord}_n(ab)$.

$\endgroup$
1
  • $\begingroup$ Are there conditions on $n,a,b$ that would bound $\textrm{ord}_n(ab)$ from below? I am curious as to how $\min\{\textrm{ord}_p|p>k\}$ behaves for large $k$, say for primes. $\endgroup$ – Conifold Aug 30 '18 at 17:41

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.