Números primos
Decimos que un número entero p>1 es primo si sus únicos divisores positivos son 1 y p.
-
Si un número entero q >1 no es primo, se le llama número compuesto. Por tanto, un entero q será compuesto si y sólo si existen
a,b enteros positivos (menores que q) tales que q=ab.
- Si mcd(a,b)=1 se dice que a y b son primos entre sí o que son primos relativos.
Algunas propiedades importantes sobre los números primos y compuestos:
- Si p es primo, p|x1.x2...xn ⇒ p|xi para algún i
Teorema Fundamental de la Aritmética: Todo número natural mayor que 1 o bien es primo, o bien se puede descomponer como producto de números primos.
Además esta descomposición es única -salvo el orden de los factores-.
- Si un número n es compuesto, se verifica que ha de tener un divisor primo menor o igual que su raíz cuadrada.
- Existen infinitos números primos
El método más antiguo y conocido de obtener todos los números primos menores que un entero dado n es la criba de
Eratóstenes,
método inventado por el matemático griego del mismo nombre en el siglo III a.C. Consiste en disponer en una tabla todos los enteros entre 2 y
n. Se empieza eliminando de la tabla todos los múltiplos de 2. En el siguiente paso se hace igual con los múltiplos de 3, luego
con los múltiplos de 5 (pues el 4 y sus múltiplos quedaron elimimados en el primer paso), etc. Así hasta que no puedan eliminarse más múltiplos de la tabla.
Los números que finalmente queden en la tabla serán todos números primos, entre 2 y n.
Por la observación hecha anteriormente sobre los números compuestos, ocurre que sólamente es necesario cribar en la tabla
hasta que lleguemos al paso correspondiente a un número mayor o igual que √n. El resto de números que queden por tachar a
partir de este momento ya serán todos números primos.
 |
 |
 |
| Anterior |
Arriba |
Siguiente |
