Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.