tetration primitive root $q \mod p$

Question

Consider primitive roots $q \mod p$ where $q$ is a prime and $p$ is an odd prime $> 5$.

I am looking for such pairs $q,p$ such that every residue $a_i \mod p$ is of the form

$$a_i = q^{(v_i)} \mod p$$

where $q^{(a+1)} = q^{q^{(a)}}$, in other words tetration or power towers with base $q$ and height $a+1$.

This means that

$q,q^q,q^{q^q},...$ are maximally distinct residues $\mod p$. In fact they are (not in order) $1,2,3,...,p-1$

This is essentially saying that $q$ is a “generator” with respect to tetration and residues $\mod p$.

I am looking for examples of such $q$ and $p$. Or proof they can not exist.

Lets call them “tetration primitive roots”.

I know $q^p = q$ (Fermat's little) and that $q,q^2$ can not both be primitive roots (because $p-1$ is even).

To demonstrate let me show some examples of primitive roots that are not tetration primitive roots (so not the answers I want):

$5,3$ are primitive roots $\mod 7$ so

$5^1 = 5 \mod 7$

$5^2 = 4 \mod 7$

$5^3 = 6 \mod 7$

$5^4 = 2 \mod 7$

$5^5 = 3 \mod 7$

$5^6 = 1 \mod 7$

$5^7 = 5 \mod 7$

---

$5^1 = 5$

$5^5 = 3$

$5^3 = 6$

$5^6 = 1$

---

$5^2 = 4$

$5^4 = 2$

---

$3^1 = 3 \mod 7$

$3^2 = 2 \mod 7$

$3^3 = 6 \mod 7$

$3^4 = 4 \mod 7$

$3^5 = 5 \mod 7$

$3^6 = 1 \mod 7$

$3^7 = 3 \mod 7$

---

$3^1 = 3$

$3^3 = 6$

$3^6 = 1$

---

$3^2 = 2$

---

$3^4 = 4$

---

$3^5 = 5$

---

So neither $5$ or $3$ is a “tetration primitive root” of $7$, since they make multiple cycles and fixpoints rather then generating every residue.

Answer 1

A computer search reveals several such pairs with $5<p<1000$, namely $(q,p) = (241, 311)$, $ (41, 331)$, $ (97, 359)$, $ (53, 389)$, $ (13, 487)$, $ (311, 509)$, $ (23, 547)$, $ (173, 653)$, $ (263, 751)$, $ (113, 811)$, $ (103, 907)$, $ (401, 907)$, and $ (709, 941)$.

Note that there's no particular reason why $q$ must be prime; without this restriction there are many smaller examples, starting with $(20,23)$ and $(6,41)$.

Probabilistic heuristics suggest that there are infinitely many such pairs $(q,p)$, and that a positive proportion of primes $p$ have such a $q$ if we don't restrict $q$ to be prime:

• There are $\phi(p-1)$ primitive roots modulo $p$, and $\phi(p-1)$ integers between $1$ and $p-1$ that are relatively prime to $p-1$; so we expect about $\frac{\phi(p-1)^2}{p-1}$ primitive roots $q$ in that range that are relatively prime to $p-1$, which gives them a chance at being tetration primitive roots.
• The map $n\mapsto q^n$ (mod $p$) permutes $\{1,\dots,p-1\}$, and we might support that it's a random permutation; and there's a $\frac1{p-1}$ chance that a random permutation of $p-1$ objects is a $(p-1)$-cycle.
• So we expect about $\frac{\phi(p-1)^2}{(p-1)^2}$ valid integers $q$ for a given $p$; and $\frac{\phi(p-1)^2}{(p-1)^2}$ has a positive average value when averaged over primes.
• We also expact about $\frac{\phi(p-1)^2}{(p-1)^2\log p}$ of these valid integers to be primes; and $\sum_p \frac{\phi(p-1)^2}{(p-1)^2\log p}$ diverges.