0
$\begingroup$

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!

  • 0
    Ops, I guess I was tired when I wrote it. Of course they divide$N$and are relative prime to each other.2012-05-21

2 Answers 2

3

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?

  • 0
    Excuse me, I am wondering if the formula still holds when N=ab & (a,b)=1? Thanks:)2012-12-13
0

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$