# Why is this relation an equivalence relation on $G\setminus \{e\}$ if and only if $o(g)$ is prime for each $g \in G\setminus \{e\}$?

Show that $\sim$ is an equivalence relation on $G\setminus \{e\}$ if and only if $o(g)$ is prime for each $g \in G\setminus \{e\}$,

where $\sim$ is defined on $G\setminus \{e\}$ by $g \sim h$ if and only if $g^k = h$ for some $k \geq 1$,

$g, h \in G\setminus \{e\}$, $e$ is the identity element of $G$, and $o(g)$ is the order of $g$.

It's pretty easy to prove reflexivity and transitivity, but I can't seem to be able to put a finger on symmetricity. That's also where the prime number condition seems to come in.

Hope it's an interesting problem. Any help greatly appreciated.

-
If $g^k = h$, then $h$ is in the cyclic subgroup generated by $g$. If the order of $g$ is prime, then...? Otherwise...? – Qiaochu Yuan Jan 26 '12 at 1:19
@QiaochuYuan Ahh I kind of get this line of thinking, but can't seem to take it far enough. If the order of g is not prime, then there must exist a unique subgroup of the cyclic subgroup generated by g, and something about it makes it impossible for symmetricity? Not exactly sure though... – dhz Jan 26 '12 at 1:28
Focus on one direction first. If the order of $g$ is prime, then the subgroup generated by $g$ has prime order, and that means...? – Qiaochu Yuan Jan 26 '12 at 1:34
@QiaochuYuan Then by Fermat's Little Theorem, you can get to the first member of that subgroup, from any starting position, by taking it to the a^(p-1)th power? – dhz Jan 26 '12 at 1:49

Hint. The relation is symmetric if and only if $$g\sim h \Longleftrightarrow h\sim g$$ if and only if $$h\in \langle g\rangle \Longleftrightarrow g\in\langle h\rangle$$ if and only if $$\langle h\rangle\subseteq \langle g\rangle \Longleftrightarrow \langle g\rangle\subseteq \langle h\rangle$$ if and only if $$\langle h\rangle \subseteq \langle g\rangle \Longleftrightarrow \langle h\rangle = \langle g\rangle$$