Group Theory and (Z/nZ)x

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 (Z/nZ) such that the representative, a, is relatively prime to n. For example, let n = 9. We know that 9 = 32, so (Z/9Z)x contains all the numbers between 1 and 8 that are not divisible by 3, in other words { 1, 2, 4, 5, 7, 8 }. Recall from our data that the cycle we found with index i = 9 was ( 1 2 4 8 7 5 ). Notice any similarity?

So, our problem consists in finding the order of 2 in (Z/nZ)x. Lagrange's Theorem tells us that the order of 2 will divide the order of (Z/nZ)x. If we can figure out the order of (Z/nZ)x, this might produce, or at least limit our search for, k.

It turns out that the order of (Z/nZ)x is determined by the Euler φ-function. To compute this, we need to factor n into powers of primes. Suppose p, q, r are primes and n = pa qb rc. Then φ(n) = φ(pa) φ(qb) φ(rc), where φ(pa) = pa-1(p-1).

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
 
Valid CSS!
 
Valid XHTML 1.1!