# 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.]

-
@labbhattacharjee: Actually, that doesn't answer this question at all, because in that case, $r_q(2) = 1$ (as $2$ is in fact a primitive root), not arbitrarily large. What we want here is for $2$ to be arbitrarily far from being a primitive root. –  ShreevatsaR May 7 '13 at 5:42
Fermat number $F_n=2^{2^n}+1,2^{2^n}\equiv-1\pmod {F_n}\implies ord_{(F_n)}2=2^{n+1}$. If $F_n$ is prime $=p,$ the ratio $=\frac{2^{2^n}}{2^{n+1}}=2^{(2^n-n-1)}$. But, there are only $5$ known Fermat's prime (mathworld.wolfram.com/FermatPrime.html) –  lab bhattacharjee May 7 '13 at 7:41
Why the downvote? –  ShreevatsaR Jan 8 '14 at 17:14

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