# Solution

Show if $\gcd (a,n) = \gcd (b,n) = \gcd (\textrm{ord}_n a, \textrm{ord}_n b) = 1$, then $\textrm{ord}_n (ab) = (\textrm{ord}_n a)(\textrm{ord}_n b)$.

For convenience, suppose $$\begin{array}{rcl} x &=& \textrm{ord}_n a\\ y &=& \textrm{ord}_n b\\ z &=& \textrm{ord}_n (ab) \end{array}$$

We then need to show $z=xy$ under the conditions given.

We will argue that $z | xy$ and $xy | z$, which taken together gives us the desired result.

To show the first statement holds, note that $$(ab)^{xy} \equiv (a^x)^y \cdot (b^y)^x \equiv 1^y \cdot 1^x \equiv 1\pmod{n}$$ As such, the initial exponent on $ab$ must be a multiple of $\textrm{ord}_n (ab)$.

Showing the second statement holds requires a little bit more work...

Our intention will be to show that $x | z$ and $y | z$. Then, since we were told that $x$ and $y$ are relatively prime, it will have to be the case that $xy | z$.

• First, we argue that $y | z$.

We know $(ab)^z \equiv 1\pmod{n}$. Thus, $(ab)^{xz} \equiv 1\pmod{n}$ as well.

Rewriting things a bit, we have $$a^{xz} \cdot b^{xz} \equiv 1\pmod{n}$$

However, $a^{xz} \equiv (a^x)^z \equiv 1^z \equiv 1\pmod{n}$, so the previous congruence reduces to $$b^{xz} \equiv 1\pmod{n}$$

Of course, this requires the exponent on $b$ must be a multiple of $\textrm{ord}_n b$. Equivalently, $y | xz$.

Since $x$ and $y$ are relatively prime, it must be the case that $y | z$.

• Arguing $x | z$ is done in a similar manner.

We know $(ab)^z \equiv 1\pmod{n}$. So, $(ab)^{yz} \equiv 1\pmod{n}$.

Thus, $a^{yz} \cdot b^{yz} \equiv 1\pmod{n}$, and noting that $b^{yz} \equiv (b^y)^z \equiv 1^z \equiv 1\pmod{n}$, we have $a^{yz} \equiv 1\pmod{n}$.

The exponent $yz$ must then be a multiple of $\textrm{ord}_n a$, so $x | yz$.

This, upon remembering that $x$ and $y$ are relatively prime, tells us that $x | z$.

As hoped for, we have $x|z$ and $y|z$ with $x$ and $y$ relatively prime. Consequently $xy|z$.

Since we have now argued that $xy|z$ and $z|xy$, it can only be the case that $z=xy$.

Replacing $x$, $y$, and $z$ with their defining expressions, we arrive at the desired result, $$\textrm{ord}_n (ab) = (\textrm{ord}_n a)(\textrm{ord}_n b)$$

QED.