# Powers modulo a fixed integer

We say that a set $A\subseteq \mathbb{N}$ has positive measure if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} > 0.$$

For $b\in\mathbb{N}$ with $b>1$ we consider the sets $$S_b := \big\{c\in\mathbb{N}:\{b^n \text{ mod } c:n\in\mathbb{N}\}=\{1,\ldots,c-1\}\big\}.$$

Is there $b>1$ such that $S_b$ has positive measure?

Is there $b>1$ such that $S_b$ has not positive measure?

• If $c\in S_b$ it has to be coprime to $b$. By Euler's theorem $S_b$ can only contain primes. Hence by the prime number theorem $S_b$ has not positive measure. – user35593 May 4 '15 at 14:27
• Oh - typo... it should be $\{1,\ldots,c-1\}$. Thanks for pointing it out! – Dominic van der Zypen May 4 '15 at 14:27
• To expand on user35593’s comment: even if the requirements were loosened so that $\{1,\dots,c-1\}$ is replaced with $\{u<c:(u,c)=1\}$, $(\mathbb Z/c\mathbb Z)^\times$ is cyclic only for $c$ of the form $p^k$ or $2p^k$, so $S_b$ would still be of density $0$. The sensible question is to ask for relative density of $S_b$, in the primes, which more or less amounts to Artin’s primitive root conjecture. – Emil Jeřábek May 4 '15 at 14:49

As written, the question seems to have a problem (pointed out by user35593): If the powers of $b$ really give all of $1, 2, \dots, c-1$ mod $c$, then $c$ must be prime, and so certainly we do not get positive measure. (By the way, the term positive lower density'' seems more standard in this context.)

So let me answer a different question: Fix an integer $b$, and ask for positive integers $n$ where the powers of $b$ generate a cyclic subgroup of maximum possible size. In other words, we want integers $n$ for which the order of $b$ mod $n$ is the exponent of the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$. Do we get positive lower density here?

If we restrict our universe to prime $n$, there's a well-known conjecture of Artin that the answer is usually yes. For instance, if $b=2$, then about 37.4% of primes $n$ should have the stated property.

What if we don't restrict to prime $n$? There's a beautiful theorem of Shuguang Li that for every fixed $b$, the answer is no. The lower density of such $n$ is always $0$.

On the other hand, for most $b$, the upper density (defined as before but with $\limsup$ replacing $\liminf$ is positive), at least if you believe GRH (a result of Li and Pomerance).

All of this is explained better than I have done here in this paper of Li and Pomerance: https://math.dartmouth.edu/~carlp/PDF/primitiverootstoo.pdf

• Indeed my question has the problem you mention -- thanks for providing a better question along with a beautiful answer! – Dominic van der Zypen May 4 '15 at 18:18