0
$\begingroup$

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

  • 0
    is 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 3

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)$

0

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

  • 1
    The size of the multiplicative group of $Z_n$ is (p-1)(q-1) and not n-1.2012-11-17
0

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.