Divisibilidad y Números Primos

La divisibilidad, el máximo común divisor y los números primos constituyen la base de la teoría de números: cada número entero se construye multiplicativamente a partir de los números primos, y la forma en que se construye rige casi todos los resultados posteriores.

Definition

Un número entero a divide a b si b es igual a a multiplicado por algún número entero; un número primo es un número entero mayor que uno cuyos únicos divisores positivos son uno y él mismo. La divisibilidad y los números primos se refieren a la descomposición multiplicativa de los números enteros y a los bloques de construcción irreducibles de esa descomposición.

Scope

Este tema trata la relación de divisibilidad en los números enteros, el algoritmo de la división, los máximos comunes divisores y los mínimos comunes múltiplos calculados mediante el algoritmo euclidiano, la identidad de Bezout, el lema de Euclides, el teorema fundamental de la aritmética y la teoría elemental de los números primos —su infinitud, heurísticas de distribución y primalidad.

Core questions

• ¿Cómo calcula el algoritmo euclidiano los máximos comunes divisores y produce la identidad de Bezout?
• ¿Por qué el lema de Euclides obliga a que la factorización en números primos sea única?
• ¿Cómo se puede demostrar que hay infinitos números primos y qué revelan tales demostraciones?
• ¿Cómo se distribuyen los números primos entre los números enteros y cómo se decide la primalidad en la práctica?

Key theories

Algoritmo de la división y algoritmo euclidiano

Cualquier número entero dividido por un número entero positivo deja un cociente y un resto únicos; la iteración de esto da el máximo común divisor y, mediante sustitución inversa, números enteros que lo expresan como una combinación lineal (identidad de Bezout).

Teorema fundamental de la aritmética

Todo número entero mayor que uno es un producto de números primos que es único salvo por el orden; el lema de Euclides (un número primo que divide un producto divide un factor) es el paso clave.

Infinitud de los números primos

El argumento clásico de Euclides demuestra que ninguna lista finita de números primos es completa; la fórmula del producto de Euler para la función zeta proporciona una prueba analítica y cuantifica la densidad de los números primos a través de la divergencia de la suma de los recíprocos de los números primos.

Clinical relevance

La factorización rápida y las pruebas de primalidad son fundamentales para la criptografía: la seguridad de RSA se basa en la dificultad de factorizar grandes productos de dos números primos, mientras que las pruebas de primalidad eficientes (como Miller-Rabin) hacen que la generación de claves sea práctica.

History

Los Elementos de Euclides (c. 300 a. C.) ya contenían el algoritmo euclidiano, el lema de Euclides y la prueba de que los números primos son infinitos. El cribado de Eratóstenes proporcionó el primer método sistemático para listar los números primos, y el trabajo de Euler, Legendre y Gauss en los siglos XVIII y XIX reformuló la distribución de los números primos como un problema cuantitativo.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

¿Es el uno un número primo?

No. El uno se excluye por definición para que la factorización prima sea única; si el uno contara como primo, cada número tendría infinitas factorizaciones.

¿Para qué se utiliza la identidad de Bezout?

Establece que el máximo común divisor de dos números enteros es una combinación lineal entera de ellos, lo cual es la base para calcular inversas modulares y resolver ecuaciones diofánticas lineales.