I recognize this question has been asked many times before (here, here, and here) and in other forms (that $pq$ does not have a primitive root for example).

I am also self-studying Aluffi's Algebra and am wondering specifically about the last solution above I have linked.

We know that $\mathbb{Z}_{pq}^*$ has order $pq$ less the multiples of $p$ or $q$ between $1$ and $pq$. These multiples of $p$ are $p,2p,...,(q-1)p$, of $q$ are $q,2q,...,(p-1)q$, and of course their least common multiple $pq$. So the order is $pq - (p-1) - (q-1) - 1 = (p-1)(q-1)$.

We aim to show that there is no element of this order so that the group cannot be cyclic. Put $n = (p-1)(q-1) /2$. Both factors in the numerator are even so we can do this and still have both factors dividing $n$.

The last solution linked above uses that for $m\in \mathbb{Z}_{pq}^{*}$ we have $m$ in both $\mathbb{Z}_{p}^{*}$ and $\mathbb{Z}_{q}^{*}$, with $$ m^{n} \equiv m^{p-1} \equiv 1 \mod p \\ m^{n} \equiv m^{q-1} \equiv 1 \mod q.$$ From which we get $p,q | m^{n} - 1$ so $pq | (m^{n}-1)$ since $p,q$ are coprime. But how do we know that $$ m^{p-1} \equiv 1 \mod p \\ m^{q-1} \equiv 1 \mod q$$ without something like Lagrange's theorem? Aluffi doesn't develop a lot for us to work with...

  • $\begingroup$ Welcome to Math Stack Exchange. Can you use Fermat's little theorem? $\endgroup$ – J. W. Tanner Jul 16 at 18:54
  • $\begingroup$ No, we do not know it yet in this text. $\endgroup$ – Waldon Jul 16 at 18:57
  • $\begingroup$ +1 for having done your homework and finding those related threads! $\endgroup$ – Jyrki Lahtonen Jul 16 at 19:21
  • $\begingroup$ Probably he already proved special cases of Lagrange (such as the order of an element divides the order of the group), and that is all that you need. Update: that's true. I just checked, see the prior section II.1.6. $\endgroup$ – Bill Dubuque Jul 16 at 20:02
  • $\begingroup$ Thank you for pointing that out @Bill Dubuque! A bad oversight on my part, I imagine it would be further away since Lagrange's Theorem is still quite far. I will be sure to add the reference in the margins of my text. $\endgroup$ – Waldon Jul 16 at 20:43

I believe I have solved it.

Let $m\in\mathbb{Z}_{pq}^{*}$. We have that $m\in\mathbb{Z}_{p}^{*}$ and $m\in\mathbb{Z}_{q}^{*}$. Let $k$ and $l$ be the orders of $m$ in these latter groups, resp. We see that $k \leq p-1$ and $l \leq q-1$ because the groups only have that many elements. If equality holds in both cases, then the result follows from the considerations in the question above. So allow one of the inequalities to be strict.

We see that $$m^{kl} \equiv (m^{k})^{l} \equiv 1 \mod p \\ m^{kl} \equiv (m^{l})^{k} \equiv 1 \mod q$$ so we must have $m^{kl} \equiv 1 \mod pq$. Thus the order of $m \in \mathbb{Z}_{pq}^{*}$ is at most $kl$. Since $kl < (p-1)(q-1)$, we are done.

  • $\begingroup$ Re: Fermat's Little Theorem. (1). An equivalent version is $m^p\equiv m\mod p$ for all $m$, when $p$ is prime. (2). The case $p=2$ is obvious. (3), For $p>2$ it suffices to consider only $m\ge 0.$ The case $m=0$ is obvious. Now if $p$ is prime and $1\le j\le p-1$ then the the binomial co-efficient $\binom {p}{j}$ is divisible by $p.$ So if $m^p\equiv m \mod p$ then ($1+m)^p=1 +(\,\sum_{j=1}^{p-1}m^j\binom {p}{j}\,)+m^p\equiv$ 1+m^p\equiv$ 1+m \mod p,$... So we have a proof by induction on $m.$ $\endgroup$ – DanielWainfleet Jul 18 at 7:04

You know that $\mathbb Z_p^*$ is of order $p-1$ because $p$ is prime. But group theory tells us that the order of any element in a group divides the order of the group itself.

So if $m\in \mathbb Z$ is not a multiple of $p$ (which is the case if you assume that the classe of $m$ in $\mathbb Z_{pq}$ is invertible), you have $$ m^{p-1} \equiv 1 \mod p$$

  • $\begingroup$ The issue is that we don't have access to that fact from group theory yet (it comes much later in the text). But I believe I have solved it in my answer. $\endgroup$ – Waldon Jul 17 at 14:59

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.