So far I’ve only looked at generating exponentiation tables by generating the first phi(n)/2 elements of each row. However, this can also be done by generating the first phi(n)/2 columns instead. At first it seems like a task that will take the same amount of effort but there are a few results that can be used to minimize this effort.

**Theorem 1:**Given two positive integers n and x such that x < n then either

(n-1)

^{x}= 1 mod n if x is even
or

(n-1)

^{x}= n-1 mod n if x is odd
Proof: Direct proof from elementary algebra.

Case 1: If x is even then x = 2k for some positive integer k

(n-1)

^{x}= (n-1)^{2k}mod n
= (n-1)*(n-1)*(n-1)*...*(n-1) mod n 2k factors

= (n

= (0 - 0 + ... - 0 + 1) mod n since any multiple of n is divisible by n

= 1 mod n

Case 2: If x is odd then x = 2k + 1, so

(n-1)

= [(n-1)

= [1 * (n-1)] mod n by Case 1

=(n-1) mod n

.'.

^{2k}- 2kn^{2k}+ ... - 2kn + 1) mod n where ... represents decreasing powers of n= (0 - 0 + ... - 0 + 1) mod n since any multiple of n is divisible by n

= 1 mod n

Case 2: If x is odd then x = 2k + 1, so

(n-1)

^{x}= (n-1)^{2k+1}mod n= [(n-1)

^{2k}]*[(n-1)^{1}] mod n= [1 * (n-1)] mod n by Case 1

=(n-1) mod n

.'.

This result proves that the last row of any exponentiation table mod n is a consecutive sequence of 1 and n-1.

It also suggests that in every even column (a column underneath an even exponent) there will be at least one repetitive element since the last entry in the column is equivalent to the first non-zero entry, namely 1.

Second half of even columns lists the first half in reverse order |

**Claim:**The second half of any

*even*column of the exponentiation table of Z

_{n}when n is the product of two distinct odd primes is equivalent to the first half in reverse order.

Since the column is even, then by Theorem 1 the element at (n-1) is equal to 1, which is equivalent to the element at 1

What remains to be proven is that the element at (n-2) is equal to the element at 2, the element at (n-3) is equal to the element at 3, the element at (n-4) is equal to the element at 4, and so on until the element at (n-1)/2 is reached, which needs to be shown is equal to the element at ((n-1)/2)+1

The proof for this builds upon Claim 2 from Types of Exponents:

(n-1)

^{2}= 1 mod n(n-1)

^{2}= [(n-1)*(n-1)] mod n

= (n

^{2}- 2n + 1) mod n
= (n

^{2}mod n) - (2n mod n) + (1 mod n)
since any multiple of n is divisible by n

= (0 mod n) - (0 mod n) + (1 mod n)

= 1 mod n

More generally, for any integer k such that 1 < k < n

(n-k)

In particular, the second half of the column at 2 in the exponentiation table will simply list the first half of the column in reverse order because:

(n-2)

Similar logic applies for other columns r where r is an integer such that r = 2s for some other integer s since

^{2}= k^{2}mod n since (n-k)^{2 }= n^{2 }- 2nk + k^{2 }= 0 + 0 + k^{2 }^{ }= k^{2 }since any multiple of n is divisible by n so therefore it is 0 mod nIn particular, the second half of the column at 2 in the exponentiation table will simply list the first half of the column in reverse order because:

(n-2)

^{2}= 4 mod n , (n-3)^{2}= 9 mod n, (n-4)^{2}= 16 mod n ,..., and so on up to (n - (n-1)/2))^{2}= ((n-1)/2) = (n - (n-1)/2) + 1 for column 2.Similar logic applies for other columns r where r is an integer such that r = 2s for some other integer s since

(n-k)

To be continued...

^{r }= n^{r }- rn^{r}nk^{ }+ ... - rnk^{r}+ k^{r }= 0^{ }- 0^{ }+ ... - 0 + k^{r}= k^{r}mod n
What remains to be shown is that the element at (n-1)/2 is equal to the element at ((n-1)/2)+1

To be continued...