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

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

-
What do you mean by Z*n? – Joe Johnson 126 Nov 17 '12 at 15:50
Do you mean $Z_n$ ?? – Amr Nov 17 '12 at 15:51
i mean for a multiplicative group Zn – USer22999299 Nov 17 '12 at 15:53
Hint: How many solutions does the equation $x^2 = 1$ have in the ring ${\mathbb Z}_n$. – Yury Nov 17 '12 at 15:53
is there any fast way to calculate it ? we just started the course , im not sure i have the tools to answer that. – USer22999299 Nov 17 '12 at 16:03

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

-
The size of the multiplicative group of $Z_n$ is (p-1)(q-1) and not n-1. – Amr Nov 17 '12 at 16:11

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.

-