8.10.14

Exponentiation Tables in Z sub n

The following post describes Zunder exponentiation where n is the product of two primes.  Each entry in each exponentiation table here is constructed by raising the row index a to the power of the column index b mod n. Note that since this construction is not Abelian the opposite statement does not hold in its exponentiation tables. The post was inspired by a small discovery I came across while taking CMPUT 210 at the University of Alberta.

Zn is closed with respect to exponentiation since for all a, b in Zn, ab = a*a*a*a*... (b factors) and since Zn is closed with respect to multiplication then a*a*a*a*... (b factors) is also in Zn.

However, Zn under exponentiation is not Abelian since ab is not always congruent to ba mod n, therefore most of what was said about multiplication tables in Z sub n and addition tables in Z sub n doesn't necessarily hold.


In fact, Zn under exponentiation as constructed below where n is the product of two primes is not even a group.


So, is it still possible to generate exponentiation tables for Z without actually computing the greatest common divisor of (ab, n) for all a and b in Zn?



To answer this question, let's consider a few statements first.
  1. 0a is 0 for all a in Zn, therefore the first row of every exponentiation table is all 0s, except 00, since it is assumed 00 = 1.
  2. For all a in Zn, a0 is 1 by construction, therefore the first column of every exponentiation table is all 1s.
  3. For all a in  Zn, a1 = a by construction, therefore the second column of the exponentiation table for Zn is equal to the row index, meaning that it lists all elements of Zin order of smallest to largest.
  4. Fermat's Little Theorem states that if n is prime, then an-1 = 1 mod n, therefore the last column of every exponentiation table for Z when n is prime is all 1s, except for the first entry, which is 0 since 0n-1 is 0 for n>1 
  5. Euler's theorem states that if the greatest common divisor GCD(a,n) = 1 for 2 integers a and n, then aφ(n) = 1 where φ(n) = (p-1)*(q-1) if n = p*q with p & q prime.
     
The first few statements ensure that under exponentiation when n is prime no row of the table will list Zn in its entirety since there will always be at least 2 entries with 1s: one at the first index and one at the very last index, namely n-1. However, there will still be rows that list (n-2) of all members of Zn since n is prime and (a,n) = 1 for all a in Zn

Below are a few examples of exponentiation tables for Zn when n is prime.


Remark: The exponentiation tables as constructed here are not Cayley tables. Instead, each entry in each exponentiation table here is constructed by raising the row index a to the power of the column index b mod n. Note that since this construction is not Abelian the opposite statement does not hold in its exponentiation tables.



Each entry in each table is ab mod n where a is the row index
of the table and b is the column index of the table

On the other hand, when n is composed of 2 primes, say p and q, then there will be rows that have common divisors with n (such rows will be row p, row q, and any products of p or q with other integers in Zn), therefore the only entry with 1 in such rows is going to be the very first entry of the row when the column index b=0, namely a0           

(Proposition B)


Below are a few exponentiation tables for n when n is composed of two primes.




Each entry in each table is ab mod n where a is the row index
of the table and b is the column index of the table


Proposition C: An interesting observation one might have is that an entry in the last row of the table is either 1 if the column index is even, or (n-1) when the column index is odd.

Proposition D: Another interesting observation is that each row contains repetitive subsets of integers, therefore if the first subset in a row is known, then the whole row is known.

For example, in Z15 where 15 = 3 * 7 and both 3 & 7 are prime, the third row where the row index a=2, there exist the following consecutive sets: 2b = {(1,2,4,8),(1,2,4,8),(1,2,4,8),(1,2,4)} mod 15 where b = 1,2,3,4,5,...,14 respectively.





An interesting observation one might have is that the first set in the 8th row when a = 7 is (1, 7, 4, 13) repeated throughout the row and then the first set in the 14th row when a = 13 is (1, 13, 4, 7), which is the mirror image of the first set in the 8th row when a = 7. The same can be said about the 13th row when a = 12 and the 3rd row when a = 3, and so on.


As predicted in (B), rows where the row index a divides n=15 do not contain 1s in their cycles and the only entry with 1 in such rows is the first entry of the row,  for example the 6th row where a=5, the row is {(1),(5,10),(5,10),(5,10),(5,10),(5,10),(5,10),(5,10)}


a=5 in Z15 is an element with an infinite order since the greatest common divisor of (5, 15) is not equal to 1.


Definition 1  An element in a groupoid either has a finite order if there exists an integer d such that ad = 1 mod n and d is the smallest positive integer such that ad = 1 mod n,  or an infinite order if gcd(ad, n)  > 1 for all d in Z.


Claim: If an element a in Zn under exponentiation has a finite order b, then ak = 1 if and only if b divides k.


Proof:

=> (if ak = 1 then b divides k)
Suppose ak = 1 and b is the order of a. By definition, an order of an element is the smallest integer b  such that ab = 1. By the Euclidean algorithm,  k can be represented as k = b*c + r  for some positive integers c, r where 0 <= r < b .

So:

1 = ak = ab*c + r=(ab*c) * ar=((ab)c) * ar = 1c*ar = ar  

It follows that  a= 1 where r is some positive integer 0 <= r < b.


However, since b is the smallest integer such that ab = 1 then r must be equal to 0, therefore k is divisible by b .'.  


<=  (if b divides k then ak = 1)


Suppose k is divisible by b so that k = b*c for some c, then:



ak = ab*c=((ab)c) = 1c = 1 


.'.
(G)

Clearly, since n is composed of more than a single prime there are elements with finite orders and elements with infinite orders
in Zn under exponentiation.

Conjecture 1: The order of an element with a finite order in Zn under exponentiation when n=p*q with p,q prime divides (φ(n)/2).


Proof: See the post titled Finding Phi.


Assuming this conjecture is true then it is clear that:

Proposition F: given an element a with finite order d in in Zn under exponentiation so that ad = 1, there will be at least two cycles in the row of a of the exponentiation table, which ensures that if ab = m then ab + d = m. 

Let's consider one more example when n is composed of 2 safe primes, in this case the smallest safe primes.


Note: most iPhone apps can't handle anything above a certain magical number somewhere on this table but Windows (scientific) calculator is solid for even larger computations than the ones needed below.



Z35 under exponentiation
As predicted in Conjecture 1, the order of each element with finite order divides φ(n)/2 since φ(n)=(p-1)(q-1) and φ(35)=(5-1)*(7-1)=4*6=24 and the largest order that an element in Z35 under exponentiation has is equal to 12.

Note that even elements with infinite order exhibit the same kind of cyclic nature under exponentiation, for example the repeated cycle when a=7 is (7,14,28,21) for b > 0 in Z35 under exponentiation.

Generally speaking, Conjecture 1 hints at the first, most inelegant solution to the question posed at the beginning, namely "Is it still possible to generate exponentiation tables for Z without actually computing the greatest common divisor of (ab, n) for all a and b in Zn?"

To generate an exponentiation table for Zn, one has to compute the greatest common divisor of (ab, n) for only the first half of each row a, which will contain at least one cycle. In fact, one should stop computing the rest of the row as soon as either the last computed element is equal to 1 or the last computed element is equal to the value of row a. 

The rows with the longest cycles are φ(n)/2 long, which means that the rows with the longest cycles can provide the value of φ(n) even if the two primes that make up n are unknown but by all means don't take my word for it. Also given any integer a < n  and b < n  ab = m mod n, there is at least one other integer d < n such that ad = m mod n

Anyway, back to the important question here, which I now transform to the following:

Is it still possible to generate exponentiation tables for Z without actually computing the greatest common divisor of (ab, n) for any a and b in Zn? 

Well, let's look at  Z35 under exponentiation. It, like the ones before it (and the ones after it as I shall attempt to prove at some point in my life) exhibits an interesting pattern. Let's look at all finite elements with largest order. Note that they are all intertwined in the following manner:



An interesting observation one might have is that the cycle is reversed when the row index a is equal to the last element in a previous cycle. For example, when a = 2, the cycle is (1,2,4,8,16,32,29,23,11,22,9,18, 1) so that when a = 18 the cycle will be (1,18,...,29,32,16,8,4,2,1). Similarly when a= 3, the last element of the cycle before it starts again is 12 so the cycle at row 12 is the cycle of row 3 but reversed. In other words, each cycle traced reveals not only the full row but also another row and the generation of this other row requires no computations whatsoever.

Now let's take a look at the cycle of an element with a smaller order. For example, when a = 4, the cycle is just (1,4,16,29,11,9,1). Clearly, when a =9, the cycle will be (1,9,11,29,16,4,1) as it is. But there is something even more interesting going on here. 

Where is 4 in the previous cycle of largest order when a = 2? It's right after 2, so a bold prediction one might have is that the cycle at a =  4 will be the cycle at a = 2 shifted by 1 so that the cycle at a = 4 contains every second element of the cycle at a = 2 until it reaches 1 again, which resets the cycle. Let's test out this bold prediction when n = 16. 

16 is also an element of the cycle at row a = 2 where it is the 4th element after 2, so it is shifted by 4. The next element in the cycle at a=16 should be the 4th element after the position of 16 in the cycle at a = 2, which is 11. The next element in the cycle at a=16 should be the 4th element after the position of 11 in the cycle at a = 2, which is 1, so the cycle at a = 16 should be (1, 16, 11, 1), which it is since 16^2 mod 35 = 11 and 16^3 mod 35 = 1.

 
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. You should be afraid.