# Order of Perfect shuffle of 2n cards

How many times do we need to perfectly shuffle a deck of 2n cards for them to return to their original order.

for $n=3$ we have the permutation $(142)(356)$

I am interested when 2n+1 is prime. Here is how far I have got:

let $a$ denote the position of a card. then what we are trying to find is the minimum x such that: $2^xa=a ($mod$2n+1)$

as we are only interested in when 2n+1 is prime we are looking for the multiplicative order of 2 mod $2n+1$

Case 1:

$p=2n+1$ where $n$ is prime and $n=3($mod$4)$

if we have the prime $p=2n+1$ where $n$ is prime and $n=3($mod$4)$ -> $p|2^n-1$

proof of above theorem http://en.wikipedia.org/wiki/Mersenne_prime

so the order of such a deck of 2n cards is $n$ eg $23=2*11+1$ then $2^{11}=1 ($mod$23)$

Case 2: $p=2^q-1$ then order is $q$

case 3: $p=2^q+1$ then order is $2q$

After this i thought that all other orders of 2 would just be $2n$ by fermats little theorem but this is not the case as take $2n = 102$

i would of expected $2^{102}$ to be the minimum power of 2 as 103 doesn't fit into any of the above cases but $2^{51}$ is the actual order.

-
In case anyone else is wondering: The question appears to be using the term "perfect shuffle" to refer to a shuffle similar to the Faro shuffle, but with the even-numbered cards preceding the odd-numbered cards. @Ben: It would have been a good idea to explain what you mean by "perfect shuffle" in the question. – joriki Jun 21 '12 at 11:32
@joriki Especially since the answer is different if the shuffle results in the odd-numbered cards preceding the odd-numbered ones. – Rick Decker Jun 21 '12 at 12:59

Just to clarify: The first of these sequences gives the number $a_n$ of out shuffles for a deck of $n$ cards; the second gives the number $b_n$ of in shuffles for a deck of $2n$ cards, which is what the question asked for; this is also the number of out shuffles for a deck of $2n+2$ cards. The two are related by $a_n=b_{\lfloor (n-1)/2\rfloor}$. – joriki Jun 22 '12 at 13:59