I came across this problem in George Andrews's book "Number Theory" (section 4-3, problem 2). It deals with a modified version of the Faro shuffle that behaves as such:
$$(1,2,3,4,5,6,7,8) \rightarrow (4,5,3,6,2,7,1,8)$$
Essentially you cut the deck in half, flip the top half ($1,2,3,4$ in our example), and then shuffle them back together ensuring that the bottom card (8) stays at the bottom. The question asks us to prove that a deck with $2^n$ cards will return to it's original state after $n + 1$ shuffles.
The book implies that this is solved using congruence relations but I haven't been able to come up with anything substantial. I see that the piece-wise function
$$f1(x) = -2x \mod(2^{n} + 1)\quad \text{for}\quad \{x: 1 \le x \le 2^{n-1}\}$$
and
$$f2(x) = 2x + 1 \mod(2^{n} + 1) \quad \text{for}\quad \{x: 2^{n-1} \lt x \le 2^{n}\}$$
correctly map the elements but repeated composition of this function hasn't gotten me anywhere. (These two pieces can be combined into one function using an absolute value operator but composition is just as ugly.) Any hints or insights you can provide would be appreciated.