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?
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 c0, c1, … c9 with positions indicated in the first column.
0. c0 c0 1. c1 c5 2. c2 c1 3. c3 c6 4. c4 ———> Shuffling ———> c2 5. c5 c7 6. c6 c3 7. c7 c8 8. c8 c4 9. c9 c9Let 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.
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` ≡ 2m · 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,
2m · k ≡ k (mod 2n − 1)
Removing k from both sides we get
2m ≡ 1 (mod (2n−1)⁄gcd(k, 2n−1))
For simplicity, let us represent (2n−1)⁄gcd(k, 2n−1)) as Fnk. 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
2m ≡ 1 (mod Fnk)
Since 2n − 1 is odd, Fnk must be odd. So, gcd(2, Fnk) = 1. The smallest positive integer m that satisfies the congruence relation above is known as the multiplicative order of 2 modulo Fnk and is denoted as ordFnk(2).
If n = 1, Fnk = 1 and 2m ≡ 1 (mod Fnk) 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
2m ≡ 1 (mod (2n−1)⁄gcd(k, 2n−1))
2m ≡ 1 (mod 2n − 1)
So, far we understand that after ord2n−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 ordFnk2.
2ord2n−1(2) ≡ 1 (mod 2n − 1) ⇒ 2ord2n−1(2) ≡ 1 (mod Fnk) … (since Fnk | 2n − 1)
As a consequence of Lagrange's theorem, ordFnk(2) | ord2n−1(2).
In other words, ord2n−1(2) = c · ordFnk(2) for some positive integer c.
So, performing ord2n−1(2) out shuffles is same as repeating ordFnk(2) out shuffles c times. Every ordFnk(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 ord2n−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, ord51(2) out shuffles would restore the deck to its original configuration.
Let us compute ord51(2).
From Carmichael's theorem, 2λ(51) ≡ 1 (mod 51), where λ(n) is the smallest positive integer m such that am ≡ 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, ord51(2) | λ(51). In other words, ord51(2) | 16.
Let us check all the factors of 16 and see which one is the multiplicative order of 2 modulo 51.
22 ≡ 4 (mod 51) 24 ≡ 16 (mod 51) 28 ≡ 256 ≡ 1 (mod 51).
∴ ord51(2) = 8.
8 is the answer.