Blogia
Tio Petros

El teorema de Lucas

- Teoremas

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 -

hola, nunca llegue a entender el teorema de Lucas, para ya es una matematica muy avanzada.

dragblanco -

hola; quisiera saber is me pueden prporcinar informacion sobre los numeros de lucas...... muchas gracias de antemano.. ah y la demostracion de la suma de cuadrados de los numeros de lucas.... y q relacion hay entre lucas y fibonacci. gracias.

kaiserr -

como podia saber cuantos 1's tiene cierto numero... por asi decirlo cuantos 1's tiene 25?? hay alguna formula???

YESENIA -

el cero entonces llegaria hace un numero natural ¿ si o no? y porfis un poquitin mas explicadito de si es par o impar entendi poco zorry

Daniel -

sorry, los pares serian 2,4,6...etc

Daniel -

pero el -2 tb es un numero entero, o sea que el -4=2*-2 tb es par?? ese k no sera numeros naturales? en ese caso serian 1,2,3 por lo tanto los pares serian 2,3,4...etc

luis -

Un numero n es par si y solo si existe un numero entero k tal que n=2k
Sabemos que 0 es un numero entero => k=0 y n=0 0=2*0, .'. 0 es numero par

Anónimo -

Charles Toribio Vereau -

más que comentario es una pregunta si me pueden ayudar el número 0 es par o impar
Gracias

Crystal -

Ya sé por qué no lo entendía: soy negada para los números binarios ;P
Me aplicaré más para la próxima...

Rimblow -

Mucha gracias, ahora ya lo he entendido.

Tio Petros -

Hola Rimblow. ¿Te refieres a mi ejemplo del quinto elemento de la fila siete? No tienes más que hacer el triángulo de Tartaglia, y comprobar que la fila siete tiene las cifras:
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 -

Yo la verdad es que tampoco me he enterado muy bien, lo de impar lo entiendo, pero porque es 21 y no 31. Un saludo...

Tio Petros -

Jajajaja, ánimo, Crystal...

Crystal -

Lo siento pero esta vez no he pillado ni media, voy a ver si una segunda lectura me despierta la neurona...