Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In undergraduate course, the two groups which are most frequently used may be $$\{ 0, 1, 2, ... , p-1\}$$ and $$\{ 1, 2, ... , p-1\}$$ where $p$ is a prime.

The first one is a group under addition and in addition it is a cyclic group whose generator is $p-1$. Also we can describe it by the solution set of $x^p=1$ in ${\bf C}$.

The latter is a group under multiplication. Fermat's theorem implies that $$a^{p-1} =1~~~ (\text{mod}\;\;p)$$ for $a\in \{ 1, ... , p-1\}$. But this is not sufficient for $ \{ 1, ... , p-1\}$ to be cyclic.

My question is :

$$ \{ 1, ... , p-1\}$$ is cyclic ?

Thank you in advance.

share|improve this question
2  
@Babak : Thank you for your distinguished editting. –  Hee Kwon Lee Jan 30 '13 at 9:44
1  
For a proof, see math.stackexchange.com/questions/78416/…. –  lhf Jan 30 '13 at 10:24
add comment

5 Answers 5

up vote 5 down vote accepted

Here is the proof that $G=\mathbb{F}_p ^*$ is cyclic (in fact any finite subgroup of the multiplicative group of a field is cyclic). One needs to know that a finite abelian group is the direct product of its Sylow subgroups: $$G \simeq G_{p_1} \times ...\times G_{p_n}$$ where $p_j$ is a prime and $G_{p_j}$ has order $p_j^{n_j}$. So you can assume that the group's order is a power of a prime, say $G$ has order $q^n$. But then, if $G$ does not contain an element of order $q^n$, the order of every element divides $q^{n-1}$, that is, for all $a\in G$, $$a^{q^{n-1}}-1=0$$ in the field. But this cannot be true because the polynomial of order $q^{n-1}$ would have $q^n$ roots.

share|improve this answer
add comment

The group $\{1,2,\ldots,p-1\}$ under multiplication is indeed cyclic. It can be shown that there exists a primitive root $\pmod p$ for every prime $p$. This will now generate the multiplicative group $\{1,2,\ldots,p-1\}$.

share|improve this answer
add comment

It is a general theorem that every finite subgroup of the multiplicative group of a field is cyclic. That is, if $F$ is any field, the set $F^*$ of all non-zero elements in $F$ is always a group under the multiplication in the field. Any finite subgroup of $F^*$ is cyclic. Thus the group $\mathbb Z_p^*$ that you describe is cyclic, since $\mathbb Z_p$ is a field.

There are several proofs for this result, one of them uses a characterization of finite cyclic groups that can be applied directly to $Z_p^*$. The characterization of finite cyclic groups is that if $G$ is a finite group of order $n$ then $G$ is cyclic if, and only if, for very $d$ that divides $n$ the group $G$ has at most one subgroup of order $d$. The proof is not very hard and is classical. It should be noted that the proof does not point to any generator, but only proves the existence of a generator. Consequently, using this theorem to prove that $\mathbb Z_p^*$ is cyclic does not produce a generator (known as a primitive element). There are no trivial ways to produce such primitive elements.

A somewhat similar situation is the result from Galois theory that every finite separable extension is generated by one element (a primitive element again). The general proof is again non-constructive and finding primitive elements for any given field extension can be very hard.

share|improve this answer
add comment

Consider the field $\mathbb{F}_{p}$ - the field with $p$ elements.

The group $\{1,...p\}$ is $\mathbb{F}_{p}^{*}$, that is all the invertible elements of $\mathbb{F}_{p}$.

This is a cyclic group as it is a finite subgroup of a field (with respect to multiplication).

share|improve this answer
add comment

It is cyclic. A generator $a \in \mathbb F_p^*$ would satisfy $|a| = p - 1$ where $|a|$ is the order of $a$. We can find the generator as follows. Factor $p - 1$ as $p - 1 = q_1^{a_1}q_2^{a_2}\ldots q_n^{a_n}$ where $q_i$ are distinct primes, and $a_i$ are all non-zero.

  1. We will try to find elements of $\mathbb F_p^*$ that have orders $q_i^{a_i}$. Since $x^{p-1} - 1 = 0$ has $p - 1$ roots (by Fermat's theorem) and $x^{p-1} - 1$ factors, for any $i$, as \begin{align*} x^{p-1} - 1 & = \left(x^{q_i^{a_i}} - 1\right)\left(1 + x^{q_i^{a_i}} + \ldots + \left(x^{q_i^{a_i}}\right)^{(p-1)q_i^{-a_i} - 1}\right), \end{align*} we know that $x^{q_i^{a_i}} - 1$ has exactly $q_i^{a_i}$ roots by counting degrees. A similar argument can be made to conclude that $x^{q_i^{a_i - 1}} - 1$ has exactly $q_i^{a_i - 1}$ roots. Therefore, there exists some $g_i \in \mathbb F_p^*$ such that $g^{q_i^{a_i}} = 1$ and $g^{q_i^{a_i - 1}} \ne 1$. We see that $|g| \mid q_i^{a_i}$ but $|g| \nmid q_i^{a_i - 1} $, so $|g| = q_i^{a_i}$.
  2. Let $g = g_1g_2\ldots g_n$. Obviously $|g| \mid p - 1$, i.e., $|g| = q_1^{b_1}q_2^{b_2}\ldots q_n^{b_n}$ with $b_n \le a_n$. Write this as $$ \prod_{i} g_i^{q_1^{b_1}q_2^{b_2}\ldots q_n^{b_n}} = 1. $$ Fix $j \in \{1, 2, \ldots, n\}$. Raise the above equation to the $q_k^{a_k - b_k}$-th power for all $k \ne j$ successively: \begin{align*} \prod_{i} g_i^{(p-1)q_j^{b_j-a_j}} & = 1. \end{align*} For $i \ne j$, the factor $g_i^{(p-1)q_j^{b_j-a_j}} = 1$ because $|g_i| = q_i^{a_i} \mid (p-1)q_j^{b_j - a_j}$. So the only non-identity factor is the term $i = j$: $$ g_j^{(p-1)q_j^{b_j-a_j}} = 1. $$ This means $|g_j| \mid (p-1)q_j^{b_j - a_j} = (p-1)q_j^{-a_j}q_j^{b_j}$, but $|g_j| = q_j^{a_j}$ and $q_j \nmid (p-1)q_j^{-a_j}$, we must have $b_j = a_j$.
share|improve this answer
add comment

Your Answer

 
discard

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.