0
$\begingroup$

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)$?

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

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

Thus you could concisely rephrase Fermat's Little Theorem as:

$\operatorname{ord}_n(a) \mid \phi(n)$ for every non-zero $a$ in $\Bbb{Z}/n\Bbb{Z}$.

$\endgroup$
  • $\begingroup$ @ A.P. Ah, of course. It always seems so obvious once you see the reasoning. Thanks so much! $\endgroup$ – 1west Nov 14 '15 at 23:33
1
$\begingroup$

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

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