Número Primo
Un número primo es un número cabal mayor que 1 que solo se puede dividir de manera exacta entre 1 y él mismo.
Definition
Un número primo es un número de conteo mayor que $1$ que solo se puede dividir exactamente entre $1$ y él mismo, teniendo exactamente dos divisores positivos. El número $1$ no es ni primo ni compuesto, y por el Teorema Fundamental de la Aritmética, todo entero mayor que $1$ es primo o un producto único de primos. Formalmente, un primo $p$ en $\mathbb{Z}$ es un elemento irreducible: si $p \mid ab$ entonces $p \mid a$ o $p \mid b$.
Example
$7$ es primo, ya que solo $1 \times 7 = 7$, pero $6$ no lo es, ya que $2 \times 3 = 6$ le da cuatro factores. $13$ es primo (divisores: $1, 13$), mientras que $15$ es compuesto (divisores: $1, 3, 5, 15$); los primos hasta $30$ son $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$. Los primos de Mersenne toman la forma $2^p - 1$ (por ejemplo, $2^7 - 1 = 127$), y el cifrado RSA se apoya en la dificultad de factorizar $n = pq$ para primos grandes $p, q$.
Key Insight
Piensa en los primos como números que no se pueden organizar en un rectángulo de más de una fila: $7$ puntos solo se pueden organizar como $1$ fila de $7$. El $2$ es el único primo par, y la Criba de Eratóstenes encuentra todos los primos hasta $n$ tachando los múltiplos de cada primo comenzando en $2$. Los primos son los "átomos" de la multiplicación en $\mathbb{Z}$; el Teorema de los Números Primos establece que $\pi(n) \sim n / \ln(n)$ donde $\pi(n)$ cuenta los primos hasta $n$, y la Hipótesis de Riemann, de demostrarse, daría la cota más ajustada conocida sobre el error en ese teorema.