Demostrar que si $2^n-1$ es primo, entonces $n$ divide $2^n-2$

Question

Supongamos que $p = 2^n - 1$ es primo. Demuestre que $n \: | \: 2^n - 2$ o, por el contrario $n \: | \: p - 1$ .
Con pista: El orden de cualquier elemento en este campo divide $p-1$ .

Ejemplo: $n=7, \; p=127 \:\Rightarrow\: 7 \: | \: 126$ .

---

No tengo ningún progreso que parezca conducir a una prueba, pero aquí están algunas de mis ideas:

• Porque $p$ es un primo de Mersenne, $n$ debe ser primordial
• Utilice el pequeño teorema de Fermat
• Demostrar que $2^n - 2 \equiv 0 \mod n$

Answer 1

Ha mencionado ingredientes que conducen a una prueba. Como usted señala, el número $n$ debe ser primo, por lo que podemos utilizar el Teorema de Fermat.

Hay un par de versiones diferentes del Teorema de Fermat. Cada versión no es difícil de derivar de la otra.

Versión 1: Si $n$ es primo, entonces para cualquier número entero $a$ tenemos $a^n \equiv a \pmod n$ . Esto dice directamente que $n$ divide $a^n-a$ que es exactamente lo que se quiere mostrar, en el caso especial $a=2$ .

Versión 2: Si $n$ es primo, y $n$ no divide $a$ entonces $a^{n-1} \equiv 1 \pmod n$ .

En su caso, $n$ es impar, por lo que si $a=2$ entonces $n$ no divide $a$ . De ello se desprende que $n$ divide $2^{n-1}-1$ y por lo tanto $n$ divide el doble de este número, que es $2^n-2$ .

Sin embargo, se le dio una pista que nos permite eludir el Teorema de Fermat. Así que probablemente se esperaba que argumentaras lo siguiente.

Desde $p=2^n-1$ Ciertamente $p$ divide $2^n-1$ Así que $2^n \equiv 1 \pmod p$ . Esto implica que el orden de $2$ en el campo $\mathbb{Z}_p$ es un divisor de $n$ . Pero el orden de $2$ es exactamente $n$ ya que $n$ es primo, y por tanto los únicos divisores de $n$ son $1$ y $n$ .

El orden de cualquier elemento del campo $\mathbb{Z}_p$ divide $p-1$ . Dado que el orden de $2$ en este campo es $n$ concluimos que $n$ divide $p-1$ Es decir, $n$ divide $2^n-2$ .

Answer 2

Una respuesta más sencilla:

Dejemos que $n \in \mathbb{N}^+$ sea arbitraria. Sea $p = 2^n-1$ .

Claramente, $2^n \equiv 1 \mod {2^n-1}$ . Mudanza, $n$ es la menor potencia donde $2^n \equiv 1$ . Por lo tanto, el orden de 2 en $\mathbb{Z}_{p}$ es $n$ .

Ahora bien, si $p$ es primo, entonces el pequeño teorema de Fermat garantiza que para cualquier $a$ (excepto 0), $a^{p-1} \equiv 1 \mod p$ . Además, el orden de $a$ divide $p-1$ .

$a=2$ tiene orden $n$ Por lo tanto $n$ divide $p-1 = 2^n - 2$ como se quiera.

---

Respuesta complicada:

Es un hecho: $x^{ab} - 1 = (x^a - 1)(x^{(b-1)a} + \ldots + x^{3a} + x^{2a} + x^a + 1)$ . Así, para el caso especial de $2^n-1$ , si $n$ es compuesto entonces $2^n-1$ puede ser factorizado. Por contraposición, si $2^n-1$ es primo entonces $n$ es primo.

El pequeño teorema de Fermat: Si $q$ es primo, entonces $\forall a \in \mathbb{Z}, \; a^q \equiv a \mod q$ .

Ahora, $n \: | \: 2^n - 2$ equivale a decir que $2^n-2$ es un múltiplo de $n$ o $2^n-2 \equiv 0 \mod n$ .

Hemos establecido que $n$ debe ser primo. Aplicando la FLT con $a=2$ obtenemos $2^n \equiv 2 \mod n$ que es fácilmente equivalente a $2^n - 2 \equiv 0 \mod n$ .

Answer 3

Sugerencia $\rm\: prime\: P,\: A^P\!\! = 1 = A^K\!\Rightarrow A^{(P,\:K)}\!\!=1,$ así que $\rm\: P| K\ $ [si $\rm (P,K) = P$ ] $\:$ o $\rm\: A\! =\! 1\:$ [si $\rm (P,K) = 1$ ]

Para más detalles, consulte esta pregunta: Si el orden divide a un primo P entonces el orden es P (o 1).