EL TEOREMA DE ERATÓSTENES

 

Eratóstenes de Cirene

 

 

Los números primos han sido estudiados a lo largo de la historia de la humanidad por todos los matemáticos que de seriedad en su trabajo se jactan. Todo teorema o toda cuestión entorno a este tipo de entidades matemáticas significa siempre un avance en el Cálculo como la rama de la Matemática que estudia a los números.  Con la noción del teorema fundamental de la Aritmética trabajaron los griegos antiguos sin problemas, considerándola válida por hipótesis (si es que en verdad la consideraban una hipótesis).

Eratóstenes es conocido por su criba, que es un algoritmo útil para mostrar cuáles son los números primos dado un conjunto de n números naturales. Sin embargo, no es éste el trabajo más importante en cuanto a las pruebas de primalidad o composición que se tienen de él. Existe una cuestión que sin lugar a dudas constituye el primer paso para la eficaz demostración de primalidad acerca de un número dado y es el teorema que lleva su nombre.

Dice Eratóstenes «si un natural no es divisible entre ninguno de los primos cuyo cuadrado es menor o igual a tal número, entonces éste es primo». Se demostrará que el teorema es válido:

1. m<p²; el cuadrado del primo p es mayor que el número por analizarse m. Se lee de a<b que a es menor que b.
2. m=p·q; donde q es otro natural y suponiendo que m es divisible de p.
3. q²<m y q<m^1/2, porque de lo contrario, se tendría que m²<p²·q², sabiéndose que 1) los tres números son positivos y 2) el producto forzosamente debe ser mayor que el cuadrado de m (de no serlo, la premisa 1 no sería válida). Luego, m<p·q quedaría porque lo anterior lo confirma, y se contradice a 2.
4. El natural q puede ser un primo o es el producto de diferentes números primos que finalmente son menores que m^1/2. Como esto se cumple para todos los números compuestos semejantes a m, si no es así, entonces se trata de un número primo.

Una vez demostrado el teorema, queda por exponer cuál es la forma en que puede éste interpretarse para generar un algoritmo que evalúe la primalidad de un número dado. A continuación, se exponen los pasos necesarios:

1. Se conoce al número y se extrae la raíz cuadrada.
2. Se hipotetiza que el número es divisible de un natural inmediatamente menor o igual a la raíz cuadrada.
3. Si es éste número igual a 1, entonces el número es primo.
4. Si se cumple, el número analizado es compuesto.
5. Si no se cumple, se hipotetiza que el número es divisible de un natural inmediatamente menor al que sirvió anteriormente.
6. Si es éste número igual a 1, entonces el número es primo.
7. Si se cumple, el número analizado es compuesto.
8. Si no se cumple, se hipotetiza como en el paso 5 y se continúa a partir de allí.

Se necesita que el último número sea igual a 1 porque en esencia, el algoritmo no tiene un listado previo que verifique cuáles son los números primos menores a la raíz del número analizado y, dado que 1 sería el único divisor de un número primo con este método, si esto ocurre efectivamente se tiene como resultado un número primo. Como se puede notar, el teorema de Eratóstenes garantiza que el límite máximo necesario para el análisis es la raíz cuadrada del número en cuestión y con ello se agiliza especialmente el proceso de identificación.

A manera de ejemplo, se tomará a un número primo y a un número compuesto para poner a prueba el algoritmo:

Que el número compuesto sea 10:

1. Se conoce al número y se extrae la raíz cuadrada.
   La raíz de 10 es aproximadamente 3.16.
2. Se hipotetiza que el número es divisible de un natural inmediatamente menor o igual a la raíz cuadrada.
   La hipótesis es que 10 es divisible de 3.
3. Si es éste número igual a 1, entonces el número es primo.
   El número 3 no es igual a 1, y se continúa.
4. Si se cumple, el número analizado es compuesto.
   No se cumple que 10 sea divisible de 3 (porque 10/3 = 3.33..., que no es natural), y se continúa.
5. Si no se cumple, se hipotetiza que el número es divisible de un natural inmediatamente menor al que sirvió anteriormente.
   La [nueva] hipótesis es que 10 es divisible de 2 (porque 2 es el natural inmediatamente menor a 3).
6. Si es éste número igual a 1, entonces el número es primo.
   El número 2 no es igual a 1, y se continúa.
7. Si se cumple, el número analizado es compuesto.
   Se cumple que 10 es divisible de 2 (porque 10/2=5, que es natural), y se detiene el análisis. El 10 es compuesto.
8. Si no se cumple, se hipotetiza como en el paso 5 y se continúa a partir de allí.
   Este paso no se lleva a cabo porque el análisis se interrumpió.

Análogamente, que el número primo sea 11:

1. Se conoce al número y se extrae la raíz cuadrada.
   La raíz de 11 es aproximadamente 3.32.
2. Se hipotetiza que el número es divisible de un natural inmediatamente menor o igual a la raíz cuadrada.
   La hipótesis es que 11 es divisible de 3.
3. Si es éste número igual a 1, entonces el número es primo.
   El número 3 no es igual a 1, y se continúa.
4. Si se cumple, el número analizado es compuesto.
   No se cumple que 11 sea divisible de 3 (porque 11/3 = 3.66..., que no es natural), y se continúa.
5. Si no se cumple, se hipotetiza que el número es divisible de un natural inmediatamente menor al que sirvió anteriormente.
   La [nueva] hipótesis es que 11 es divisible de 2 (porque 2 es el natural inmediatamente menor a 3).
6. Si es éste número igual a 1, entonces el número es primo.
   El número 2 no es igual a 1, y se continúa.
7. Si se cumple, el número analizado es compuesto.
   No se cumple que 11 sea divisible de 2 (porque 11/2=5.5, que es no natural), y se continúa.
8. Si no se cumple, se hipotetiza como en el paso 5 y se continúa a partir de allí.
   La [nueva] hipótesis es que 11 es divisible de 1 (porque 1 es el natural inmediatamente menor a 2).
9. Si es éste número igual a 1, entonces el número es primo.
   El número 1 es igual a 1, y se detiene el análisis. El 11 es primo.

En ambos casos sólo se evalúa la divisibilidad de los números respecto a otros dos, mientras que al probar con cada uno de los números inmediatamente menores a los pertinentes en el análisis, se requieren de cinco o diez, respectivamente, pasos para llegar al mismo resultado. Mostrado que el algoritmo basado en el teorema de Eratóstenes es válido, sólo cabe aclarar que puede ser programado a través de un ordenador para agilizar aún más el cálculo.

∎

20 de Enero de 2013

El programa de ordenador (escrito en lenguaje C) puede encontrarse en el siguiente enlace:

https://docs.google.com/file/d/0Bz70TnooCVOybGtuT3c2NlB4R0U/edit

También se tiene el programa compilado para terminal (extensión .out):

https://docs.google.com/file/d/0Bz70TnooCVOyRm4xcDlJcmM1SWc/edit