Supongo que está preguntando sobre el teorema de Lucas sobre la reducción de mod p de coeficientes binomiales. También supongo que sabes sobre el triángulo de Pascal y la identidad de Pascal, pero solo como recordatorio: 
(Fuente: Página en www.walser-hm.ch)
La identidad de Pascal dice que azul + rojo = verde. Por cierto, prefiero este tipo de representación, en lugar de la típica representación piramidal, porque visualiza más fácilmente la identidad de Pascal.
Esto es casi todo lo que necesitamos saber para comprender el teorema de Lucas. En primer lugar, comencemos tratando de entender el teorema en el caso de p = 3: 
Entonces, lo primero que vemos es que tenemos líneas de la forma 100 … 001 (las amarillas). Probémoslo. Esas líneas son exactamente las líneas [matemáticas] p ^ {\ alpha} [/ matemáticas]. De hecho, tome la identidad [matemáticas] k \ binom {n} {k} = n \ binom {n-1} {k-1} [/ matemáticas] (Esta identidad se traduce en el hecho de que si no desea elegir un equipo de k personas entre n personas con un líder, puede elegir el equipo ([matemáticas] \ binom {n} {k} [/ matemáticas] opciones posibles) y luego el líder entre el equipo ([matemáticas] k = \ binom {k} {1} [/ math] posibles opciones) o primero puede elegir el líder ([math] n = \ binom {n} {1} [/ math] posibles opciones) y luego elegir k-1 miembros de equipo ([matemáticas] \ binom {n-1} {k-1} [/ matemáticas] posibles opciones).
Ahora tome [math] n = p ^ {\ alpha} [/ math] y k diferentes de 0 y n y aplique esta identidad:
[matemáticas] k \ binom {p ^ {\ alpha}} {k} = p ^ {\ alpha} \ binom {p ^ {\ alpha-1}} {k-1} [/ matemáticas]
Pero sabes que [matemáticas] k <p ^ {\ alpha} [/ matemáticas]. Por lo tanto, [math] p ^ {\ alpha} [/ math] no divide [math] k [/ math], sino que divide el lado derecho de la igualdad y, por lo tanto, también divide el lado izquierdo. De esto podemos concluir que al menos [math] p [/ math] divide [math] \ binom {p ^ \ alpha} {k} [/ math]. Entonces tenemos :
[matemática] \ binom {p ^ \ alpha} {k} \ equiv 0 \ pmod {p} [/ matemática] para k diferente de 0 y n.
Este hecho ya da una buena pista de que deberíamos estar buscando la expansión en la base p. Regresemos a p = 3 y descubramos una forma rápida de calcular la reducción de mod p de un coeficiente binomial. Tome n = 13 y k = 10 por ejemplo. [matemáticas] n = p ^ 2 + p + 1 [/ matemáticas] y [matemáticas] k = p ^ 2 + 1 [/ matemáticas]. El coeficiente que estamos buscando está en el tercer triángulo marrón, pero si se mira de cerca, el tercer triángulo marrón es el mismo que el primero. Por lo tanto, tenemos [matemáticas] \ binom {p ^ 2 + p + 1} {p ^ 2 + 1} \ equiv \ binom {p + 1} {1} \ pmod {p} [/ matemáticas]. Ahora estamos buscando el segundo triángulo azul, pero el segundo triángulo azul es el mismo que el primer triángulo azul. Entonces tenemos:
[matemáticas] \ binom {p + 1} {1} \ equiv \ binom {1} {1} \ equiv 1 \ pmod {p} [/ matemáticas]
Por lo tanto, [math] \ binom {13} {10} \ equiv 1 \ pmod {p} [/ math].
- ¿Qué método matemático se usa en una herramienta de ajuste de curvas en MATLAB?
- ¿Por qué muchos matemáticos también conocen psicología?
- ¿Los axiomas de la lógica dictan las leyes de las matemáticas, o es todo lo contrario?
- ¿Quién inventó la regla BODMAS en matemáticas?
- ¿Cómo se puede aumentar la capacidad del canal utilizando la definición de información? ¿Cómo puedo identificarlo y mostrarlo matemáticamente?
Pero tomemos un ejemplo que es un poco más complicado. [matemáticas] n = 2p ^ 2 + 2p + 2 [/ matemáticas] y [matemáticas] k = p ^ 2 + 2p + 1 [/ matemáticas]
Ahora estamos en el quinto triángulo marrón, pero observe que la caja naranja de este triángulo es igual a 2 y no 1, pero los triángulos vecinos todavía tienen unos en sus cajas … 1 2 1 … hmmm? parece bastante familiar, ¿no? ¡Sí, exactamente un nuevo triángulo de Pascal con las cajas! ¡Mira aún más de cerca! No son solo las cajas: ¡todo el quinto triángulo es solo la suma del segundo y tercer triángulo (identidad de Pascal)! Si quieres sorprenderte aún más, mira los triángulos azules: lo mismo ocurre con ellos. Esta hermosa propiedad es en realidad la idea detrás del teorema de Lucas. De una manera muy interesante, el patrón del triángulo de Pascal aparece en cada escala. Así que volvamos al caso donde [matemática] n = 2p ^ 2 + 2p + 2 [/ matemática] y [matemática] k = p ^ 2 + 2p + 1 [/ matemática]. Como hemos dicho, es el quinto triángulo. Pero también sabemos que el quinto triángulo tiene una caja naranja con dos. La razón es simplemente que [matemáticas] \ binom {2} {1} \ equiv 2 \ pmod {3} [/ matemáticas]. (Observe que 2 y 1 son el coeficiente antes del término [matemática] p ^ 2 [/ matemática] en la expansión base p) Entonces sabemos que el quinto triángulo es solo el primer triángulo multiplicado por [matemática] \ binom {2} {1} [/ matemáticas]. Si continúa recursivamente, obtendrá:
[matemáticas] \ binom {2p ^ 2 + 2p + 2} {p ^ 2 + 2p + 1} \ equiv \ binom {2} {1} \ binom {2} {2} \ binom {2} {1} \ equiv 1 \ pmod {3} [/ math].
Puede generalizar el razonamiento anterior a cualquier p prime para obtener el siguiente resultado:
Si [matemáticas] n = \ sum_ {i} ^ {l} a_ {i} p ^ i [/ matemáticas] y [matemáticas] k = \ sum_ {i} ^ {l} b_ {i} p ^ i [/ matemáticas] entonces:
[matemáticas] \ binom {n} {k} \ equiv \ prod_ {i = 0} ^ {l} \ binom {a_ {i}} {b_ {i}} \ pmod {p} [/ matemáticas]
Observe también que, por ejemplo, [math] \ binom {1} {2} = 0 [/ math] por convención, por lo que este resultado está bien definido y esto también explica por qué justo encima de un triángulo marrón tiene muchos ceros.
Sin embargo, debo admitir que es muy difícil escribir rigurosamente la prueba anterior para una p general, por lo tanto, daré una prueba alternativa que es muy concisa, pero donde extrañas la belleza de este resultado y que también es más técnica.
(Observación sobre mi notación: cada vez que tengo k como índice en una suma, supongo que [math] k = \ sum_ {i} ^ {l} b_ {i} p ^ i [/ math]. Rigurosamente debería escribir : [matemáticas] k = \ sum_ {i} ^ {l} b_ {i} (k) p ^ i [/ matemáticas] ([matemáticas] b_i [/ matemáticas] en función de k), pero no lo haré hazlo para mantener las cosas más claras)
[matemáticas] \ sum_ {k = 0} ^ {n} \ binom {n} {k} X ^ k = (1 + X) ^ n [/ matemáticas]
[matemáticas] (1 + X) ^ {n} = \ prod_ {i = 0} ^ {l} ((1 + X) ^ {p ^ i}) ^ {a_i} [/ matemáticas].
Pero [matemáticas] (1 + X) ^ {p ^ {i}} = \ sum_ {j = 0} ^ {p ^ {i}} \ binom {p ^ {i}} {j} X ^ j [/ matemáticas]
Ahora recuerde que [matemáticas] \ binom {p ^ {i}} {j} \ equiv 0 \ pmod {p} [/ matemáticas] para j diferente de 0 y p ^ i. Por lo tanto:
[matemáticas] (1 + X) ^ {p ^ {i}} \ equiv 1 + X ^ {p ^ {i}} \ pmod {p} [/ matemáticas]
[matemáticas] \ sum_ {k = 0} ^ {n} \ binom {n} {k} X ^ k \ equiv \ prod_ {i = 0} ^ {l} (1 + X ^ {p ^ i}) ^ {a_i} [/ math]
[matemáticas] \ prod_ {i = 0} ^ {l} (1 + X ^ {p ^ i}) ^ {a_i} = \ prod_ {i = 0} ^ {l} \ sum_ {b_i = 0} ^ { a_i} \ binom {a_i} {b_i} X ^ {b_i p ^ i} [/ math]
Aquí viene una parte difícil, usamos nuevamente la convención de que si [matemática] a <b [/ matemática], tenemos [matemática] \ binom {a} {b} = 0 [/ matemática], entonces podemos agregar un par de cero términos.
[matemáticas] \ prod_ {i = 0} ^ {l} \ sum_ {b_i = 0} ^ {a_i} \ binom {a_i} {b_i} X ^ {b_i p ^ i} = \ prod_ {i = 0} ^ {l} \ sum_ {b_i = 0} ^ {p-1} \ binom {a_i} {b_i} X ^ {b_i p ^ i} [/ math]
Y aquí viene la parte más difícil. Si desarrolla la última expresión obtendrá algo de esta forma:
[matemáticas] \ prod_ {i = 0} ^ {l} \ sum_ {b_i = 0} ^ {p-1} \ binom {a_i} {b_i} X ^ {b_i p ^ i} = \ sum_ {k = 0 } ^ {n} \ alpha_ {k} X ^ k [/ matemáticas]
Ahora estamos tratando de encontrar [matemáticas] \ alpha_ {k} [/ matemáticas]:
[matemática] k = \ sum_ {i} ^ {l} b_ {i} p ^ i [/ matemática], entonces por la unicidad de la expansión en la base p, si desea formar [matemática] X ^ k [/ matemática] eligiendo un factor en cada [matemática] \ {X ^ 0, X ^ 1,…, X ^ {p-1} \} [/ matemática], [matemática] \ {X ^ 0, X ^ p, …, X ^ {(p-1) p} \} [/ matemáticas]… [matemáticas] \ {X ^ 0, X ^ {p ^ l}… X ^ {(p-1) p ^ {l}} \} [/ math], debes tomar los coeficientes de la expansión en la base p. Por lo tanto:
[matemáticas] \ alpha_ {k} = \ prod_ {i = 0} ^ {l} \ binom {a_i} {b_i} [/ matemáticas]
y
[matemáticas] \ prod_ {i = 0} ^ {l} \ sum_ {b_i = 0} ^ {p-1} \ binom {a_i} {b_i} X ^ {b_i p ^ i} = \ sum_ {k = 0 } ^ {n} (\ prod_ {i = 0} ^ {l} \ binom {a_i} {b_i}) X ^ k [/ math]
Finalmente, juntando todas esas cosas:
[matemáticas] \ sum_ {k = 0} ^ {n} \ binom {n} {k} X ^ k \ equiv \ sum_ {k = 0} ^ {n} (\ prod_ {i = 0} ^ {l} \ binom {a_i} {b_i}) X ^ k \ pmod {p} [/ math]
Mediante la identificación de los coeficientes, obtenemos:
[matemáticas] \ binom {n} {k} \ equiv \ prod_ {i = 0} ^ {l} \ binom {a_i} {b_i} \ pmod {p} [/ matemáticas]
QED
