Consider the group generated by the two functions $x\mapsto \frac 1x$ and $x\mapsto -1-x$. It is isomorphic to $S_3$ and contains the following elements:
$$G=\left\{x,\frac 1x, -1-x,-\frac{1}{1+x},-\frac{x}{1+x},-\frac{1+x}{x}\right\}$$
And define the equivalence relation
$$a\sim b\iff\exists g\in G, g(a)=b$$
The integers mod $p$ for a prime are partitioned into:
-
$0,-1$ for which some inverses are undefined;
-
The two solutions of $x^2+x+1\equiv 0$ if they exist;
-
A set of equivalence classes with 6 elements each;
-
The equivalence class $1,-2,-2^{-1}$.
This is laborious but straightforward to do with standard modular arithmetic, but I wanted a (hopefully more illuminating) proof in algebraic terms. The thing about partitioning into disjoint sets of equal size reminded me of the proof of Cayley's theorem but I wasn't able to adapt it. Likewise I tried to state it as some claim about a homomorphism $G\rightarrow\mathbb{Z}/p\mathbb{Z}$ without luck.
I'm asking because here the site math pages used this result without proof.
Best Answer
You want to think of this in terms of group actions. There is no clear way to think of this as a group homomorphism from $G \to \mathbb{Z}_{p}$, since there is not clear relation between the structure of these groups. You are partitioning the elements of the set (aside from $\{0,-1\}$) into group orbits, they will not necessarily all have the same size, but they will be disjoint, and there are some nice algebraic tools for determining the sizes of these sets.
This group acts on the elements of $\mathbb{Z}_{p}\setminus\{0,-1\}$, since the group operations are not defined on those two elements. Algebraically, you are looking for the orbits of $G$ group on this set. Label the generators of your group $\sigma_{1}$ and $\sigma_{2}$, respectively.
Let $a^{G} = \{a^{g} : g \in G\}$, then $$|a^{G}| = [G:\mathrm{Stab}_{G}(a)] = |G|/|\mathrm{Stab}_{G}(a)|$$ by the orbit stabilizer theorem. Therefore all orbits will have size either $1$, $2$, $3$, or $6$. The size of $a^G$ is completely determined by the stabilizer, so we can just consider the subgroups and which elements they stabilize (there are only 3 conjugate subgroups of order 2, and a unique subgroup of order 3).
It is clear that $\sigma_{1}$ only fixes $1$ (since $-1$ is already excluded); $\sigma_{2}$ only fixes $-2^{-1}$; and $\sigma_{1}\sigma_{2}\sigma_{1}$ fixes $-2$. Thus these are the only elements stabilized by an element of order $2$. If $p=3$, they are all the same element (meaning $\mathrm{Stab}_{G}(1) = G$, giving an orbit of size 1), otherwise they are distinct and form $1^{G}$.
Note: If we put $\rho = \sigma_{1}\sigma_{2}$, $\rho$ is an element of order 3 that sends $1 \mapsto -2 \mapsto -2^{-1}$; it also gives the stabilizers of each of these elements, that is, $\rho^{-1} \sigma_{1} \rho = \sigma_{2}\sigma_{1}\sigma_{2}$ stabilizes $-2=1^{\rho}$, and $\rho^{-2} \sigma_{1} \rho^{2} = \sigma_{2}$ stabilizes $-2^{-1} = 1^{\rho^{2}}$.
On the other hand, all elements of order $3$ lie in a single subgroup generated by $\rho=\sigma_{1}\sigma_{2}$. If $a^{\rho} = a^{\sigma_{1}\sigma_{2}}=a$ then $a^\sigma_{1} = a^\sigma_{2}$, that is, $a^{-1} = -1-a$. Therefore $a(-1-a)=1$, or $a^{2}+a+1=0$. There is a single root to this equation when $p=3$ (already covered), or else there are $0$ or $2$ roots; if $0$ roots then we have no orbits of size $2$ because no elements stabilized by this subgroup, otherwise this gives a unique orbit of size 2.
All other orbits under $G$ must now have size 6, because any element of $\mathbb{Z}_{p}$ aside from $\{0,-1,1,-2,-2^{-1}\}$ has a trivial stabilizer under the group action.