The self-power map and collecting all residue classes

Abstract:

The self-power map is the function from the set of natural numbers to itself which sends the number $n$ to $n^n$. Motivated by applications to cryptography, we consider the image of this map modulo a prime $p$. We study the question of how large $x$ must be so that $n^n \equiv a \bmod p$ has a solution $1 \le n \le x$, for every residue class $a$ modulo $p$. While $n^n \bmod p$ is not uniformly distributed, it does appear to behave in certain ways as a random function. We give a heuristic argument to show that the expected $x$ is approximately $p^2\log \phi (p-1)/\phi (p-1)$, using the coupon collector problem as a model. We prove the bound $x <p^{2-\alpha }$ for sufficiently large $p$ and a fixed constant $\alpha > 0$ independent of $p$, using a counting argument and exponential sum bounds.