# Orbits in modular arithmetic

Let $p$ be an odd prime number and consider the set of $p-2$ integers that is $\mathbb{Z}_p$ minus 0 and 1. Next define two bijective functions on this set \begin{align} f(x) &= 1-x \mod p \end{align} and \begin{align} g(x) &= x^{-1} \mod p \qquad \text{(the multiplicative inverse of $x$).} \end{align} One can view these two functions as group actions (generated by $f$ and $g$) on this set of integers and study the orbits. For example, if $p=7$, there are two orbits namely {2,4,6} and {3,5}.

For the general prime $p>3$, I can prove there is always an orbit consisting of $\{ 2,p-1, 2^{-1} \}$.

Question : I'm interested to find the number of orbits as a function of $p$.

-
I have no idea what the answer is, but here's one thing you might try; calculate the number of orbits for the first few primes, then look up the resulting sequence in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Mar 7 '11 at 22:34
OK let's see. Let $N(p)$ be the number of orbits. Then $N(5) = 1, N(7) = 2, N(11) = 2, N(13) = 3$. It seems I need more data points to narrow things down. – kett Mar 7 '11 at 23:03
These maps show up, if I recall it correctly, in several publications on "exceptional units" (Martinet, Leutbecher, Niklasch). – Franz Lemmermeyer Mar 8 '11 at 12:18
This is a pretty classical question. You can find a description of the answers in my paper with Boyd and Thom: math.ubc.ca/~gerg/index.shtml?abstract=SVTD – Greg Martin Apr 5 at 21:39

You can first notice that $fgfgfg(x)=x$ and conclude that most orbits have size $6$. It is easy to show that there is one orbit of size $3$ which you found and there is an orbit of size $2$ whenever there is a solution to $$x(1-x)\equiv 1\pmod{p}$$ this happens if $\binom{-3}{p}=1$ so if $p\equiv 1\pmod{3}$. You can easily show that there can't be orbits of size $4$ or $5$. So the answer is $\frac{p+1}{6}$ if $p\equiv -1\pmod{3}$ and $\frac{p+5}{6}$ if $p\equiv 1\pmod{3}$.

-
If you have time, would you mind expanding a little bit more on your proof as I haven't been able to reproduce your answer. For example, I don't know how to show $fgfgfg(x)=x$. I can see why one would only need to consider composed functions that alternate between $f$ and $g$ because their squares are just the identity map. – kett Mar 7 '11 at 23:53
Also I can see how the orbit of size 2 can be obtained by solving $f(x) \equiv g(x)$ which leads to your equation $x(1-x) \equiv 1 \bmod p$ but I don't understand how your condition impies there is a solution. It seems like I need to solve the quadratic equation $x^2 - x + 1 \equiv 0 \bmod p$. – kett Mar 7 '11 at 23:54
@kett, at this point you should be able to work out the details yourself. The values under the f,g maps are the same as the ones of the cross-ratio under the $S_4$ action. en.wikipedia.org/wiki/Cross-ratio#Action_of_symmetric_group Also notice that you can rewrite the second equation as $(2x-1)^2\equiv -3\pmod{p}$ – Gjergji Zaimi Mar 8 '11 at 0:03
Your second comment is quite useful, to solve it using quadratic reciprocity. en.wikipedia.org/wiki/Quadratic_reciprocity – kett Mar 8 '11 at 1:16
Much better than my suggestion of calculating examples and looking it up in the OEIS. – Gerry Myerson Mar 8 '11 at 3:07

Your transformations act on the projective line $\mathbb Z_p \cup\{\infty\}$, preserving the three points $0$, $1$, $\infty$. The group they generate is isomorphic to the group $\mathfrak S_3$ of permutations on these three points.

Anyway, you can enumerate the orbit of a point $x\in\mathbb Z_p\setminus\{0,1\}$ and obtain [ { x, 1-x, \frac 1x, \frac1{1-x}, \frac x{x-1} , \frac{x-1}x}. ] This orbit usually has cardinality 6, unless if the stabilizer of $x$ is nontrivial. When this happens, you have $x=1-x$, or $x=1/x$, or $x=1/(1-x)$, or $x=x/(x-1)$, or $x=(x-1)/x$.

Assume now that $p>3$. (The cases $p=2$ and $3$ are trivial.)

The preceding analysis shows that there is exaclty one orbit with cardinality $3$, namely $\{-1,2,1/2\}$, and one orbit of cardinality $2$, $\{\alpha,1-\alpha\}$, where $\alpha$ is an element of $\mathbb Z_p$ satisfying $\alpha^2-\alpha+1=0$. Such an $\alpha$ exists if and only if $-3$ is a square in $\mathbb Z_p$.

Let $k$ be the number of orbits with cardinality $6$. The total number of orbits is $k+2$ if $-3$ is a square, and $k+1$ otherwise. Counting the number of elements in $\mathbb Z_p\setminus\{0,1\}$ gives $p-2=6k+3+2$ in the former case, and $p-2=6k+3$ in the latter, that is: $p=6k+7$, resp. $p=6k+5$.

Finally, we obtain that for $p\equiv 1\pmod 6$, $-3$ is a square modulo $p$ and there are $(p+5)/6$ orbits, while for $p\equiv -1\pmod 6$, $-3$ is not a square and there are $(p+1)/6$ orbits.

NB. In both cases, the number of orbits is equal to $\lfloor(p+5)/6\rfloor$.

-

Thanks to Gjergji's post and subsequent comment, I was able to arrive at his answer after some effort. I post the full proof here for anyone who might find it useful.

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 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 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$.

-
@kett: There appear to be two essentially complete answers to this question already, so there is no need to bump it so many times (5 times in the past 2 days). If you feel the need for such an extremely detailed write-up, it may be worthwhile writing it on your own (in a text or LaTeX editor) and then, if you'd like to put it here, to copy and paste it upon completion. – Daniel Litt Mar 11 '11 at 5:03
I'm sorry, I wasn't aware this post gets bumped every time I edit my answer -- that wasn't my intention. Is there a way to turn this feature off? – kett Mar 11 '11 at 6:55
No alas, except to write up your answer externally and paste it in when you're done, as I suggested. – Daniel Litt Mar 14 '11 at 1:40