_{n}and I provided a pattern for fast generation of addition tables in Z

_{n}.

The group Z

_{n}is also closed with respect to multiplication, i.e. for all a, b in Z

_{n}, the result of a*b is also in Z

_{n}.

Let's consider a few statements, which also hold true in Z

_{n }:

- Z
_{n}is Abelian, or in other words for all a, b in Z_{n}, a*b = b*a - All entries in the first row and the first column of the multiplication table of Z
_{n}are always 0 since 0*a=0 for all a in Z_{n}; - The second row or column of Z
_{n}lists all elements in Z_{n}since 1 is the identity element in Z_{n}and so 1*a = a for all a in Z_{n}; - If n is a prime p then every column or row contains all elements of Z
_{n}without duplicates since Z sub p is an integral domain;

#4 ensures that there are two distinct types of multiplication table patterns of Z

_{n}depending on whether n is prime or composite. The multiplication table of Z

_{n}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 Z

_{n}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 Z

_{n}, 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 Z

_{n}is Abelian, then

*Alpha_Upside_Down*is simply the inverse of

*Alpha*. The same argument holds for the columns of the multiplication tables of Z

_{n}, 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 Z

_{5}we have (2,4,1,3). Similarly, in Z

_{7}there are (2,4,6,1,3,5), and in Z

_{11}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 Z

_{11 }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 Z_{11} |

Similarly, the 4th row of Z

_{11 }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 k

_{first_last}of the first subset is equivalent to n-(k-1) where k is the row index.

But what happens if the last element k

_{first_last}of the first subset is not equal to n-(k-1)?

In Z

_{11 }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 k

_{first_last }is not equal to n-(k-1), then it appears that the next element after k

_{first_last}is (n - k

_{first_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 Z

_{n }

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(k_{i}*k_{j}, 23)for all rows and columns k _{i, }k_{j}_{ } |

So, to sum up the algorithm for generating the first half of the multiplication table of Z

_{n}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:

- (Generate a subset with starting index k
_{i ,}while starting index k_{i}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) - If the last index of that subset is equal to n - ( k - 1 ) then go to (1.) with k
_{i }= 1, k = k, and table T; - Else if the last index of that subset is equal to n - k then go to (1.) with k
_{i }= 0, k = k+1, and table T; - Else if the last index of that subset is less than n and the row k is less than n/2 then shift new_k
_{i}= k-(n - k_{i}) and go to (1.) with k_{i }= new_k_{i }, k = k, and table T; - 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 Z

_{n}when n is prime.

```
//Author: Marina Ibrishimova
//generating the first half of the multiplication table of Z
```_{n}
//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 Z

_{n}when n is prime, but it is easy to modify the existing algorithm to accommodate for the differences between the multiplication table of Z

_{n}when n is prime and the multiplication table of Z

_{n}when n is the product of 2 or more primes.

The main difference in the multiplication table of Z

_{n}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 k

^{th}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 Z

_{n}when n is the product of 2 or more primes (n-1) may be odd but 2A still holds since Z

_{n}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 Z

_{n}

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.