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$.
Trying to prove that a $\Bbb Z^*_n$ group is not cyclic
-
0is there any fast way to calculate it ? we just started the course , im not sure i have the tools to answer that. – 2012-11-17
3 Answers
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)$
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$.
-
1The size of the multiplicative group of $Z_n$ is (p-1)(q-1) and not n-1. – 2012-11-17
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.