1

Given an $n=pq$ where $p$ and $q$ are odd, distinct primes. Let $\alpha \in \mathbb Z_n^*$ and $\text{ord}_n(\alpha)$ be the order of $\alpha$ in $\mathbb Z_n^*$. The text claims that:

$\text{ord}_n(\alpha) = \text{lcm}(\text{ord}_p(\alpha),\text{ord}_q(\alpha))$.

How am I supposed to interpret this? What if $\alpha \geq p$? Do I just compute the value modulo $p$? In that case the order of $n$ in $\mathbb Z_n^*$ is always $\text{lcm}((p-1),(q-1))$. But if $p=3$ and $q=5$ we can easily find an element in $\mathbb Z_{15}^*$ such that the order is not 4. Take for instance 4. Have anyone got some light to shed on this?

KryptoJon
  • 25

1 Answers1

0

Is $\Bbb Z^*_n$ the multiplicative group of integers coprime to $n$? Yes, if $\alpha \gt p$ (it can't be equal, then it wouldn't be coprime to $n$) you take $\alpha \pmod p$ and look for its multiplicative order. The multiplicative order is the lowest solution to $\alpha^k=1 \pmod p$ So if $p=13, \alpha=2, \operatorname {ord}_p(\alpha)=12$, but if $p=13, \alpha=4, \operatorname {ord}_p(\alpha)=6$ For your example, you are correct that $\operatorname {ord}_{15}(4)=2$, but $ \operatorname {ord}_3(4)=1$ and $ \operatorname {ord}_5(4)=2$ with $\operatorname{lcm } 2$, so all is well.

Ross Millikan
  • 374,822
  • Thank you for your answer. I had for some silly reason convinced myself that all elements of $\mathbb Z_p^*$ had order $p-1$, hence the problem. – KryptoJon Dec 11 '13 at 02:41