Reducir a la mitad, Un Extraño en el Tamaño de los Anillos

Question

Considere la posibilidad de los anillos $\mathbb{Z} /n \mathbb{Z}$ donde $n$ es impar. Cada número está aún en estos anillos. Suponemos que comienzan con $1$ y mantener "reducir a la mitad" hasta llegar de nuevo a $1$. ¿Qué se puede decir sobre el número de veces que podemos reducir a la mitad respecto al $n$? Algunos ejemplos:

$\mathop\bmod 7$: $1 = 4+4$, $4 = 2+2$, $2 = 1+1$

Podemos reducir a la mitad tres veces $\mathop\bmod 7$.

$\mathop\bmod 11$: $1 = 6+6$, $6 = 3+3$, $3 = 7+7$, $7 = 9+9$, $9 = 10+10$, $10 = 5+5$, $5 = 8+8$, $8 = 4+4$, $4 = 2+2$, $2 = 1+1$

Podemos reducir a la mitad la diez veces $\mathop\bmod 11$.

Por lo $n$ podemos reducir a la mitad una $n-1$ veces?

Answer 1

La pregunta es muy difícil. Damos una breve descripción de lo que se conoce.

Si $n$ no es un número primo, entonces no podemos "dividir por $2$" $n-1$ veces. En más de un lenguaje convencional, si $n$ no es primo, entonces el orden de $2$ modulo $n$ no es igual a $n-1$/

Si $n$ es primo, es posible que el orden de $2$$n-1$, es decir, para $2$ a ser un generador del grupo multiplicativo, para $2$ a ser una raíz primitiva de $n$.

Si el primer $n$ es de la forma$8k\pm 1$, $2$ no puede ser una raíz primitiva de $n$. Sin embargo, poco se sabe de los números primos de la forma $8k\pm 3$. Aun no se sabe si existen infinitos números primos que han $2$ como una raíz primitiva, a pesar de que hay una abrumadora evidencia numérica que hay.

Tenga en cuenta que su cálculo demostró que $2$ no es una raíz primitiva de $7$ (esto también puede ser mostrado sin cálculo, ya que $7$ es de la forma $8k-1$). También mostró que el $2$ es una raíz primitiva de $11$.

Más en general, incluso para el prime $n$, no es mucho lo que puede decirse acerca de la orden de $2$ modulo $n$, es decir, el número de divisiones hasta llegar a $1$. Es fácil que el hecho de que el orden debe dividir $n-1$. Para los no primos $n$, podemos decir que el orden de las $2$ divide $\varphi(n)$ donde $\varphi$ es el de Euler $\varphi$-función. Esto puede ser reemplazado por el Carmichael función de $\lambda$.

El problema se puede expresar de forma equivalente, como una pregunta acerca de la longitud del ciclo de los binarios de expansión de $\frac{1}{n}$ donde $n$ es impar.