Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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?

share|cite|improve this answer
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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.