Puede el orden de los 2 mod p ser arbitrariamente pequeño (en relación al $p - 1$)?

Question

Dado un número primo $p$, vamos a $\operatorname{ord}_p(2)$ ser el multiplicativo orden de $2$ modulo $p$, es decir, el entero más pequeño $k$ tal que $p$ divide $2^k - 1$. Por Lagrange del teorema, $\operatorname{ord}_p(2)$ divide $(p - 1)$, así que vamos a $r = r_p(2) = \dfrac{p-1}{\operatorname{ord}_p(2)}$. Pregunta: ¿$r$ ser arbitrariamente grande? Es decir, dado cualquier $M$, no siempre existen algunos $p$ tal que $r_p(2) > M$?

(Tenga en cuenta que cuando se $2$ es una raíz primitiva módulo $p$,$r_p(2) = 1$, así que lo que estamos pidiendo es la de los números primos para que $2$ es arbitrariamente "lejos" de ser una raíz primitiva.)

Una manera en que esto sería cierto es que si existen infinitos números primos de Mersenne. Si $p$ es una de Mersenne prime, decir $p = 2^q - 1$ algunos $q$, $p$ divide (es igual a) $2^q - 1$, y pequeñas potencias de $2$ son de menos de $p$, lo $\operatorname{ord}_p(2) = q$, e $r_p(2) = \dfrac{p-1}{q} = \dfrac{2^q - 1}{q}$ que puede ser arbitrariamente grande, si hay infinitamente muchos de esos $q$.

Pero, por supuesto, tal vez la respuesta es sí, sin asumir la existencia de infinitos números primos de Mersenne. Es? Es algo que se conoce acerca de este problema? (Es $2$ especial a todos?)

[Fuente: Esta pregunta se planteó en Brian Hayes del blog.]

Answer 1

Sí. Necesitamos la siguiente consecuencia de Chebotarev densidad del teorema: Vamos a $f \in \mathbb{Z}[x]$ ser un polinomio. Existen infinitos números primos $p$ que $f$ factores como producto de términos lineales.

Deje $\phi_M(x)$ $M$- th cyclotomic polinomio. Tome $f(x) = \phi_M(x)(x^M-2)$. Deje $p$ ser una de las primeras, de modo que $f(x)$ se divide en factores lineales modulo $p$. Desde $\phi_M(x)$ tiene una raíz mod $p$, no es un primitivo $M$-ésima raíz de la unidad en la $\mathbb{F}_p$$M|p-1$. Desde $x^M-2$ tiene una raíz modulo $p$, podemos ver que $2=a^M \bmod p$ algunos $a$. A continuación,$2^{(p-1)/M} \equiv a^{p-1} \equiv 1 \bmod p$$M|r_p(2)$.