# Why $\mathbb{Z}_p^*$ is a cyclic group? [duplicate]

Possible Duplicate:
A question about the proof that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic

The fact that $\mathbb{Z}_p^*=\left\{ k\in\mathbb{N}_1 : \gcd(k,p)=1 \right\}$ is a cyclic group was extremely useful for me many times. But I'm afraid I completely don't know how to prove that, what makes me upset. Is the proof very difficult? Is it constructive, I mean that finds a generator? From Fermat little theorem we have $\forall_{a\in\mathbb{Z}_p^*}a^{p-1}\equiv_p 1$, but $p-1$ does not have to be the smallest exponent for all $a$.

-

## marked as duplicate by lhf, M Turgeon, Jennifer Dylan, Cocopuffs, RasmusAug 21 '12 at 13:27

mathoverflow.net/questions/54735/… –  Graphth Aug 21 '12 at 12:47
May I ask what is $\mathbb N_1$ ? –  Babak S. Aug 21 '12 at 12:47
that group, assuming you view the set as a subset of Z_p, is guaranteed to be cyclic if p is prime. Otherwise, it may or may not be. More generally, any finite subgroup of the multiplicative subgroup of a field is cyclic. The proof relies on the following characterization of finite cyclic groups: A finite group is cyclic iff for every divisor d of the order of the group there are at most \phi(d) elements of order d. The proof is a bit tricky but not that difficult. –  Ittay Weiss Aug 21 '12 at 12:47
Theorem: "Any finite subgroup of the multiplicative group of any field is cyclic". The proof, depending on what you already know, may be slightly lengthy but it is easy and elementary. You can find it in many places, for example in Serre's excelent and delicious "A Course in Arithmetic" –  DonAntonio Aug 21 '12 at 12:49
I disagree that this Question is an exact duplicate, because the issue is explicitly raised here (but not in the linked question) as to whether the proof (that $\mathbb{Z}_p^*$ has a primitive element) is constructive. I presume that many readers will know that it is not constructive (see this Question), but since this aspect is not dealt with in the proposed duplicate, I'm voting to reopen. –  hardmath Aug 21 '12 at 13:38

Since $\mathbb Z_p^{\times}$ is a finite abelian group, it's isomorphic to a product of cyclic groups say $$Z / n_1 Z \ \times \dots \times Z / n_k Z,$$ with say $n_1 | n_2 \dots | n_k$ - see the fundamental theorem of finite abelian groups.
On the other hand, we know all the elements of $\mathbb Z_p^{\times}$ satisfy the equation $x^{p-1} = 1$, so all the $n_i$'s divide $p-1$.
Now if there were more than one factor, then all the $n_i$'s are strictly smaller than $p-1$. In particular all the elements of $Z_p^{\times}$ would satisfy the equation $x^{n_k} - 1$, but there are at most $n_k$ such roots, a contradiction.
Um, $\mathbb{Z}_2 \times \mathbb{Z}_3$ is abelian, but $2\nmid 3$. –  hayd Aug 21 '12 at 13:13
@haydoni $\mathbb{Z}_2 \times \mathbb{Z}_3$ is cyclic. See the Chinese remainder theorem. –  Cocopuffs Aug 21 '12 at 13:16