11.9.14

Multiplication Tables in Z sub n

Here I talked about finding patterns to generate operation tables in Zn and I provided a pattern for fast generation of addition tables in Zn.

The group Zn is also closed with respect to multiplication, i.e. for all a, b in Zn, the result of a*b is also in Zn.

Let's consider a few statements, which also hold true in Z:
  1. Zn is Abelian, or in other words for all a, b in Zn, a*b = b*a
  2. All entries in the first row and the first column of the multiplication table of Zn are always 0 since 0*a=0 for all a in Zn;
  3. The second row or column of Zn lists all elements in Zn since 1 is the identity element in Zn  and so 1*a = a for all a in Zn;
  4. If n is a prime p then every column or row contains all elements of Zn without duplicates since Z sub p is an integral domain;

#4 ensures that there are two distinct types of multiplication table patterns of Zn depending on whether n is prime or composite. The multiplication table of Zn when n is composite may contain rows and columns with zero divisors, or duplicate entries.

So let's start with a few multiplication tables of Zn when n is prime.

If n is prime, then n is either 2 or n is odd since all even integers are divisible by 2 and all prime integers are only divisible by themselves and 1.

Therefore, if n > 2, then the last element of Zn, namely n - 1 is even (since by definition every odd integer n can be represented as 2q + 1 for some q and so n - 1 =  (2q + 1) - 1 = 2q, and 2q is by definition an even integer (1A) ), which means that the meat of the multiplication table, or in other words, all non-zero rows of the table, can be equally divided into 2 sets, i.e. one set Alpha starting from row 1 to row (n-1)/2 and another set Alpha_Upside_Down starting from row [(n-1)/2]+1 to row n-1.(2A)

Since Zn is Abelian, then Alpha_Upside_Down is simply the inverse of Alpha. The same argument holds for the columns of the multiplication tables of Zn, when n is prime, i.e. they can be equally divided into two sets where one is the inverse of the other. (3A) A few examples below when n = 5, 7, and 11:


Upside down alpha (TM)

In other words, only a pattern for the first half of the multiplication table is needed to generate the whole thing because the second half is just a mirror image of the first half. (0A)

The second interesting observation one might have is that row 2 in each table (k = 2) lists all even, then all odd integers up to n-1. For example, in row 2 of Z5 we have (2,4,1,3).  Similarly, in Z7 there are (2,4,6,1,3,5), and in Z11 there are (2,4,6,8,10,1,3,5,7,9). This is because n - 1 is even as shown in (1A)

In each subsequent row there appears to be a shift by k integers where k is the row index of the table about the identity element. But how can it be known where the identity would fall on each row without doing any calculations?

Firstly, on each row k > 1 the identity element 1 always falls right behind n - (k - 1) , and the integer after the identity is always k + 1


Another interesting observation is that the rows of these examples can be divided into consecutive subsets that seem to be dependant on each other.

For example the 3rd row of Z11  is [0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8] and it can be divided into several consecutive subsets, namely: (0, 3, 6, 9), (1, 4, 7, 10), (2, 5, 8).  Note that these subsets may not have the same cardinality: some may have more elements that the others.

Clearly,  the second subset is simply the first subset shifted by one up to n-1, and the third subset is just the second subset shifted by 1 up to n-1"

An intimate close-up of the multiplication table of Z11


Similarly, the 4th row of Z11 can also be divided into several subsets, namely: (0,4,8),(1,5,9),(2,6,10),(3,7) and once again every subset is a shift of 1 from the previous subset.

In both rows 3 and 4 the last element kfirst_last of the first subset is equivalent to n-(k-1) where k is the row index.

But what happens if the last element kfirst_last of the first subset is not equal to n-(k-1)?

In Z11 for example, this happens in row 5: (0,5,10),(4,9),(3,8),(2,7),(1,6). The last element of the first subset is 10, the first element in the second subset is 1 less than the first element of the first subset. 1 =  11 - 10

If  kfirst_last is not equal to n-(k-1), then it appears that the next element after kfirst_last is (n - kfirst_last ) less than the first element of the first subset (4A) until n-(k-1) is reached, which changes things a bit, but more on this later.

On another note, as a direct result of (2A), the last column of each multiplication table is simply the inverse of column 1, which is known in its entirety since 1*a = a for all a in Zn

In other words, the last element of the last subset is always n-k, so if n-k is reached then it is certain that the end of the row is reached where k is the index of the row.(5A)

Also if the current row k is equal to (n-1)/2, then the first half of the multiplication table has been reached, and the second half is trivial to generate since it is the inverse of the first half since the group is Abelian.(6A)

Here's a bigger example, which reveals the bigger picture, (and how tiny my handwriting really is)

Each element in the table is computed as GCD(ki*kj, 23)
 for all rows and columns ki, kj  
Also, the total number of integers in the first half of the table is n*((n-1)/2) since there are n columns and ((n-1)/2) rows in the table.(7A)

So, to sum up the algorithm for generating the first half of the multiplication table of Zn when n is prime without actually computing the GCD(each_row_index*each_column_index, n) so far from the points made in 2A, 3A, 4A, 5A, 7A:

  1. (Generate a subset with starting index ki ,while starting index ki is less than or equal to n-1 shift it by k, add that subset to a table T, (return T if it reached the n*((n-1)/2)th index)
  2. If the last index of that subset is equal to  n - ( k - 1 ) then go to (1.) with  k= 1, k = k, and table T; 
  3. Else if the last index of that subset is equal to n - k then go to (1.) with k= 0, k = k+1, and table T; 
  4. Else if the last index of that subset is less than n and the row k is less than n/2 then shift  new_ki = k-(n - ki) and go to (1.) with k= new_k,  k = k, and table T;
  5. Return table T;

The following Javascript implementation, which showcases exactly how "creative" my javascripting skills are, spits out the most desired first (n-1)/2 rows of the multiplication table of Zn when n is prime.

//Author: Marina Ibrishimova
//generating the first half of the multiplication table of Zn 
//when n is prime without actually computing
//the GCD(each_row_index*each_column_index, n)
function HammerTime(ki, k, n, table_so_far) {  
  var len = table_so_far.length;  
  var half_table_slots = n*((n-1)/2);  
  if(len == half_table_slots) {return;}  
  else {   
   while ( ki <= (n - 1)) {  
   table_so_far.push(ki);  
   ki = ki + k;  
   }  
   len = table_so_far.length;  
   var last_inset = table_so_far[len-1];  
   var k_dist = n - last_inset;   
   var new_ki = k - k_dist;   
   var n_k = k + 1;  
   if(last_inset == n-(k-1) && k < n/2) { HammerTime(1, k, n, table_so_far); }  
   if(last_inset == n-k && k < n/2) { HammerTime(0, n_k , n, table_so_far);}  
   else if(last_inset < n && k < n/2){ HammerTime(new_ki, k, n, table_so_far); }  
   }  
   return table_so_far;    
 }  


So far I've only discussed the multiplication table of Zn when n is prime, but it is easy to modify the existing algorithm to accommodate for the differences between the multiplication table of Zn when n is prime and the multiplication table of Zn when n is the product of 2 or more primes.

The main difference in the multiplication table of Zn when n is the product of 2 or more primes is that certain rows will contain 0 divisors, or in other words, integers a > 0, b > 0 such that a*b = 0 and as a result of this the first subset may repeat k times until the end of the kth row. Such rows are easy to spot because the last element of the first subset in that row will always be n-k.

The other difference is that in Zn when n is the product of 2 or more primes (n-1) may be odd but 2A still holds since Zn is Abelian for any n in Z. So when n is composite and (n-1) is odd, the number of rows needed to generate the first part of the table is the ceiling of (n-1)/2

Here is a better algorithm for generating the multiplication table of Zn

DISCLAIMER: I'm not sure if any of this has been done before because every time I go to search for something useful on the interwebs, I end up looking up adorable kittens instead. It's not in any of the textbooks I own so that's why I pursue it mostly during my lunch break but in case this has been done before then all I can say is, "Great minds think alike".  
If, however, it hasn't been done before, please contact me to chat about it as opposed to just snatching this halfway through or else. Or else I'll put a hex on you. White gypsy hex. That's right.