# Show that every group of prime order is cyclic

Show that every group of prime order is cyclic.

I was given this problem for homework and I am not sure where to start. I know a solution using Lagrange's theorem, but we have not proven Lagrange's theorem yet, actually our teacher hasn't even mentioned it, so I am guessing there must be another solution. The only thing I could think of was showing that a group of prime order $p$ is isomorphic to $\mathbb{Z}/p\mathbb{Z}$. Would this work?

Any guidance would be appreciated.

-
Sure. You end up basically re-proving Lagrange's theorem for groups of prime order, but this is certainly easier than proving Lagrange's in full generality first. – Cam McLeman Feb 6 '12 at 0:18
A related question: math.stackexchange.com/questions/28332/… – Jonas Meyer Feb 6 '12 at 4:57

As Cam McLeman comments, Lagranges theorem is considerably simpler for groups of prime order than for general groups: it states that the group (of prime order) has no non-trivial proper subgroups.

I'll use the following

## Lemma

Let $G$ be a group, $x\in G$, $a,b\in \mathbb Z$ and $a\perp b$. If $x^a = x^b$, then $x=1$.

Proof: by Bezout's lemma, some $k,\ell\in\mathbb Z$ exist, such that $ak+b\ell=1$. Then $$x = x^{ak+b\ell} = (x^a)^k \cdot (x^b)^\ell = 1^k \cdot 1^\ell = 1$$

(If you know a little ring theory, you might prefer to notice that the set $\{i | x^i=1\}\subseteq \mathbb Z$ forms an ideal which must contain $(a,b)=1$ if it contains $a$ and $b$.)

## The question

Now let $P$ be an arbitrary group of prime order $p$. Consider any $x\in P$ such that $x\neq 1$ and consider the set $$S = \{ 1, x, x^2 , \dots , x^{p-1} \}\subseteq P.$$ First assume two of these elements are equal, say $x^u=x^v$ and $u<v$ without loss of generality. Then $x^{v-u}=1$ and $1\leq v-u \leq p-1$. But then surely $v-u \perp p$. By the lemma, $x^{v-u} = x^p = 1$ now implies that $x=1$, a contradiction so every two members of $S$ must be different.

But then $|S|=p$. This implies $S=P$ and $P=\langle x\rangle$ is cyclic.

-
I think this was a comment of Prof McLeman's. This is neat, by the way! – Dylan Moreland Feb 6 '12 at 12:48
@DylanMoreland: Oops, I confused the two comments! – Myself Feb 6 '12 at 13:11
I just noticed I assumed that $x^p=1$, which is still unproven at that point. Perhaps this can be fixed, but I don't have time to figure out how right now. – Myself Feb 6 '12 at 13:22
Well, it's such a natural theorem that I think one barely notices that you're using anything! I'll try to think about it as well. – Dylan Moreland Feb 6 '12 at 13:42
The problem is that the assumption that $x^p=1$ is basically equivalent to Lagranges theorem (for groups of order $p$). In other words, my reasoning shows that any of the question at hand can easily be transformed into a proof of Lagranges theorem and vice versa, in other words: it shows that they are of the same difficulty. (Still it's not really the perfect answer to the OP's question, I'll think about improving it if I find the time, if no-one else has posted something better.) – Myself Feb 6 '12 at 15:26

This is a proof of Cauchy's theorem that does not use Lagrange, it is due to James McKay. It has an uncanny similarity to the proof of Fermat's Little theorem using necklaces.

Let $G$ be a group of order $np$. Then there are $(np)^{p-1}$ solutions to $g_1g_2\dots g_p=1$ since for any values of $g_1,g_2,\dots ,g_{p-1}$ there is a unique inverse for $g_1g_2\dots g_{p-1}$. We call $S$ the set of solutions, we have asserted $|S|$ is a multiple of $p$.

Notice if $g_1,g_2\dots g_p=1$ then $g_ig_{i+1}\dots g_pg_1\dots g_{i-1}=1$ also.

Divide $S$ in rotation classes. Where $s$ is in the same class as $s'$ only if they are rotations of each other. Notice all classes have size $1$ or $p$ (this uses $p$ is prime).Therefore the number of classes of size $1$ is multiple of $p$. Since $\underbrace{1,1\dots ,1}_\text{p times}$ makes up a class of size $1$ there must be another, this provides the desired element of order $p$.

We may now use Cauchy Theorem to determine a group $G$ of order $p$ has an element $g$ of order $p$, this element generates a cyclic subgroup of order $p$. This subgroup must be $G$ so $G$ is cyclic.

-