27.1.15

Exponentiation tables in Z sub p when p is prime

There's a lot going on in exponentiation tables of Z sub n when n is the product of two distinct primes both greater than 2. For one thing, we have two universal exponents, which means that every element goes through at least 2 cycles.

In other words, there will never be an element of order φ(n) in Zn when n is the product of two distinct odd primes. The largest order of any element in Zwhen n is the product of two distinct odd primes can be φ(n)/2 at most.

This is not the case in Zwhen n is just a single prime integer p because according to Theorem 1, a prime integer p has at least 1 primitive root, or in other words, it will have at least one integer r such that rφ(p) = 1 mod p and φ(p) is the order of r, or in other words φ(p) is  the smallest such exponent where this equation holds true and so therefore the only universal exponent is going to be φ(p) since, by Euler's theorem, for every a in  Zp  where p is a prime integer aφ(p) = 1 mod p   

To paraphrase Theorem 1 from Finding Phi :

An array of length n that consists of consecutive positive integers starting from 0 to n-1 has an element r such that:

rφ(n) = 1 mod n and φ(n) is the smallest such exponent 

if and only if n is either of the form  pt, or 2p where p is prime and t is any positive integer in Z

So clearly when n = p  and p is prime the only universal exponent is φ(n) = φ(p) = p - 1, which means that a single row will generate the entire exponentiation table! For most  many primes that row is the row at 2.

More generally speaking, the row that generates the entire exponentiation table of Zp  where p is a prime integer is the row at the smallest primitive root of p.

Below are a few examples of the exponentiation tables for Z5, Z7, and Z11 respectively:



The smallest primitive root when p = 5 is 2, the smallest primitive root for p = 7 is 3, and the smallest primitive root for p = 11 is 2 because a primitive root r for a prime p is by definition a positive integer where φ(p) is the smallest exponent for which the equation rφ(p) = 1 mod p holds true.


Since φ(p) is the smallest exponent for which the equation rφ(p) = 1 mod p holds true, then from Group theory, φ(p) is the order of r and so therefore all exponents of r up to φ(p) must produce unique integers mod p, or in other words the row at the primitive root in the exponentiation table of  Z contains all integers in Zp except for 0, namely, it contains some permutation of [1,2,3,...,n-1], since:

Theorem: Let G be a group and a in G:

i)  if an element a in G has a finite order b, then ak = 1 if and only if b divides k.

ii) if an element a in G has a finite order b, then ai= aj if and only if i - j is divisible by b, in particular the elements a0a1a2a3,...,ab-1, are all unique.

Proof: 

i)
=> (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 .'.  

ii) This follows from i) since ai= aj if and only if ai-j= 1 and this is true if and only if i-j divides the order of a.


So clearly, the first step in the algorithm for generating exponentiation tables in Zp when p is prime is:

1. Find the smallest primitive root of p (which becomes a question of finding out what type of a prime p is)

The next steps in the algorithm for generating exponentiation tables in Zp when p is prime are:

2. Generate the row at the primitive root

3. For each subsequent row k, shift the row at the primitive root by the number of integers that k is from the initial index

Example 1:  Z13 
1. The smallest primitive root of 13 is 2 because 2 is the smallest integer for which:
2φ(13) =  2(13 -1)  = 1 mod 13

2. using a slightly modified version of the findO2 algorithm, I get:
the row at 2 = [1,2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1]

3. I don't need to do anything else, I just shift.
For example,  3 is 3 integers away from 1 in the row at 2 , so the row at 3 becomes
[1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1]
Similarly, 4 is 1 integer away from 1 in the row at 2 so the row at 4 becomes
[1, 4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1]

And so on ...