Counting all $n$ with $p\mid n^n -1$ for given $p$ prime

Question

Say I have a prime $p$. I choose a number $n$ in the interval $[1, p^{p}]$ so that $p$ divides $n^{n}{-}1$. Now, can we quantify the cardinality of the set containing all possible values of $n$?

Answer 1

The expression $n^n\bmod p$ has the base periodic with period $p$ and the exponent periodic with period $p-1$, therefore the expression $n^n\bmod p$ itself has period $p(p-1)$.

The solutions to $n^n\equiv1$ mod $p$ can be constructed from residues $n\equiv k$ mod $p$ by solving

$$ \begin{cases} n\equiv k \bmod p \\ n\equiv 0 \bmod |k| \end{cases} $$

where $|k|$ is the multiplicative order of $k$ mod $p$. These solutions have period $p|k|$, so in the interval $[1,p(p-1)]$ there are $(p-1)/|k|$ such solutions, and the total number is

$$ f=\sum_{k\bmod p} \frac{p-1}{|k|}. $$

Note $k=0$ is excluded. The multiplicative group of integers mod $p$ is cyclic of order $m=p-1$, so there are $\phi(d)$ elements $k$ of order $|k|=d$ for every divisor $d\mid m$. So we may write

$$ f=m\sum_{d\mid m}\frac{\phi(d)}{d}. $$

Since $\phi(d)/d$ is multiplicative, so too is the sum as a function of $m$, so it suffices to evaluate for $m=q^s$ a prime power, which yields $\sum_{t=0}^s \phi(q^t)/q^t=1+s(1-1/q)$, so this expression is

$$ f=m\prod_{q\mid m}\left[1+v_q(m)\left(1-\frac{1}{q}\right)\right], $$

where $q$ runs over prime divisors of $m$.

Since $p^p\equiv p\bmod p(p-1)$, the # of solutions to $n^n\equiv 1$ mod $p$ in the interval $[1,p^p]$ is

$$ N=\frac{p^{p-1}-1}{p-1}f+g $$

where $g$ is the number of solutions in the interval $[1,p]$ (which I expect has no formula).