Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, $\operatorname{ord}_p(2)$ divides $(p - 1)$, so let $r = r_p(2) = \dfrac{p-1}{\operatorname{ord}_p(2)}$. Question: can $r$ be arbitrarily large? That is, given any $M$, does there always exist some $p$ such that $r_p(2) > M$?

(Note that when $2$ is a primitive root modulo $p$, we have $r_p(2) = 1$, so what we're asking for is primes for which $2$ is arbitrarily "far" from being a primitive root.)

One way this would be true is if there are infinitely many Mersenne primes. If $p$ is a Mersenne prime, say $p = 2^q - 1$ for some $q$, then $p$ divides (is equal to) $2^q - 1$, and smaller powers of $2$ are less than $p$, so $\operatorname{ord}_p(2) = q$, and $r_p(2) = \dfrac{p-1}{q} = \dfrac{2^q - 1}{q}$ which can be arbitrarily large if there are infinitely many such $q$.

But of course maybe the answer is yes without assuming the existence of infinitely many Mersenne primes. Is it? Is something known about this problem? (Is $2$ special at all?)

[Source: This question arose on Brian Hayes's blog.]


Yes. We need following consequence of Chebotarev's density theorem: Let $f \in \mathbb{Z}[x]$ be a polynomial. There are infinitely many primes $p$ for which $f$ factors as a product of linear terms.

Let $\phi_M(x)$ be the $M$-th cyclotomic polynomial. Take $f(x) = \phi_M(x)(x^M-2)$. Let $p$ be a prime so that $f(x)$ splits into linear factors modulo $p$. Since $\phi_M(x)$ has a root mod $p$, there is a primitive $M$-th root of unity in $\mathbb{F}_p$ and $M|p-1$. Since $x^M-2$ has a root modulo $p$, we see that $2=a^M \bmod p$ for some $a$. Then $2^{(p-1)/M} \equiv a^{p-1} \equiv 1 \bmod p$ and $M|r_p(2)$.

| cite | improve this answer | |
  • $\begingroup$ Sorry for the delay in marking this as accepted. I was holding off because I hoped to learn and understand the proof of this very useful theorem first, but I don't seem to be getting the time for it right now. Meanwhile I was wondering if there might be a more elementary proof that doesn't require such heavy machinery, but it seems unlikely, now that I think of it more. (Next comment.) $\endgroup$ – ShreevatsaR May 11 '13 at 17:03
  • $\begingroup$ Meanwhile, I'm also convinced that there cannot be a much more elementary proof than this. Writing this proof backwards, for my own understanding: Let $r_p(2)=M$, and $\operatorname{ord}_p(2)=N$, so that $p-1=MN$. Considering some primitive root $a$ of $p$, we have $2\equiv a^k$ for some $k$, and as $1\equiv2^N\equiv a^{kN}$, we need $(p-1)|kN$, so $M|k$ and $2\equiv a^k=(a^{k/M})^M$. So we do necessarily need $p$ to satisfy both that $M|p-1$, and that $2$ is $x^M$ for some $x$ (i.e., $x^M-2$ has a root mod $p$). Something like Chebotarev's density theorem is probably needed to guarantee this. $\endgroup$ – ShreevatsaR May 11 '13 at 17:03

Your Answer

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

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