show/hide this revision's text 6 added 2320 characters in body

Thanks to Gjergji's post and subsequent comment, I was able to arrive at his answer after some effort. Over the next few days I will try to post the full proof of his resulthere for anyone who might find it useful.

We begin by assuming the existence of an orbit of size 2 with elements $\{\alpha, \beta\}$. Then we must have $f(\alpha) = g(\alpha) = \beta$ which means $\alpha$ is the solution to $1-x = x^{-1}$. Multiplying both sides with $4x$ and completing the squares, we end up with $(2x-1)^2 \equiv -3 \bmod p$. The law of quadratic reciprocity tells us a solution exists iff $(2x-1)^2 \equiv p \bmod 3$. Looking at quadratic residues modulo 3 we see it is solvable if $p \equiv 1 \bmod 3$ and not solvable if $p \equiv 2 \bmod 3$. This proves the second statement of the Lemma.

If $p \equiv 1 \bmod 3$, then $(2x-1)^2 \equiv -3 \bmod p$ can be solved. We shall denote the solutions as $\pm y$, i.e. $(\pm y)^2 \equiv -3 \bmod p$ which means $\alpha = 2^{-1}(1\pm y)$. These two distinct solutions seems to indicate there are two orbits of size 2 but this is not the case. To see this, if we let $\alpha = 2^{-1}(1 + y)$ and solve for $\beta$, we end up with $\beta = 2^{-1}(1 - y)$. Therefore there is only one orbit of size 2 whenever $p \equiv 1 \bmod 3$.

Lemma 4 : There are no orbits of size 4 or 5.

TO BE CONTINUED

To show there are no orbits of size 4, again we begin by assuming such an orbit exists with integer $\{\alpha, \beta, \gamma, \delta \}$. Let $f(\alpha) = \beta$ and $g(\alpha) = \gamma$.

Next, $f(\gamma)$ cannot be equal to $\alpha$ nor $\beta$. We can also eliminate $f(\gamma) = \gamma$ as this will just give us back the orbit in Lemma 2. Therefore the only possible assignment is $f(\gamma) = \delta$. Using a similar argument, we can argue that it must be the case that $g(\beta) = \delta$. This means $f(\gamma) = g(\beta)$ which implies $fg(\alpha) = gf(\alpha)$. This in turn implies $fgffg(\alpha) = fgfgf(\alpha) \Rightarrow f(\alpha) = g(\alpha)$ where we have used Lemma 1 and the fact that $ff$ and $gg$ are both identity maps. However we have already solved $f(\alpha) = g(\alpha)$ to get an orbit of size 2 so this proves there is no orbit of size 4.

The same techniques will also show there are no orbits of size 5.

Theorem 5 : The number of orbits as a function of $p$ is as claimed in posts above.

In the first case where $p \equiv 1 \bmod 3$, there are two orbits (size 2 and 3) and all $p-7$ remaining integers belong to orbits of size 6. Therefore, the number of orbits is $(p-7)/6 + 2 = (p+5)/6$.

If $p \equiv 2 \bmod 3$, there is one orbit of size 3 with $p-5$ integers left over. Therefore, the number of orbits is $(p-5)/6 + 1 = (p+1)/6$.
show/hide this revision's text 5 added 204 characters in body

Thanks to Gjergji's post and subsequent comment, I was able to arrive at his answer after some effort. Over the next few days I will try to post the full proof of his result.

Let $p \ge 5$ be a prime number and $f(x), g(x)$ defined above in the OP on the set of integers $S=\mathbb{Z}_p \backslash \{0,1\}$.


Lemma 1 : $fgfgfg(x) = x$.

Proof : \begin{align} fgfgfg(x) &= fgfg( 1 - x^{-1}) = fgfg(x^{-1}(x-1))\\
&= fg \left( 1-x(x-1)^{-1} \right) = fg \left( (x-1)(x-1)^{-1}-x(x-1)^{-1} \right) \\
&= fg \left( -(x-1)^{-1} \right) = x \end{align} One can similarly show $\;gfgfgf(x) = x$. This proves there are no orbits with size greater than 6.

Next, consider fixed points of $f$ which amounts to solving $x \equiv 1-x$. This gives us $x \equiv 2^{-1} \bmod p$. Therefore, $f$ has exactly one fixed point.
The function $g$ also has only one fixed point which is $-1$. (Recall that $1 \notin S$).


Lemma 2 : For all prime $p\ge 5$, $\{2, -1, 2^{-1}\}$ is the only orbits of size 3.

Proof:
Consider the orbit that $2^{-1}$ belongs to. Clearly $g(2^{-1}) = 2$ and $f(2) = -1$. Further applications of $f,g$ do not map outside of $\{2, -1, 2^{-1}\}$ so this set forms an orbit. Also for all $p\ge 5$, $\{2, -1, 2^{-1}\}$ are 3 distinct elements, which means the size of this orbit is 3.

To prove there are no orbits of size 3 besides $\{2, -1, 2^{-1}\}$, assume there is another orbit of size 3, $\{\alpha, \beta, \gamma\}$, all distinct of course. W.l.o.g, we can assign $f(\alpha) = \beta$ and $g(\alpha) = \gamma$. We cannot have $g(\alpha) = \beta$ as this would imply an orbit of size 2. Then $f(\beta) = ff(\alpha) = \alpha$ and $g(\gamma) = gg(\alpha) = \alpha$. Next $f(\gamma)$ cannot be equal to $\alpha$ for it implies $f(\alpha) = \gamma$. Nor can it be equal to $\beta$ so we arrive at $f(\gamma) = \gamma$. But $-1$ is the only fixed point of $f$ so $\{\alpha, \beta, \gamma\}$ is exactly the orbit we already found, which is a contradiction.


Lemma 3 : There is exactly one orbit of size 2 whenever $p \equiv 1 \bmod 3$ and no orbit of size 2 if $p \equiv 2 \bmod 3$.

We begin by assuming the existence of an orbit of size 2 with elements $\{\alpha, \beta\}$. Then we must have $f(\alpha) = g(\alpha) = \beta$ which means $\alpha$ is the solution $1-x = x^{-1}$.


Lemma 4 : There are no orbits of size 4 or 5.

TO BE CONTINUED. . .
show/hide this revision's text 4 added 72 characters in body

Thanks to Gjergji's post and subsequent comment, I was able to arrive at his answer after some effort. Over the next few days I will try to post the full proof of his result.

Let $p \ge 5$ be a prime number and $f(x), g(x)$ defined above in the OP on the set of integers $S=\mathbb{Z}_p \backslash \{0,1\}$.


Observation


Lemma 1 : $fgfgfg(x) = x$.

Proof : \begin{align} fgfgfg(x) &= fgfg( 1 - x^{-1}) = fgfg(x^{-1}(x-1))\\
&= fg \left( 1-x(x-1)^{-1} \right) = fg \left( (x-1)(x-1)^{-1}-x(x-1)^{-1} \right) \\
&= fg \left( -(x-1)^{-1} \right) = x \end{align} One can similarly show $\;gfgfgf(x) = x$. This proves there are no orbits with size greater than 6.

Next, consider fixed points of $f$ which amounts to solving $x \equiv 1-x$. This gives us $x \equiv 2^{-1} \bmod p$. Therefore, $f$ has exactly one fixed point.
The function $g$ also has only one fixed point which is $-1$. (Recall that $1 \notin S$).


Observation


Lemma 2 : For all prime $p\ge 5$, $\{2, -1, 2^{-1}\}$ is the only orbits of size 3.

Proof:
Consider the orbit that $2^{-1}$ belongs to. Clearly $g(2^{-1}) = 2$ and $f(2) = -1$. Further applications of $f,g$ do not map outside of $\{2, -1, 2^{-1}\}$ so this set forms an orbit. Also for all $p\ge 5$, $\{2, -1, 2^{-1}\}$ are 3 distinct elements, which means the size of this orbit is 3.

To prove there are no orbits of size 3 besides $\{2, -1, 2^{-1}\}$, assume there is another orbit of size 3, $\{\alpha, \beta, \gamma\}$, all distinct of course. W.l.o.g, we can assign $f(\alpha) = \beta$ and $g(\alpha) = \gamma$. We cannot have $g(\alpha) = \beta$ as this would imply an orbit of size 2. Then $f(\beta) = ff(\alpha) = \alpha$ and $g(\gamma) = gg(\alpha) = \alpha$. Next $f(\gamma)$ cannot be equal to $\alpha$ for it implies $f(\alpha) = \gamma$. Nor can it be equal to $\beta$ so we arrive at $f(\gamma) = \gamma$. But $-1$ is the only fixed point of $f$ so $\{\alpha, \beta, \gamma\}$ is exactly the orbit we already found, which is a contradiction.


Observation


Lemma 3 : There is exactly one orbit of size 2 whenever $p \equiv 1 \bmod 3$ and no orbit of size 2 if $p \equiv 2 \bmod 3$.


Lemma 4 : There are no orbits of size 4 or 5.

TO BE CONTINUED. . .
show/hide this revision's text 3 added 47 characters in body
show/hide this revision's text 2 added 1321 characters in body; deleted 21 characters in body; added 1 characters in body
show/hide this revision's text 1