Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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 ( – lab bhattacharjee May 7 '13 at 7:41
up vote 10 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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