Exponential Iteration

Obviously x^n (mod p) is not generally congruent to (x mod p)^(n mod p), 
but it's interesting to consider situations in which the residue class 
of an exponent actually does determine its behavior.  Consider a simple 
exponential recurrence of the form  

                x[k+1]   =   x[k]^n       (mod p)

Beginning with some initial value x[0] = b this recurrence generates 
the values b^(n^j), j=0,1,2,...  The question is this: When do these 
values "cover" the residue classes (mod p)?  Here the term "cover" 
means that every residue class, up to sign, other than 0 and +-1, 
occurs in the sequence of x iterates.  In other words, every 
residue class (mod p) other than 0 and +-1 can be expressed in 
the form +- b^(n^j).

I believe the answer is that the values of +-b^(n^j) cover the 
residues (mod p) if and only if both p and q=(p-1)/2 are primes AND 
n is a primitive root (mod q).  Thus, when considering the set of 
values (without regard to order) produced by iteration of x^n, it is 
sufficient to consider just residue class of n (mod q).

Interestingly, an exponential covering requires that q be a "Germain
prime", i.e., a prime such that 2q+1 is also a prime.  These are 
related to the "first case" of FLT.  It's not known if there are 
infinitely many such primes, although empirically they are not too 
uncommon.

Suppose we want the allowable exponents n in our covering iteration 
to be "maximized".  By this I mean that every non-square residue 
(mod q) should be a primitive root (excluding -1 of course).  This 
happens precisely then (q-1)/2 = phi(phi(q))+1, which implies that 
w=(q-1)/2 must be a "Germain prime" also.

Sequences of primes such as w,q,p, where each prime is one greater 
than twice the previous one, are called Cunningham chains.  (R. Guy 
reports that Gunter Loh found a chain of length 13 beginning with 
the prime 758083947856951.)