Número Compuesto
Un número compuesto es un número cabal mayor que 1 que tiene más de dos factores, es decir, se puede dividir entre números distintos de 1 y él mismo.
Definition
Un número compuesto es un número de conteo mayor que $1$ que se puede dividir exactamente entre al menos otro número además de $1$ y él mismo, lo cual significa que tiene más de dos factores. Equivalentemente, un número compuesto $n > 1$ se puede escribir como el producto de dos enteros cada uno mayor que $1$, y tiene al menos un factor $d$ donde $1 < d < n$; el factor primo más pequeño de cualquier compuesto $n$ es como máximo $\sqrt{n}$. En la teoría de anillos, más en general, un elemento compuesto es uno que es reducible, expresable como producto de dos elementos que no son unidades ni cero, y la distinción entre elementos primos e irreducibles (que coinciden en los UFD pero no en anillos generales) es central en la teoría algebraica de números.
Example
$12$ es compuesto porque se puede dividir entre $1$, $2$, $3$, $4$, $6$, y $12$, seis factores en total. Para comprobar si $97$ es primo, se verifican los primos hasta $\sqrt{97} \approx 9.8$ (a saber, $2, 3, 5, 7$): ninguno lo divide, así que $97$ es primo, mientras que $91 = 7 \times 13$ es compuesto. Los números de Carmichael, como $561 = 3 \times 11 \times 17$, son números compuestos que pasan la prueba de primalidad de Fermat para todas las bases coprimas con ellos, mostrando por qué la prueba de Fermat por sí sola es insuficiente para certificar primalidad.
Key Insight
Si un número mayor que $1$ no es primo, es compuesto, y todo número compuesto se puede descomponer en piezas primas. El necesitar verificar solo hasta $\sqrt{n}$ hace que la Criba de Eratóstenes y la división por tanteo sean eficientes para números de tamaño moderado. La mayoría de las pruebas de primalidad usadas en criptografía (como Miller-Rabin) son probabilísticas en lugar de deterministas, porque las demostraciones deterministas de primalidad son más lentas; el algoritmo AKS (2002) fue la primera prueba de primalidad determinista en tiempo polinómico.