Si [math] p [/ math] es un número primo y [math] x [/ math] y [math] y [/ math] son ​​dos enteros, ¿cómo podemos demostrar que [math] (x + y) ^ p \ equiv x ^ p + y ^ p \ pmod p [/ math]?

Answer 1

El teorema binomial nos permite expandir [matemáticas] (x + y) ^ p [/ matemáticas] como

[matemáticas] \ displaystyle (x + y) ^ p = \ sum_ {k = 0} ^ p \ binom {p} {k} x ^ ky ^ {pk} [/ math]

El primer y el último coeficiente binomial, [matemática] \ binom {p} {0} [/ matemática] y [matemática] \ binom {p} {p} [/ matemática], son ambos [matemática] 1 [/ matemática]. La clave es que los otros coeficientes, [matemática] \ binom {p} {k} [/ matemática] cuando [matemática] 1 <k <p [/ matemática], son divisibles por [matemática] p [/ matemática]. Este es el por qué:

[matemáticas] \ displaystyle \ binom {p} {k} = \ frac {p!} {k! (pk)!} [/ matemáticas]

El numerador, [math] p! [/ Math], es claramente divisible por [math] p [/ math]. Pero el denominador no es divisible entre [matemática] p [/ matemática] cuando [matemática] 1 <k <p [/ matemática], ya que [matemática] k! [/ Matemática] es el producto de números todos menores que [matemática] p [/ math] y [math] (pk)! [/ math] también es el producto de números todos más pequeños que [math] p [/ math]. Como [math] p [/ math] es primo, no se puede formar como producto de números más pequeños.

Entonces tenemos un numerador divisible por [math] p [/ math] y un denominador no divisible por [math] p [/ math], lo que significa que todo (que sabemos que es un número entero) todavía es divisible por [math] p [/matemáticas].

Entonces, módulo [math] p [/ math], todos los términos en la expansión binomial desaparecen excepto el primero [math] y ^ p [/ math] y el último [math] x ^ p [/ math], entonces

[matemática] \ displaystyle (x + y) ^ p \ equiv x ^ p + y ^ p \ pmod p [/ math]. QED

---

Es importante recordar que esto ya no es cierto si el poder [matemática] p [/ matemática] no es primo. Por ejemplo, el coeficiente binomial [matemática] \ binom {4} {2} = 6 [/ matemática] que no es divisible por [matemática] 4 [/ matemática], y como resultado [matemática] (x + y) ^ 4 [/ math] no es lo mismo que [math] x ^ 4 + y ^ 4 [/ math] módulo [math] 4 [/ math]. Pruebe esto con [matemáticas] x = y = 1 [/ matemáticas].

Este teorema a veces se llama “El sueño del estudiante de primer año”, como una referencia en broma al hecho de que muchos jóvenes estudiantes habrían amado que [matemática] (a + b) ^ n = a ^ n + b ^ n [/ matemática] cierto, haciendo sus vidas más fáciles. Es cierto, pero solo como congruencia, no como igualdad, y solo cuando [math] n [/ math] es primo.

Bromas aparte, esta feliz coincidencia significa que “elevar al poder [matemático] p ^ \ text {th} [/ matemático]” preserva tanto el módulo de suma como el de multiplicación [matemático] p [/ matemático]. Esta transformación tiene un nombre, el endomorfismo de Frobenius, y es una operación increíblemente importante en teoría de números y geometría aritmética, siendo uno de los “regalos” centrales del álgebra sobre campos finitos. Hace que muchos resultados que aún nos eluden sean posibles de probar sobre campos finitos u otros campos de características principales.

Answer 2

Por el pequeño teorema de Fermat,

[matemáticas] a ^ p \ equiv a \ pmod {p} [/ matemáticas]

Al aplicar esto a [matemáticas] a = x + y [/ matemáticas],

[matemáticas] (x + y) ^ p \ equiv x + y \ pmod {p} [/ matemáticas]

Al aplicar esto a [matemáticas] x [/ matemáticas] y [matemáticas] y [/ matemáticas],

[matemáticas] x ^ p \ equiv x \ pmod {p} [/ matemáticas]

[matemáticas] y ^ p \ equiv y \ pmod {p} [/ matemáticas]

Combinando estos, podemos ver que

[matemáticas] (x + y) ^ p \ equiv x + y \ equiv x ^ p + y ^ p \ pmod {p} [/ matemáticas]

Answer 3

todas las otras pruebas a través de la expansión binomial están bien, pero también puede hacerlo a través del pequeño teorema de Fermat, [math] a ^ {p-1} \ equiv 1 \ bmod p [/ math] (para todos [math] a \ no \ equiv 0 \ bmod p [/ math])

de donde [math] a ^ p \ equiv a \ bmod p [/ math] para todos los enteros [math] a [/ math]

en particular [matemáticas] (x + y) ^ p \ equiv x + y \ equiv x ^ p + y ^ p [/ matemáticas]

Por supuesto, eso solo lleva a la pregunta “¿Cómo demuestras el pequeño teorema de Fermat?”, Y por supuesto, la página de wikipedia enlaza con muchas pruebas diferentes, incluida una que es más o menos la prueba de expansión binomial dada en las otras respuestas aquí.

Pero el que siempre me gustó fue el que, dado cualquier número [matemático] a \ not \ equiv 0 \ bmod p [/ matemático], el [matemático] p-1 [/ matemático] números diferentes [matemático] a, 2a , 3a, \ ldots (p-1) a [/ math] son ​​todos distintos [math] \ bmod p [/ math] y, por lo tanto, deben contener un representante de cada uno de [math] p-1 [/ math] distinto de cero clases de congruencia, es decir, hay una correspondencia uno a uno entre esos números [matemáticos] p-1 [/ matemáticos] y los números [matemáticos] 1,2,3,4, \ ldots p-1 [/ matemáticos] para que cada número es congruente con el número al que corresponde. Pero esto significa

[matemáticas] a \ cdot 2a \ cdot 3a \ cdots (p-1) a \ equiv 1 \ cdot 2 \ cdot 3 \ cdots (p-1) \ bmod p [/ math]

es decir, [matemáticas] a ^ {p-1} \ cdot (p-1)! \ equiv (p-1)! \ bmod p [/ matemáticas]

y desde [matemáticas] (p-1)! [/ math] es relativamente primo para [math] p [/ math], podemos dividir ambos lados de la congruencia por él, produciendo el resultado deseado [math] a ^ {p-1} \ equiv 1 \ bmod p [/ matemáticas]

Answer 4

Considere la expansión de

[matemáticas] \ displaystyle {\ qquad (x + y) ^ p = \ sum_ {k = 0} ^ p \ begin {pmatrix} p \\ k \ end {pmatrix} x ^ {pk} y ^ k} [/ matemáticas],

dónde

[matemáticas] \ displaystyle {\ qquad \ begin {pmatrix} p \\ k \ end {pmatrix} = \ frac {p!} {k! (pk)!}} [/ math]

se llama coeficiente binomial (se pronuncia “[matemática] p [/ matemática] elija [matemática] k [/ matemática]”) y [matemática] \ displaystyle {x! = \ prod_ {i = 1} ^ xi} [/ matemática], para un número natural positivo [matemática] x [/ matemática] (y [matemática] 0! = 1 [/ matemática]), es el factorial de [matemática] x [/ matemática].

Cuando [math] k = 0 [/ math] o [math] k = p [/ math], el coeficiente binomial es solo [math] 1 [/ math].

¿Qué notas sobre todos los demás coeficientes binomiales?

Answer 5

Distribuya [math] (x + y + z + \ dots) ^ p [/ math] pero no asuma la conmutatividad o recopile términos de la manera habitual todavía. Cada término es una cadena que es una mezcla de [matemática] x [/ matemática] sy [matemática] y [/ matemática] sy [matemática] z [/ matemática] sy cualquier otra cosa, con una longitud total [matemática] p [/matemáticas].

Para cada una de estas cadenas, al girarla cíclicamente, obtienes otras cadenas; [math] 1 [/ math] o [math] p [/ math] en general, muchos distintos. (Esto se debe a que el período de la rotación tiene que ser un factor de [matemáticas] p [/ matemáticas], y dado que [matemáticas] p [/ matemáticas] es primo, sus únicos factores son [matemáticas] 1 [/ matemáticas] y [matemáticas] p [/ matemáticas]).

En el caso de que haya [math] p [/ math] muchas rotaciones distintas, estos [math] p [/ math] muchos términos tienen el mismo valor, por lo que al sumarlos, obtenemos un múltiplo de [math] p [/ math], que podemos ignorar en mod [math] p [/ math] land.

Lo que queda son las cadenas cuyas rotaciones tienen un período de 1: las cadenas constantes. Es decir, la cadena de todos [math] x [/ math] s, que es [math] x ^ p [/ math], y la cadena de todos [math] y [/ math] s, que es [math] y ^ p [/ math], y así sucesivamente para cada sumando. Obtenemos que [matemáticas] (x + y + z + \ puntos) ^ p = x ^ p + y ^ p + z ^ p + \ puntos [/ matemáticas].

Sin embargo, tenga en cuenta que este argumento muestra que esto es en realidad mucho más general que un hecho sobre la aritmética de enteros mod [math] p [/ math]. Tenemos un análogo de esta propiedad para cualquier función multilineal [matemática] p [/ matemática] [matemática] f (x_1, \ puntos, x_p) [/ matemática] donde la suma de [matemática] f [/ matemática] sobre Todos los cambios cíclicos de sus argumentos desaparecen. Entonces, por ejemplo, [math] \ mathrm {Trace} \ left (\ left (M_1 + \ dots + M_n \ right) ^ p \ right) = \ mathrm {Trace} \ left (M_1 ^ p + \ dots + M_n ^ p \ right) \ pmod {p} [/ math] para matrices, aunque la multiplicación de matrices no sea conmutativa y la traza de productos de matrices no sea simétrica (es solo “simétrica en ciclo”, por así decirlo) )

Answer 6

A2A, gracias.

Expandiendo [matemáticas] (x + y) ^ p [/ matemáticas] usando el teorema del binomio – Wikipedia, obtenemos una suma de la forma

[matemática] x ^ p + y ^ p + [[/ matemática] términos que son múltiplos de [matemática] p] [/ matemática].

Todo en [] ‘s, en el módulo de división [math] p [/ math], da cero.

Answer 7

(x + y) ^ p = suma (pCi * x ^ (pi) * y (i)) para i varía de cero a p

pC0 = 1, pCp = 1

por lo tanto: (x + y) ^ p = X ^ p + p * X ^ (p-1) * y + p (p-1) * X ^ (p-2) * y ^ 2 +… + y ^ p

como regla: w (modp) = 0 si w / p = número entero (sin resto)

por lo tanto, podemos decir que los términos completos que contienen el valor (p) no tienen resto cuando se dividen entre p y, por lo tanto, su módulo p = 0

Por lo tanto: (x + y) ^ p mod p = X ^ p + 0 + 0 + 0 +… + y ^ p

Answer 8

Dado que…

[math] p [/ math] es un número primo y [math] x ~ y ~ y [/ math] son ​​dos enteros.

Lo sabemos…

[matemáticas] (x + y) ^ p = \ sum_ {k = 0} ^ pC_k ^ px ^ ny ^ {pk} [/ matemáticas]

Esto se puede escribir como …

[matemáticas] (x + y) ^ p = x ^ p + \ sum_ {k = 1} ^ {p-1} C_k ^ px ^ py ^ {pk} + y ^ p [/ matemáticas]

[matemáticas] \ Rightarrow (x + y) ^ p = x ^ p + y ^ p + \ sum_ {k = 1} ^ {p-1} \ dfrac {p!} {k! (pk)!} x ^ ky ^ {pk} [/ matemáticas]

[matemática] \ Flecha derecha (x + y) ^ p \ equiv x ^ p + y ^ p [\ mod p] [/ matemática]

El problema ya está hecho.

Si me equivoco, por favor dímelo.