El teorema de Lucas
Para Luis, para que no
olvide nunca que detrás
de la tormenta siempre
viene la calma.
A veces, cuando manejamos números muy grandes, o muy difíciles de obtener, podemos investigar sus propiedades sin necesidad de hallar explícitamente dichos números, lo cual es una gran ventaja. El teorema de Lucas es uno de esos atajos.
Se refiere a los coeficientes binomiales ; esos que aparecen en el triángulo de Pascal, también llamado de Tartaglia. Dado que dichos números se obtienen mediante factoriales, en número de operaciones involucradas crece enormemente cuando los números se van haciendo mayores.
En su versión general, el Teorema de Lucas nos da un algoritmo muy sencillo para encontrar el resto de dividir cualquier coeficiente binomial por un primo p . La versión que veremos del enunciado nos permitirá saber si un coeficiente binomial es par o impar, que es el caso concreto para p=2.
Si construimos un triángulo de Tartaglia módulo 2, que es exactamente dividir cada número del triángulo original por dos, y anotar únicamente el resto (que sólo podrá ser 0 ó 1), obtenemos lo indicado en la figura siguiente:
Cada cero indica que el correspondiente número del triángulo inicial era par, y cada uno indica lo contrario. Es patente que existe una estructura anidada: tenemos una plantilla principal D1 que tiene 21=2 filas y tres elementos, todo unos, en la figura en rojo. Tres de dichas plantillas forman un arreglo triangular D2 de 22=4 filas. Entre las tres, queda un hueco que de momento es el único cero.
Tres plantillas D2 forman la plantilla del siguiente orden, D3, de 23=8 filas. Ahora queda un hueco en forma de triángulo invertido en el que caben seis ceros. El proceso sigue indefinidamente, en la figura siguiente podemos ver las sucesivas plantillas generadas como se ha explicado:
Cada fila del triángulo se expresa mediante el parámetro n , que empieza con el valor cero. Dentro de una fila concreta (esto es: para un n concreto) el parámetro k va recorriendo los valores que expresan el puesto del número en la fila, desde 0 para el primer puesto hasta n para el último y (n+1)-ésimo.
EL teorema de Lucas nos dice que basta comparar los desarrollos en base dos de n y de k para saber si el coeficiente binomial es par o impar: todos los dígitos del desarrollo de k deben ser menores o iguales que los correspondientes de n para que el número sea impar, en caso contrario es par. Como estamos trabajando ahora con ceros y unos, esto es lo mismo que decir que donde haya un cero en el desarrollo de n, no puede haber un uno en el desarrollo de k.
vemos un ejemplo. Investiguemos si el quinto elemento de la fila siete (redordemos que la primera fila, la de la cúspide del triángulo es la fila cero) es par o impar:
n=7 desarrollo binario: 0 1 1 1
k=4 desarrollo binario: 0 1 0 0
como no hay ningún dígito mayor en k que el correspondiente de n, el número es impar ( de hecho es 35).
Para las filas de forma 2m-1, por ejemplo las filas 7, 15, 31, todos los coeficientes son impares: efectivamente, el desarrollo binario de dichos números es todo unos, luego k no tiene la menor posibilidad de tener un dígito más grande que el correspondiente de n.
La potencia del teorma de Lucas es mayor de lo explicado aquí, pues no se resume en módulo 2, pero baste esta pincelada para entrever el aroma del teorema completo( que por cierto no es sino un caso parcial de un resultado más general conocido con el nombre de Teorema de Kummer).
15 comentarios
Generic Cialis -
dragblanco -
kaiserr -
YESENIA -
Daniel -
Daniel -
luis -
Sabemos que 0 es un numero entero => k=0 y n=0 0=2*0, .'. 0 es numero par
Anónimo -
Charles Toribio Vereau -
Gracias
Crystal -
Me aplicaré más para la próxima...
Rimblow -
Tio Petros -
1, 7, 21, 35, 35, 21, 7, 1.
Ahora, y si no metes la pata como la he metido yo, verás que el quinto es 35, y no 21.
Aparte de este desliz, lo interesante es que en esta fila todos son impares. Como el desarrollo binario de 7 (111) sólo tiene unos, ningún valor de k menor de siete puede tener un bit mayor que el 1 correspondiente, luego según el Teorema de Lucas, todos los miembros de la fila son impares. Como comentaba, eso sólo pasa con las filas que son de la forma "una unidad menos que una potencia de dos", por ejemplo la fila 7 (2 al cubo menos uno), la 15 (2 a la cuarta menos uno), la 31 (2 a la quinta menos uno), que en sus respectivas expansiones decimales valen:
7 --->111
15--->1111
31--->11111; todo unos.
Rimblow -
Tio Petros -
Crystal -