Trying to prove that a $\Bbb Z^*_n$ group is not cyclic

Question

I need to prove that ${\mathbb Z}^*_n$ is not a cyclic group for any $n = p \cdot q$ where $p$ and $q$ are any two different prime numbers greater than $2$.

Answer 1

Using Fermat's Little Theorem, $a^{p-1}\equiv1\pmod p$ if $(a,p)=1$

and $a^{q-1}\equiv1\pmod q$ if $(a,q)=1$

If $d=lcm(p-1,q-1),a^d\equiv1\pmod p$ and $a^d\equiv1\pmod q$ if $(a,pq)=1$

$\implies a^d\equiv1\pmod {lcm(p,q)}$

But $lcm(p,q)=pq,$ so $a^d\equiv 1\pmod{pq}$

As $p,q$ are odd, $(p-1,q-1)\mid 2$ so, $d\le\frac{(p-1)(q-1)}2<(p-1)(q-1)=\phi(pq)$

So, there can be no element $|\langle a \rangle|$ with order $\phi(pq)$

Answer 2

Suppose $a$ is a generator. Obviously, $a$ and $n$ must be relatively prime. By Euler's theorem, $a^{\phi(n)} \equiv a^{(p-1)(q-1)} \equiv 1 \mod n$, so the order of $a$ is at most $(p-1)(q-1)$, which is strictly less than $n-1$. Thus, $|\langle a \rangle| < |\mathbb{Z}^*_n|$, and we have a contradiction. So $\mathbb{Z}^*_n$ is not cyclic.

Scratch that. Haha. Thanks, amr. I was using the wrong order for $\mathbb{Z}^*_n$.

Answer 3

Requiring $(Z_n)^* $ to be cyclic is the same as requiring there to be a "primitive root" mod $n$. It is known that the $n$ for which there are primitive roots are $2,4,p^k,2p^k$ where $p$ is an odd prime. So your assumption of two different primes greater than 2 does not fall under one of these cases where there is a primitive root.

Of course this is only quoting a known result, and not directly showing what the question asked, but a look ath the primitive root topic in number theory might be helpful to the OP.