28.11.14

Types of Exponents

Definition: A universal exponent of the positive integer n is a positive integer U such that

aU = 1 mod n

for all integers a relatively prime to n

Example 1: By Euler's theorem

aφ(n) = 1 mod n 

for all a relatively prime to n. Therefore, φ(n) is a universal exponent of n.

Example 2: By Claim 1 that I proved here, if n is the product of two distinct primes both greater than 2, then:

 aφ(n)/2 = 1 mod n 

for all a relatively prime to n. Therefore, φ(n)/2 is a universal exponent of n.

Clearly, when n is the product of two distinct primes both greater than 2, then n has at least 2 universal exponents, namely φ(n) and φ(n)/2. Although I proved this logically, the behaviour can be observed in any exponentiation table in Zwhen n is the product of two distinct primes both greater than 2.

Example 3: Below is the exponentiation table for Z35 where n = 5 * 7 = 35, the smallest safe primes.
φ(35) = (5-1)*(7-1) = 24  and φ(35)/2 = 24/2 = 12 and so note the column below the 24th exponent and the 12th exponent and see how identical they are.



Universal exponents are useful but there are other types of exponents that prove to be useful in generating exponentiation tables of Zn.

In the Exponentiation tables in Zn  post I observed several peculiar behaviours of specific tables, which need to be proven in general.

Claim 2: Given a positive integer n, then

(n-1)2 = 1 mod n

Proof: A nice and simple direct proof from elementary algebra.

(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

.'.

This gives rise to an even bigger claim and its proof explains why the last row of any exponentiation table is a repetition of 1 and n-1

Claim 3:  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: Again, 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

.'.

In Finding Phi it was shown that φ(n) is even and in fact it is 2x even in the case when n is the product of two distinct odd primes p and q since φ(n) = (p-1)(q-1) and since p and q are both odd primes then both (p-1) and (q-1) are even integers.

By definition of an even integer,
(p - 1) = 2r 

for some positive integer r strictly smaller than p and 

(q - 1) = 2s 

for some positive integer s < q, so multiplying (p-1) times (q-1),

φ(n) = (p-1)*(q-1) = 2r * 2s = 4rs

So φ(n)/2 = (4rs)/2 = 2rs and since the order of any integer smaller than and relatively prime to n  divides φ(n)/2 when n is the product of two odd primes, then the following different types of smallest exponents, or finite orders of integers relatively prime to n in the cyclic group Zn  are possible:

  1. a2rs  = 1 mod n  
  2. brs = 1 mod n
  3. cr = 1 mod n
  4. ds = 1 mod n
  5. e2 = 1 mod n
  6. 2r  = 1 mod n  
  7. g2s  = 1 mod n  
where a,b,c,d,e, r, s are all positive integers.

Example 4: Clearly (n-1) belongs to the 5th type since it was proven in Claim 2 above that

(n-1)2 = 1 mod n