Prueba de que $2^p-2$ es divisible por $p$ ?

Question

Me gustaría demostrar que $2^p-2$ es divisible por $p$ cuando $p$ es primo. Esto es cierto para miles de primos $p$ que he probado, pero no puedo averiguar o encontrar una prueba.

Answer 1

Una prueba mínima, $$2^p -2 = \sum_{k=1}^{p-1} \binom{p}{k}$$ y observe que cada término $$\binom{p}{k} = \frac{p!}{(p-k)! k!}$$ es divisible por $p$ . En este caso, el hecho de que $p$ es primo es esencial: ya que $p$ es primo, será relativamente primo de cualquier $l$ , $1\le l \le p-1$ y por lo tanto relativamente primo con $(p-k)! k!$ . Ahora, $p$ divide el producto ( $p!)$ de los enteros $(p-k)! k!$ y $\frac{p!}{(p-k)! k!}$ mientras que es relativamente primo de $(p-k)! k!$ por lo que se divide $\frac{p!}{(p-k)! k!}= \binom{p}{k}$ por cada $1\le k \le p-1$ .

$\bf{Added:}$ Hay otras pruebas en el enlace proporcionado que utilizan la acción del grupo $\mathbb{Z}/p$ en un conjunto de collares, un argumento de "contar órbitas". Así que demostremos de forma similar que $\binom{p}{k}$ es divisible por $p$ . Pregunta: ¿cómo agrupar los subconjuntos con $k$ elementos de ${0,1,\ldots, p-1}$ en grupos de $p$ ? Poner en el mismo grupo un subconjunto $\{a_1, \ldots, a_k\}$ y todos sus desplazamientos en módulo $p$ por algunos $s$ , donde $1\le s \le p-1$ . Obsérvese que, efectivamente, obtenemos $p$ diferentes subconjuntos: porque si $$\{a_1+s, \ldots, a_k+s\} = \{a_1+t, \ldots, a_k+t\}$$ entonces tomando la suma de ambos lados obtenemos $$(\sum_{i=1}^k a_i)+ k s = (\sum_{i=1}^k a_i) + kt \mod p$$ y, como $p$ es primo y $1\le k \le p-1$ Debemos tener $s = t \mod p$ .

Answer 2

Informo aquí de una de las pruebas Wikipedia da de El pequeño teorema de Fermat que es equivalente a su declaración. Me parece que esta es la más accesible. Eres libre de ir a leer y/o copiar otras pruebas como respuestas.

En primer lugar, tenemos que saber que:

$$(x+y)^p=\sum_{i=1}^p\binom{p}{i}x^iy^{p-i}.$$

Esto se puede demostrar por inducción para números enteros arbitrarios $k$ como exponentes, no sólo primos $p$ .

Utilizando esto, y reduciendo el módulo $p$ la ecuación anterior, vemos que los únicos términos de la derecha que quedan son $x^p+y^p$ ya que todos los demás coeficientes son divisibles por $p$ y, por lo tanto, cero módulo $p$ . Es decir:

$$(x+y)^p\equiv x^p+y^p\pmod p.$$

Pasemos ahora a nuestra reclamación:

$$a^p\equiv a\pmod p,$$

para cualquier número entero $a$ y primo $p$ . Lo demostramos por inducción. El caso base $a=1$ es trivial. Supongamos que se cumple para $k$ . Entonces:

$$(k+1)^p\equiv k^p+1^p\equiv k+1\pmod p,$$

donde el primer pasaje es lo que hemos demostrado con la expansión binomial al principio de esta prueba, y el segundo pasaje es el caso base + la hipótesis de inducción. Así que hemos demostrado la $k+1$ caso asumiendo el $k$ caso y el $1$ caso. Por lo tanto, esto es válido para cualquier número entero $a$ incluyendo, en particular, $2$ .

Answer 3

Esto se deduce fácilmente del pequeño teorema de Fermat, como señaló Clement C. en un comentario.

Si $p$ es primo y $\gcd(a, p) = 1$ entonces $a^{p - 1} \equiv 1 \pmod p$ . Desde $a^p = a^{p - 1} a$ entonces $a^p \equiv 1a \pmod p$ (Escribo " $1a$ " en lugar de sólo " $a$ "para mayor claridad). Si $a = 2$ entonces tenemos $2^p \equiv 2 \pmod p$ y $2^p - 2 \equiv 0 \pmod p$ que es otra forma de decir lo que ya has observado.