  Fix $a \in \mathbb{Z}$, $a\notin \{0,\pm 1\}$. A simple argument shows that
for each $\epsilon > 0$, and almost all (asymptotically 100% of) primes $p$,
the multiplicative order of $a$ modulo $p$ exceeds $p^{\frac12-\epsilon}$. It
is an open problem to show the same result with $\frac12$ 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^2b, ab^2$ has order exceeding
$p^{\frac{1}{2}+\frac{1}{30}}$. The same method allows one to produce, for each
$\epsilon > 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-\epsilon}$. Similar results hold for orders modulo general integers $n$
rather than primes $p$.
