# Prove that the order of an element in the group N is the lcm(order of the element in N's factors p and q)

How would you prove that

$$\operatorname{ord}_N(\alpha) = \operatorname{lcm}(\operatorname{ord}_p(\alpha),\operatorname{ord}_q(\alpha))$$

where $N=pq$ ($p$ and $q$ are distinct primes) and $\alpha \in \mathbb{Z}^*_N$

I've got this:

The order of an element $\alpha$ of a group is the smallest positive integer $m$ such that $\alpha^m = e$ where $e$ denotes the identity element.

And I guess that the right side has to be the $\operatorname{lcm}()$ of the orders from $p$ and $q$ because they are relatively prime to each other. But I can't put it together, any help would be appreciated!

• Ehr, $p$ and $q$ are not relatively prime to $N$: they divide $N$. They are relatively prime to each other, but not to $N$. – Arturo Magidin May 20 '12 at 23:43
• Ops, I guess I was tired when I wrote it. Of course they divide N and are relative prime to each other. – Sup3rgnu May 21 '12 at 21:19

## 2 Answers

Hint. There are natural maps $\mathbb{Z}^*_N\to\mathbb{Z}^*_p$ and $\mathbb{Z}^*_N\to\mathbb{Z}^*_q$ given by reduction modulo $p$ and reduction modulo $q$. This gives you a homomorphism $\mathbb{Z}^*_N\to \mathbb{Z}^*_p\times\mathbb{Z}^*_q$.

What is the kernel of the map into the product? What is the order of an element $(x,y)$ in the product?

• Excuse me, I am wondering if the formula still holds when N=ab & (a,b)=1? Thanks:) – puresky Dec 13 '12 at 9:25

Hint $\rm\ \ pq\:|\:a^n\!-\!1\iff p,q\:|\:a^n\!-\!1\iff ord_p a, ord_q a\:|\:n\iff lcm(ord_p a, ord_q a)\:|\: n$