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!

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

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?

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

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$

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