Results and estimates on pseudopowers

Abstract:

Let $n$ be a positive integer. We say $n$ looks like a power of 2 modulo a prime $p$ if there exists an integer $e_p \geq 0$ such that $n \equiv 2^{e_p} (\operatorname {mod} {p})$. First, we provide a simple proof of the fact that a positive integer which looks like a power of $2$ modulo all but finitely many primes is in fact a power of $2$. Next, we define an $x$-pseudopower of the base $2$ to be a positive integer $n$ that is not a power of $2$, but looks like a power of $2$ modulo all primes $p \leq x$. Let $P_2 (x)$ denote the least such $n$. We give an unconditional upper bound on $P_2 (x)$, a conditional result (on ERH) that gives a lower bound, and a heuristic argument suggesting that $P_2 (x)$ is about $\exp ( c_2 x / \log x)$ for a certain constant $c_2$. We compare our heuristic model with numerical data obtained by a sieve. Some results for bases other than $2$ are also given.