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 Z

In other words, there will never be an element of order φ(n) in Z

_{n }when n is the product of two distinct odd primes. The largest order of any element in Z_{n }when n is the product of two distinct odd primes can be φ(n)/2 at most.
This is not the case in Z

_{n }when 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 Z_{p}where p is a prime integer a^{φ(p)}= 1 mod p
An array of length n that consists of consecutive positive integers starting from 0 to n-1 has an element r such that:

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 Z

Below are a few examples of the exponentiation tables for Z

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

So clearly, the first step in the algorithm for generating exponentiation tables in Z

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 Z

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

1. The smallest primitive root of 13 is 2 because 2 is the smallest integer for which:

2

2. using a slightly modified version of the findO2 algorithm, I get:

3. I don't need to do anything else, I just shift.

For example, 3 is 3 integers away from 1 in

[1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1]

Similarly, 4 is 1 integer away from 1 in

[1, 4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1]

And so on ...

r

^{φ(n)}= 1 mod n and φ(n) is**the smallest such exponent**__n is either of the form p__

**if and only if**^{t}, or 2p

^{t }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

More generally speaking, the row that generates the entire exponentiation table of Z

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

_{5}, Z

_{7}, and Z

_{11}respectively:

^{φ(p)}= 1 mod p holds true.

Since φ(p) is the smallest exponent for which the equation r

i)

ii)

Proof:

i)

=> (if a

Suppose a

So:

It follows that a

However, since b is the smallest integer such that a

^{φ(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_{p }contains all integers in Z_{p}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)

**i**f an element a in G has a finite order b, then a^{k}= 1__if and only if__b divides k.ii)

**i**f an element a in G has a finite order b, then a^{i}= a^{j}if and only if i - j is divisible by b, in particular the elements a^{0}, a^{1}, a^{2}, a^{3},...,a^{b-1}, are all unique.Proof:

i)

=> (if a

^{k}= 1 then b divides k)Suppose a

^{k}= 1 and b is the order of a. By definition, an order of an element is the smallest integer b such that a^{b}= 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 = a

^{k}= a^{b*c + r}=(a^{b*c}) * a^{r}=((a^{b})^{c}) * a^{r}= 1^{c}*a^{r}= a^{r }It follows that a

^{r }= 1 where r is some positive integer 0 <= r < b.However, since b is the smallest integer such that a

^{b}= 1 then r must be equal to 0, therefore k is divisible by b .'.
ii) This follows from i) since a

^{i}= a^{j}if and only if a^{i-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 Z

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

_{p}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: Z**

_{13 }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 ...