1
$\begingroup$

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

  • 1
    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](http://math.stackexchange.com/q/124408/3111)), but since this aspect is not dealt with in the proposed duplicate, I'm voting to reopen.2012-08-21

1 Answers 1

3

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.

  • 3
    @haydoni $\mathbb{Z}_2 \times \mathbb{Z}_3$ is cyclic. See the Chinese remainder theorem.2012-08-21