# Proof that $a^{\mathrm{lcm}(\mathrm{ord}_m(a), \mathrm{ord}_n(a) ) } \equiv 1 \pmod{mn}$ where $\gcd(m,n)=1$.

In an answer posted to this question it is said that:

Let $k=\text{ord}_{mn}(a)$, $x=\text{ord}_m(a)$ and $y=\text{ord}_n(a)$.

The relation $$a^{\text{lcm}(x,y)}\equiv1\pmod{mn}$$ follows since $a^{\text{lcm}(x,y)}\equiv1\pmod {m\text{ and }n}$ and $\text{lcm}(m,n)=mn$. Hence $k\mid\text{lcm}(x,y)$.

I see that $a^{lcm(x, y)} \equiv 1$ (mod m) and $a^{lcm(x, y)} \equiv 1$ (mod n) hold when I do a couple toy examples, but what is this property called? How would I go about proving that? I think Fermat's Little Theorem or Euler's Function could be used but can not think of how. How is the lcm of two orders a multiple of $\phi(m)$?

• Are you assuming $\gcd(m,n) = 1$? – Myath Nov 14 '15 at 23:20
• @Myath Yes, that's part of the referenced answer. – A.P. Nov 14 '15 at 23:23

Nope, Fermat's Little Theorem isn't involved. Simply, by definition the multiplicative order of an element $g$ in a group $G$ is the smallest integer $h$ such that $g^h = e$, the identity of $G$. In this particular case it means that $$a^{\operatorname{ord}_m(a)} \equiv 1 \pmod{m} \quad \text{and} \quad a^{\operatorname{ord}_n(a)} \equiv 1 \pmod{n}$$ In particular you should note that minimality implies that the order of $a$ modulo, say, $n$ divides every other integer $h$ such that $a^h \equiv 1 \pmod{n}$.
$\operatorname{ord}_n(a) \mid \phi(n)$ for every non-zero $a$ in $\Bbb{Z}/n\Bbb{Z}$.
By definition of $\mathrm{ord}_n(a)$, $\mathrm{ord}_n(a)$ is the least positive integer $y$ such that $a^y\equiv 1\pmod{n}$; and similar for $\mathrm{ord}_m(a) = x$. And by definition of $\mathrm{lcm}(x,y)$, $\mathrm{lcm}(x,y) = ux=vy$ for some $u,v\in\mathbb{Z}$. So $$a^{\mathrm{lcm}(x,y)} \equiv a^{ux}\equiv (a^x)^u\equiv 1^u\equiv 1\pmod{m}\\ a^{\mathrm{lcm}(x,y)} \equiv a^{vy}\equiv (a^y)^v\equiv 1^v\equiv 1\pmod{n}$$