Historia De Los Numeros Primos
Páginas: 13 (3222 palabras)
Publicado: 19 de abril de 2011
HISTORIA DE LOS NUMEROS PRIMOS
* Matemáticas Antigua Grecia
Los números primos y sus propiedades fueron estudiados de manera exhaustiva por los matemáticos de la antigua Grecia.
Los matemáticos de la Escuela Pitagórica (500 a. C. a 300 a. C.) estaban interesados en los números por su misticismo y sus propiedades numerológicas. Ellos comprendían la idea de primalidad y estabaninteresados en los números perfectos y amigables.
Para el momento en que los Elementos Euclidianos aparecieron por el 300 a. C., ya habían sido probados varios resultados importantes acerca de números primos. En el Libro IX de los Elementos, Euclides prueba que hay infinidad de números primos. Esta es una de las primeras demostraciones conocidas en la que se utiliza el método del absurdo paraestablecer el resultado. Euclides también demuestra el Teorema Fundamental de Aritmética: Todo entero puede ser escrito como un producto único de primos.
Euclides también demostró que si el número 2n - 1 es primo, entonces el número 2n-1(2n - 1) es un número perfecto. El matemático Euler (más tarde, en 1747) pudo demostrar que todos, aún los números perfectos, tienen esta forma. Hasta el día de hoy nose sabe si existe algún número perfecto que sea impar.
Cerca del 200 a. C. el Griego Eratóstenes ideó un algoritmo para calcular números primos llamado el Tamiz de Eratóstenes.
Se da luego un gran vacío en la historia de los números primos que es usualmente llamado la Edad Obscura.
* Como encontrar números primos:
* Test de Primalidad
La criba de Eratóstenes fue concebida porEratóstenes de Cirene, un matemático griego del siglo III a. C. Es un algoritmo sencillo que permite encontrar todos los números primos menores o iguales que un número dado.
La criba de Eratóstenes es una manera sencilla de hallar todos los números primos menores o iguales que un número dado. Se basa en confeccionar una lista de todos los números naturales desde el 2 hasta ese número y tacharrepetidamente los múltiplos de los números primos ya descubiertos.
En la práctica, lo que se desea es determinar si un número dado es primo sin tener que confeccionar una lista de números primos. Un método para determinar la primalidad de un número es la división por tentativa, que consiste en dividir sucesivamente ese número entre los números primos menores o iguales a su raíz cuadrada. Sialguna de las divisiones es exacta, entonces el número no es primo; en caso contrario, es primo.
Es el test de primalidad más sencillo, y rápidamente pierde su utilidad a la hora de comprobar la primalidad de números grandes, ya que el número de factores posibles crece demasiado rápido a medida que crece el número potencialmente primo.
En efecto, el número de números primos menores que n esaproximadamente
.
De esta forma, para determinar la primalidad de n, el mayor factor primo que se necesita no es mayor que √n, dejando el número de candidatos a factor primo en cerca de
.
Esta expresión crece cada vez más lentamente en función de n, pero, como los n grandes son de interés, el número de candidatos también se hace grande: por ejemplo, para n = 1020 se tienen 450 millones decandidatos.
* Algoritmos de Factorización
Un algoritmo de factorización es un algoritmo que separa uno a uno los factores primos de un número. Los algoritmos de factorización pueden funcionar también a modo de test de primalidad, pero en general tienen un tiempo de ejecución menos ventajoso. Por ejemplo, se puede modificar el algoritmo de división por tentativa de forma que no se detengacuando se obtenga una división exacta, sino que siga realizando nuevas divisiones, y no sobre el número original, sino sobre el cociente obtenido. Después de la división por tentativa, los métodos más antiguos que se conocen son el método de Fermat, que se basa en las diferencias entre cuadrados y que es especialmente eficaz cuando n es el producto de dos números primos próximos entre sí, y el...
* Matemáticas Antigua Grecia
Los números primos y sus propiedades fueron estudiados de manera exhaustiva por los matemáticos de la antigua Grecia.
Los matemáticos de la Escuela Pitagórica (500 a. C. a 300 a. C.) estaban interesados en los números por su misticismo y sus propiedades numerológicas. Ellos comprendían la idea de primalidad y estabaninteresados en los números perfectos y amigables.
Para el momento en que los Elementos Euclidianos aparecieron por el 300 a. C., ya habían sido probados varios resultados importantes acerca de números primos. En el Libro IX de los Elementos, Euclides prueba que hay infinidad de números primos. Esta es una de las primeras demostraciones conocidas en la que se utiliza el método del absurdo paraestablecer el resultado. Euclides también demuestra el Teorema Fundamental de Aritmética: Todo entero puede ser escrito como un producto único de primos.
Euclides también demostró que si el número 2n - 1 es primo, entonces el número 2n-1(2n - 1) es un número perfecto. El matemático Euler (más tarde, en 1747) pudo demostrar que todos, aún los números perfectos, tienen esta forma. Hasta el día de hoy nose sabe si existe algún número perfecto que sea impar.
Cerca del 200 a. C. el Griego Eratóstenes ideó un algoritmo para calcular números primos llamado el Tamiz de Eratóstenes.
Se da luego un gran vacío en la historia de los números primos que es usualmente llamado la Edad Obscura.
* Como encontrar números primos:
* Test de Primalidad
La criba de Eratóstenes fue concebida porEratóstenes de Cirene, un matemático griego del siglo III a. C. Es un algoritmo sencillo que permite encontrar todos los números primos menores o iguales que un número dado.
La criba de Eratóstenes es una manera sencilla de hallar todos los números primos menores o iguales que un número dado. Se basa en confeccionar una lista de todos los números naturales desde el 2 hasta ese número y tacharrepetidamente los múltiplos de los números primos ya descubiertos.
En la práctica, lo que se desea es determinar si un número dado es primo sin tener que confeccionar una lista de números primos. Un método para determinar la primalidad de un número es la división por tentativa, que consiste en dividir sucesivamente ese número entre los números primos menores o iguales a su raíz cuadrada. Sialguna de las divisiones es exacta, entonces el número no es primo; en caso contrario, es primo.
Es el test de primalidad más sencillo, y rápidamente pierde su utilidad a la hora de comprobar la primalidad de números grandes, ya que el número de factores posibles crece demasiado rápido a medida que crece el número potencialmente primo.
En efecto, el número de números primos menores que n esaproximadamente
.
De esta forma, para determinar la primalidad de n, el mayor factor primo que se necesita no es mayor que √n, dejando el número de candidatos a factor primo en cerca de
.
Esta expresión crece cada vez más lentamente en función de n, pero, como los n grandes son de interés, el número de candidatos también se hace grande: por ejemplo, para n = 1020 se tienen 450 millones decandidatos.
* Algoritmos de Factorización
Un algoritmo de factorización es un algoritmo que separa uno a uno los factores primos de un número. Los algoritmos de factorización pueden funcionar también a modo de test de primalidad, pero en general tienen un tiempo de ejecución menos ventajoso. Por ejemplo, se puede modificar el algoritmo de división por tentativa de forma que no se detengacuando se obtenga una división exacta, sino que siga realizando nuevas divisiones, y no sobre el número original, sino sobre el cociente obtenido. Después de la división por tentativa, los métodos más antiguos que se conocen son el método de Fermat, que se basa en las diferencias entre cuadrados y que es especialmente eficaz cuando n es el producto de dos números primos próximos entre sí, y el...
Leer documento completo
Regístrate para leer el documento completo.