Número primo

Un entero mayor que 1 que no es primo se llama compuesto, y se escribe como producto de enteros menores: \(91=7\cdot13\). El 1 no es ni primo ni compuesto; excluirlo no es un capricho, pues permite que la factorización de abajo sea única. El único primo par es 2, y los primeros son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

El teorema fundamental de la aritmética afirma que todo entero \(n>1\) se escribe como producto de primos, y de una sola manera salvo el orden: \(360=2^3\cdot3^2\cdot5\). Esa unicidad descansa en el lema de Euclides: si un primo divide a \(ab\), divide a \(a\) o a \(b\). Con ella se calculan el máximo común divisor y el número de divisores (si \(n=p_1^{e_1}\cdots p_r^{e_r}\), hay \((e_1+1)\cdots(e_r+1)\)), y se justifican muchas demostraciones.

Para decidir si \(n\) es primo basta probar los primos \(p\le\sqrt n\): si \(n=ab\) con \(a\le b\), entonces \(a\le\sqrt n\). Euclides demostró que hay infinitos primos: si fueran finitos, \(p_1p_2\cdots p_r+1\) tendría un factor primo fuera de la lista. Los primos son la base de la criptografía de clave pública, que se apoya en lo difícil que es factorizar números enormes.