A colleague asked this problem.

How many such riffle shuffles do we need to perform on a deck of 52 cards, in order to obtain the exact same starting order?

*out shuffle*.

Let us assume that there are 2n cards where n is a positive integer. Let
us number the positions of the cards as
0, 1, … 2n − 1 where position 0 is
the top of the deck and position 2n − 1 is the bottom of the deck.
Here is an example with 10 cards called c_{0}, c_{1},
… c_{9} with positions indicated in the first column.

0. cLet us consider a card at position k where 0 ≤ k < 2n. It is easy to see from the description of the problem that a card at position k moves to position 2k if the card belongs to the top half of the deck, otherwise it moves to 2(k − n) + 1._{0}c_{0}1. c_{1}c_{5}2. c_{2}c_{1}3. c_{3}c_{6}4. c_{4}———> Shuffling ———> c_{2}5. c_{5}c_{7}6. c_{6}c_{3}7. c_{7}c_{8}8. c_{8}c_{4}9. c_{9}c_{9}

2(k − n) + 1 ≡ 2k − (2n − 1) ≡ 2k (mod 2n − 1)

So, we can say that a card at position k moves to position k' ≡ 2k mod (2n − 1) after an out shuffle where 0 ≤ k' < 2n.

So, after m shuffles a card at position k moves to position k` ≡
2^{m} · k (mod 2n − 1) where 0 ≤ k` < 2n. So,
we are looking for the smallest positive integer m such that for all
integers k, where 0 ≤ k < 2n,

2^{m} · k ≡ k (mod 2n − 1)

Removing k from both sides we get

2^{m} ≡ 1 (mod
^{(2n−1)}⁄_{gcd(k, 2n−1)})

For simplicity, let us represent
^{(2n−1)}⁄_{gcd(k, 2n−1)}) as
F_{nk}. So, a card at position k returns to the same position
after m out shuffles where m is the smallest positive integer that
satisfies the congruence relation

2^{m} ≡ 1 (mod F_{nk})

Since 2n − 1 is odd, F_{nk} must be odd. So, gcd(2,
F_{nk}) = 1. The smallest positive integer m that satisfies the
congruence relation above is known as the multiplicative order of 2
modulo F_{nk} and is denoted as ord_{Fnk}(2).

If n = 1, F_{nk} = 1 and 2^{m} ≡ 1 (mod
F_{nk}) is true for all positive integers m. So, with two cards,
an out shuffle doesn't change the positions of the cards.

If n > 2, let us consider a k which is coprime to 2n − 1 and 1 < k < 2n − 1. There exists at least one such k because φ(x) ≥ 2 for x > 2 where φ(x) is the Euler's totient of a positive integer x which is defined as the number of positive integers less than or equal to x that are coprime to x. Now, gcd(k, 2n − 1) = 1. So, now the congruence relation

2^{m} ≡ 1 (mod
^{(2n−1)}⁄_{gcd(k, 2n−1)})

reduces to

2^{m} ≡ 1 (mod 2n − 1)

So, far we understand that after ord_{2n−1}(2) out
shuffles, any card at a position number coprime to
2n − 1 would be back to its original position. What
about cards at other positions?

For a card at position k such that k is not coprime to 2n − 1,
gcd(k, 2n − 1) ≠ 1. In this case the number of out shuffles
required to bring the card at its original position is
ord_{Fnk}2.

2^{ord2n−1(2)} ≡ 1 (mod 2n − 1)
⇒ 2^{ord2n−1(2)} ≡ 1 (mod
F_{nk}) … (since F_{nk} | 2n − 1)

As a consequence of Lagrange's theorem, ord_{Fnk}(2)
| ord_{2n−1}(2).

In other words, ord_{2n−1}(2) = c ·
ord_{Fnk}(2) for some positive integer c.

So, performing ord_{2n−1}(2) out shuffles is same as
repeating ord_{Fnk}(2) out shuffles c times. Every
ord_{Fnk}(2) shuffles brings back the card at
position k to the same position. So, repeating it c times would leave it
at the same position as well.

Hence, we conclude that *ord _{2n−1}(2) out shuffles
would restore a deck of 2n cards to its original configuration, where n
is a positive integer.*

For a deck of 52 cards, n = 26. So, ord_{51}(2) out shuffles
would restore the deck to its original configuration.

Let us compute ord_{51}(2).

From Carmichael's theorem, 2^{λ(51)} ≡ 1 (mod 51),
where λ(n) is the smallest positive integer m such that
a^{m} ≡ 1 (mod n) for every positive integer a coprime to
and smaller than n.

λ(51) = lcm(λ(3), λ(17)) = lcm(2, 16) = 16.

Again as a consequence of Lagrange's theorem, ord_{51}(2) |
λ(51). In other words, ord_{51}(2) | 16.

Let us check all the factors of 16 and see which one is the multiplicative order of 2 modulo 51.

2^{2} ≡ 4 (mod 51)
2^{4} ≡ 16 (mod 51)
2^{8} ≡ 256 ≡ 1 (mod 51).

∴ ord_{51}(2) = 8.

8 is the answer.

## No comments