Finite sets containing near-primitive roots

Abstract

Fix $a\in \mathbb{Z}$, $a\notin \{0,\pm 1\}$. A simple argument shows that for each $\hat{I}\mu >0$, and almost all (asymptotically 100% of) primes $p$, the multiplicative order of $a$ modulo $p$ exceeds $p^{\frac{1}{2}-\hat{I}\mu }$. It is an open problem to show the same result with $\frac{1}{2}$ replaced by any larger constant. We show that if $a,b$ are multiplicatively independent, then for almost all primes $p$, one of $a,b,ab,a^{2}b,a{b}^2$ has order exceeding $p^{\frac{1}{2}+\frac{1}{30}}$. The same method allows one to produce, for each $\hat{I}\mu >0$, explicit finite sets $\mathcal{A}$ with the property that for almost all primes $p$, some element of $\mathcal{A}$ has order exceeding $p^{1-\hat{I}\mu }$. Similar results hold for orders modulo general integers $n$ rather than primes $p$.

10 pages + references