# Fixed points of $g^x$ (modulo a prime)

In an explicit construction in combinatorics I need to study the following problem: assume we pick a odd prime number $p$, a generator $g$ of the multiplicative group $(Z/pZ)^{\ast}$.

Question 1: for how many $x\in\{2,\dots,p-2\}$, is it true that $x\equiv g^x\, (p)$.

Question 2: how the previous counting depends on the choice of $g$?

In general I would need indeed the number of solutions of the congruence equation $x\equiv a+g^x\, (p)$ (for fixed $a$), but already the base case $a=0$ is interesting for me.

Just to take an arbitrary example, mod $p = 23$ there are $\phi(22) = 10$ primitive roots. Of those, four ($14, 19, 20, 21$) have no solutions to $x \equiv g^x \mod 23$, two have one, three have two, and one ($11$) has five.

Here, for each of the first $30$ primes, are the number of primitive roots $g$ for which there are no solutions to $x \equiv g^x \mod p$ with $2 \le x \le p-2$:

$$1, 1, 1, 1, 2, 1, 1, 3, 4, 2, 1, 6, 5, 2, 9, 11, 12, 5, 7, 9, 8, 8, 17, 12, 11, 16, 12, 23, 20, 16$$

This sequence does not seem to be in the OEIS (yet).

[EDIT: Although this one is not in OEIS, the number of $g$ for where there are solutions is: OEIS sequence A174407].

For each prime $< 1000$, the number of such $g$ is at least $1$.

The probability of a random permutation of $[1\ldots p-1]$ being a derangement is approximately $1/e$, so heuristically we might expect about that fraction of the primitive roots to have no solution to $x \equiv g^x \mod p$.

• Maybe we should not include $g=\pm1$ in the discussion, as these are not generators? – T. Amdeberhan May 9 '17 at 21:55
• This was just counting generators $g$. – Robert Israel May 9 '17 at 22:59
• Dumb (?) question: Is it obvious there should be at least one generator with no fixed points for each odd prime? – kodlu May 10 '17 at 22:37
• No, it is not at all obvious to me. Heuristically, if the probability of a generator having no fixed points is about $1/e$, and there are $\phi(p-1)$ generators, the probability that none of them have a fixed point is about $(1-1/e)^{\phi(p-1)}$, and this goes to $0$ rapidly enough that it's not surprising. But that's not a proof. – Robert Israel May 10 '17 at 23:04
• @RobertIsrael The paper by Levin, Pomerance and Soundararajan pointed out in the comment to the question by Lucia actually proves this. – kodlu May 11 '17 at 1:53