# Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

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)$.

• 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.) – ShreevatsaR May 11 '13 at 17:03
• 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. – ShreevatsaR May 11 '13 at 17:03