Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.