20

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

ShreevatsaR
  • 41,374
  • http://math.stackexchange.com/questions/256853/quadratic-reciprocity-and-proving-a-number-is-a-primitive-root – lab bhattacharjee May 07 '13 at 04:51
  • http://math.stackexchange.com/questions/117269/prime-of-the-form-4p1 – lab bhattacharjee May 07 '13 at 05:30
  • 3
    @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 07 '13 at 05: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 (http://mathworld.wolfram.com/FermatPrime.html) – lab bhattacharjee May 07 '13 at 07:41

1 Answers1

16

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

mercio
  • 50,180
David E Speyer
  • 61,724
  • 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
  • Sorry to resurrect this post, but can we calculate the size $s$ of the Galois group of $f(x)=\phi_M(x)(x^M-2)$?

    (By Chebotarev's density theorem, the density of primes where $M \mid r_p(2)$ would then be $1/s$.)

     – Quang Dao Jul 30 '22 at 10:09
  • It's going to be a little annoying. The splitting field is the compositum of $\mathbb{Q}(\zeta_M)$ and $\mathbb{Q}(\sqrt[M]{2})$, so an upper bound is $\phi(M) M$. But these two fields aren't always disjoint. For example, $\mathbb{Q}(\zeta_8) \cap \mathbb{Q}(\sqrt[8]{2}) = \mathbb{Q}(\sqrt[2]{2})$, so, when $M=8$, we get $\tfrac{8 \phi(8)}{2}$, not $8 \phi(8)$. @QuangDao – David E Speyer Jul 30 '22 at 19:38