21.10.15

Exponentiation Tables From Another Perspective

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.

The following theorem, which I first claimed and proved in Types of Exponents suggests something very interesting regarding two types of exponents that can be useful in generating exponentiation tables faster: namely even exponents and odd exponents.

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
= (n2k - 2kn2k + ... - 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 Zn 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
= (n2 - 2n + 1) mod n 
= (n2 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)2 k2 mod n   since  (n-k)n- 2nk + k2   = 0 + 0 + k2  ksince any multiple of n is divisible by n so therefore it is 0 mod n

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)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)=  nr  -  rnrnk  + ... - rnkr  + kr  = 0  -  0  + ... -  0 + kr = kr 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...