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?

  • 1
    $\begingroup$ 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. $\endgroup$ – user35593 May 4 '15 at 14:27
  • $\begingroup$ Oh - typo... it should be $\{1,\ldots,c-1\}$. Thanks for pointing it out! $\endgroup$ – Dominic van der Zypen May 4 '15 at 14:27
  • 2
    $\begingroup$ 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. $\endgroup$ – 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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.