We need to discuss the group of integers modulo `n`, known as `(Z/nZ)`. Given two integers `a` and `b`, we say that `a` is related to `b` if `n` divides `(b - a)`. The equivalence class or residue class of `a` is the set of all integers which differ from `a` by a multiple of `n`.

There are precisely `n` distinct equivalency classes mod `n` determined by the possible remainders after division by `n`, namely `0` to `(n-1)`. These residue classes partition the integers.

We define the multiplicative group `(Z/nZ) ^{x}` as all the residue classes in

So, our problem consists in finding the order of 2 in `(Z/nZ) ^{x}`. Lagrange's Theorem tells us that the order of

It turns out that the order of `(Z/nZ) ^{x}` is determined by the Euler

I have written a C program to calculate `φ(i)` and relate it to our cycle data for decks whose index is `i`. Unfortunately, it does not seem to help much for large values of `i`.

I will keep working on this. Let me know if you have any ideas.

Home |

Shuffle Problem |

Initial Ideas |

Permutation |

Cycle Length |

Groups |

Last modified: |

© 2006 |

Peter C. Scott |