Los números primos, compuestos y factorización
En
la teoría de números uno de los conceptos importantes es tener bien claro la
divisibilidad.
El concepto de la divisibilidad debemos
tenerlo claro para poder saber si un número es divisible entre otro, ya que en muchas ocasiones nos facilita la factorización de un número natural. Decimos entonces
que un número natural es divisible entre otros si, al dividir el primero entre
el segundo, se obtiene un residuo de cero (0). El conocer ciertas reglas de
divisibilidad te ayudarán a comprender mejor los números primos, compuestos y la factorización.
Algunas reglas sencillas sobre divisibilidad
El que un
número sea divisible entre 2, 3, 4, 5, 8, 9, 10 u 11 es relativamente sencillo
de comprobar. Un número
entero cualquiera n:
• es divisible entre 2 si y
sólo si su última cifra es par,
• es divisible entre 3 si y
sólo si la suma de las cifras de n es múltiplo de 3,
• es divisible entre 4 si y
sólo si su última cifra es par pero no múltiplo de 4, y su penúltima cifra es
impar, o
si su última cifra es múltiplo de 4 y su penúltima cifra es par (o
equivalentemente, si el
número
formado por sus dos últimas cifras es divisible entre 4),
• es divisible entre 5 si y
sólo si su última cifra es 0 o 5,
* Para determinar si un número es divisible por 7,saca el último dígito del número, duplícalo y réstalo del número restante. Si este resultado es exactamente divisible por 7 (ej, 14, 7 , 0 , -7, etc.) entonces el número es divisible por 7. Puede ser que necesites repetir esto varias veces.
310 - saca el ultimo dígito del número que es el 1
-2 - dobla el dígito separado y réstalo
-------
308 - repite el proceso sacando el 8
-16 - y doblálo para obtener 16 y réstalo
------
14 - el resultado es 14 que es un múltiplo de 7
* Para determinar si un número es divisible por 7,saca el último dígito del número, duplícalo y réstalo del número restante. Si este resultado es exactamente divisible por 7 (ej, 14, 7 , 0 , -7, etc.) entonces el número es divisible por 7. Puede ser que necesites repetir esto varias veces.
310 - saca el ultimo dígito del número que es el 1
-2 - dobla el dígito separado y réstalo
-------
308 - repite el proceso sacando el 8
-16 - y doblálo para obtener 16 y réstalo
------
14 - el resultado es 14 que es un múltiplo de 7
• es divisible entre 8 si y
sólo si el número formado por sus tres últimas cifras es múltiplo de 8,
• es divisible entre 9 si y
sólo si la suma de las cifras de n es múltiplo de 9,
• es divisible entre 10 si y
sólo si su última cifra es 0,
• es divisible entre 11 si y
sólo si la suma de sus cifras en posición par, menos la suma de sus cifras
en
posición impar, es múltiplo de 11 (incluido el 0).
Ilustramos
el último caso con un ejemplo: el número 164151324116 no es múltiplo de 11,
porque
sumando
las cifras de posición impar (1+4+5+3+4+1=18), y las cifras de posición impar
(6+1+1+2+1+6=17),
la diferencia es 1, que no es múltiplo de 11. Sin embargo, el número
164151324161 sí sería múltiplo de 11 (1+4+5+3+4+6=23, 6+1+1+2+1+1=12,
y 23−12=11,
que sí es múltiplo de 11).
Factorización en primos
La
descomposición en factores primos de un entero n, también llamada
factorización en primos o
simplemente
factorización, consiste en expresar n como producto de números primos;
como ya hemos dicho,
esta forma de expresarlo es única salvo el orden de los factores primos. Para
números
relativamente
pequeños, esta factorización suele ser sencilla, por ejemplo 12=22×3, 56=23×7,
o 51=3×17. Para
números más grandes, como 123761232, la tarea empieza a ser más complicada, de
entrada porque, ¿cómo
sabemos qué factores primos tiene 123761232? ¿Y si 123761232 fuera él mismo un
número primo? Yendo por
partes, vemos en primer lugar que 123761232 no puede ser primo; de hecho,
aplicando las reglas de
la división vemos que es divisible por 2 y por 9, pero ni por 5 ni por 11.
Podemos en primer lugar
simplificar el problema, “sacando” todos los factores de 2 que podamos,
dividiendo sucesivamente por 2
mientras se pueda, añadiendo 1 al exponente de 2 en la factorización del número
por cada division que
podemos hacer; otro tanto haríamos con el 3.
Obtenemos así que 123761232=24×32×859453, y ahora las reglas de divisibilidad nos dicen que 859453 no es divisible por 2, 3, 5 u 11. Si intentamos dividir entre 7, vemos que la división da exacta (¡pero ya “sólo” hemos tenido que dividir entre 7 un número de 6 cifras, no uno de 9 cifras!). El resultado de la división, 122779, ya no es divisible entre 7. Tenemos que probar ahora los números primos mayores que 11, es decir, 13, 17, 19, 23,.... Tras varios intentos infructuosos, llegamos a que 122779=59×2081, luego 123761232=24×32×7×59×2081, y ya hemos acabado la factorización.
Obtenemos así que 123761232=24×32×859453, y ahora las reglas de divisibilidad nos dicen que 859453 no es divisible por 2, 3, 5 u 11. Si intentamos dividir entre 7, vemos que la división da exacta (¡pero ya “sólo” hemos tenido que dividir entre 7 un número de 6 cifras, no uno de 9 cifras!). El resultado de la división, 122779, ya no es divisible entre 7. Tenemos que probar ahora los números primos mayores que 11, es decir, 13, 17, 19, 23,.... Tras varios intentos infructuosos, llegamos a que 122779=59×2081, luego 123761232=24×32×7×59×2081, y ya hemos acabado la factorización.
La criba de Eratóstenes
¿Cómo
sabemos en el anterior caso que ya hemos acabado? ¿Y cómo sabemos por qué
números intentar dividir? Claramente, 2, 3, 5, 7, 11, 13 son primos,
pero ¿cómo sé que he dividido por todos los primos y no me he
dejado ninguno? ¿Puedo en algún momento dejar de dividir y decir que 122779 es
primo (si lo fuera)?
Las respuestas a estas dos preguntas las da el procedimiento conocido como “criba
de Eratóstenes”.
Escribimos primero todos los enteros del 1 al 100, y luego tachamos todos los
múltiplos de 2 (menos
el 2). Después tachamos los múltiplos de 3 (menos el 3). Cuando llegamos al 4,
vemos que ya está
tachado por ser múltiplo de 2, así como todos los múltiplos de 4, que también
son múltiplos de 2. El menor
entero sin tachar es el 5, y tachamos todos los múltiplos de 5 (menos el 5). El
siguiente entero sin tachar es
el 7, así que tachamos todos los múltiplos de 7 (menos el 7). Si haces esto,
comprobarás que todos los
números que te quedan sin tachar entre el 2 y el 100 son primos.
¿Por qué
con este procedimiento no nos dejamos ningún primo entre 2 y 100 sin tachar?
100 no es primo, y si un
número n menor que 100 no es primo, entonces lo podemos escribir como el
producto de dos enteros a
y b mayores que 1, n=a×b (a y b pueden ser ambos primos, o no).
Claramente, uno de estos dos números
es menor que 10, porque si fueran ambos mayores o iguales que 10, entonces n
sería mayor o igual que
100. Tenemos entonces que, o a, o b, es menor que 10, y como ya
hemos visto, los únicos números
sin tachar menores que 10 son 2, 3, 5 y 7 (los demás son múltiplos de alguno de
ellos). Luego a tiene un
factor primo que es 2, 3, 5 o 7, y por lo tanto n también lo tendría.
¡Entonces, si n está sin tachar y es
menor que 100, es primo! De la criba de Eratóstenes, obtenemos dos
conclusiones:
• si intento dividir a un
número n por todos los primos menores o iguales que su raíz cuadrada
(que
puede no
ser entera), y en ningún caso obtengo una división exacta, entonces n es
primo, y
• puedo obtener todos los
números primos menores que N, sin más que repetir la criba de
Eratóstenes,
hasta llegar a la raíz cuadrada de N (que nuevamente, no tiene por qué
ser entera).
Por
ejemplo, queremos saber si 122779 es primo: si hallo su raíz cuadrada por el
método tradicional, veo que será
350 y decimales, luego me basta con dividir hasta el mayor primo menor o igual
que 350, y como la
raíz cuadrada de 350 es 18 y decimales, me basta con realizar la criba de
Eratóstenes, tachando todos los
múltiplos de los primos hasta 17 inclusive, es decir, de 2, 3, 5, 7, 11, 13 y
17. El mayor primo menor o
igual que 350 resulta ser 349. ¡Menos mal que 122779 resulta ser divisible por
59!
Ahora
bien, una vez que hemos encontrado que 122779=59×2081, paramos. ¿Por qué?
Bueno, según lo anterior,
si 2081 no es primo, entonces es divisible por algún primo menor que su raíz
cuadrada, que es 45 y
decimales, es decir, si 2081 no es primo, entonces es divisible por algún primo
menor o igual que 43. ¡Pero
esos ya los hemos probado todos, cuando intentábamos hallar un factor primo de
122779! Luego 2081
es primo, y hemos acabado la factorización.
Hoy con la ayuda de los ordenadores (computadoras),
determinar los factores primos de números muy grandes, puede ser un simple
ejercicio. Un gran ejemplo de cómo las computadoras han cambiado el mundo es la
factorización de un número de 129 dígitos conocido como RSA-129 publicado en la
revista Science News del 7 de mayo de 1994. Este número había sido factorizado
por el método de la criba cuadrática (QS, por sus siglas en inglés), con más de
600 computadoras que trabajaron en conjunto. Aquí está el número y sus dos
factores:
114,381,625,57,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,706,
935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541 = 3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638,493,387,843,990,820,577 x 32,769,132,993,266,709,549,961,988,190,834,461,413,177,642,967,992,539,798,288,533.
114,381,625,57,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,706,
935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541 = 3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638,493,387,843,990,820,577 x 32,769,132,993,266,709,549,961,988,190,834,461,413,177,642,967,992,539,798,288,533.
También en
un escrito del 1 de octubre de 1994, publicado en Science News, Ivars Peterson
da una explicación fascinante de un descubrimiento de una máquina para
factorizar de 75 años de antigüedad. En el 1989, Jeffrey Shallit de la
Universidad de Waterloo, en Ontario, encontró un artículo de una poco conocida
revista francesa de 1920 en la que el autor, Eugene Olivier Carissan, informó
su invención del aparato para factorizar. La máquina fué encontrada en
Francia; aún existía y funcionaba,
estando almacenada en un cajón de un observatorio astronómico en Floirac, cerca
de Burdeos. La máquina funcionaba y al probarla, al Sr. Carissan le tomó 10
mínutos probar que 708,158,977 es un número primo, y fue capáz de factorizar un
número de 13 dígitos. Aunque no puede compararse con la tecnología de las
computadoras modernas, fue un logro sígnificativo en la época de Carissan.
Ganando dinero con los números primos
El 14 de noviembre de 2001, la computadora de Michael
Cameron, un a T-Bird con procesador AMD a 800 MHz, encontró el 390
número primo de Mersenne conocido, después de sólo 42 días de cómputo en los
ratos en que se encontraba disponible una computadora. El número tiene 4,053,946
dígitos. La fundación Electronics Frontier ha pagado premios de 50,000 dólares
por números primos que rompan el récord, a partir del primer primo con más de 1
millón de dígitos. El primer descubridor
de un primo de 10 millones de dígitos recibirá 100,000 dólares. Si quiere
unirse a la GIMPS (gran búzqueda en internet de primos de Mersenne) revise en
http:www.mersenne.org.
Responde a las siguientes preguntas:
1) ¿Qué es la Criba de Eratóstones?
2) Menciona 4 números primos de la criba de Eratóstenes cuya suma de los dígitos sea 13.
3) Indica cuales de estos números son
primos o compuestos: