Let $q$ be a prime number, and let $k={\rm ord}_q\ 2$, the multiplicative order of 2 modulo $q$. Is there a known upper bound (a function depending on $p$, maybe) to the number of primes $p$ such that $k={\rm ord}_p\ 2$?

  • 2
    $\begingroup$ You don't want a bound that depends on $p$, since you're trying the bound the number of $p$. There are various ways to approach this. For example, it is known that the sum $\sum_p \frac{\log p}{\text{ord}_p(2)^\epsilon\cdot p}$ converges for all $\epsilon>0$ (with an explicit upper bound), from which one can should be able to deduce a bound for $\#\{p : \text{ord}_p(2)=k\}$, since $\sum_p\frac{\log p}{p}$ diverges. $\endgroup$ – Joe Silverman Nov 25 '18 at 12:24
  • 1
    $\begingroup$ Isn't $|\{ p:ord_p(2) = k\}|$ bounded by number of prime divisors of $2^k - 1$? $\endgroup$ – Aleksei Kulikov Nov 25 '18 at 12:49
  • 2
    $\begingroup$ Thanks for both comments above. Right, Joe, my bad. So if we look at Aleksei's comment, and let $n=2^k-1$, the question would be if there is a better bound than the best known bounds for the number of prime divisors of $n$, ($O(\log n/\log\log n$) let us say, something like $O(\log^x n)$, $0<x<1$. I suspect the truth might be something like $O(\log\log n)$. Thanks again. $\endgroup$ – EGME Nov 25 '18 at 13:16
  • 1
    $\begingroup$ Are you willing to assume the GRH, or you rather want something that can be proved unconditionally? (By the way: there are stronger unconditional bounds than the one in Joe's comment, e.g. the basic bound $\mathrm{ord}_p^{\times}{2} > \sqrt{p}$ holds outside of a set of primes with a convergent $\sum \log{p} / p$. No one knows how to raise the exponent $1/2$ here, although the GRH is known to give any exponent $\kappa < 1$. For all of this you may consult Pappalardi's paper On the order of finitely generated subgroups$\ldots$, and I'd be happy to say more if you're fine with assuming GRH.) $\endgroup$ – Vesselin Dimitrov Nov 25 '18 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.