Cycle lengths with prime denominators

Question

For a math course I've been playing with the following piecewise recurrence relation,

$$f(x_t) = x_{t+1} = \begin{cases} 3x_t & 0 \leq x_t < \frac{1}{3} \\ 3x_t - 1 & \frac{1}{3} \leq x_t < \frac{2}{3} \\ 3 - 3x_t & \frac{2}{3} \leq x_t \leq 1. \end{cases} $$

When the initial condition $x_0$ = $\frac{1}{p}$, where $p$ is prime, successive iterations lie on a cycle. By brute force checking many primes it appears that all cycles have at most $\frac{p-1}{2}$ elements (rarely some have fewer). With my skills I haven't been able to show (or really get an intuition for) why this is the case.

Any help would be appreciated.

Answer 1

Let $\{x\} = x-\lfloor x\rfloor$, for $p$ prime $\ge 5$ and $x_0= \frac1p$ then by induction $$x_t =\left\{ \frac{(-1)^{e_t} 3^t}p\right\}, \qquad e_t=\pm 1$$

Let $r$ be the least positive integer such that $3^r \equiv \pm 1 \bmod p$, since $\Bbb{Z/pZ}^\times / \pm 1$ is a group with $\frac{p-1}{2}$ elements then

$r$ divides $\frac{p-1}{2}$

Either $x_r = \frac1p=x_0$ and we have a cycle of length $r$,

Or $x_r=- \frac1p$ which means $x_{r+1} = \frac3p=x_1$ and we have a cycle of length $r$.