Factorización prima

Factorización prima: la huella que cada número tiene exactamente una vez

Todo entero mayor que 1 es un producto de números primos y —esto es lo que lo hace útil— lo es de una sola manera. El teorema fundamental de la aritmética garantiza que la factorización es única, por eso funciona como huella y por eso se apoya en ella tanto, desde simplificar fracciones hasta la criptografía de clave pública.

Cómo funciona

• Descompone un número en factores primos, en forma de potencias y desarrollado por completo.
• Cuenta los divisores sin enumerarlos, directamente a partir de los exponentes.
• Dice si el número es primo, que no es más que el caso en que se factoriza en sí mismo.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Ejemplo resuelto

Factorizar 360 extrayendo repetidamente el primo más pequeño que encaje.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5, y ninguna otra combinación de primos da 360. Solo de los exponentes se deduce el número de divisores: (3+1)(2+1)(1+1) = 24, porque cualquier divisor elige de 0 a 3 doses, de 0 a 2 treses y 0 o 1 cinco.

Cómo leer el resultado

• La fórmula de los divisores merece conocerse por sí sola. Nunca hace falta listarlos para contarlos: suma uno a cada exponente y multiplica, porque construir un divisor es elegir de forma independiente cuántos de cada primo incluir.
• La división por tanteo solo necesita probar hasta la raíz cuadrada. Si n tiene un factor mayor que √n, forzosamente tiene el complementario por debajo, así que pasada la raíz no queda nada por hallar. Por eso factorizar un número de seis cifras es instantáneo.
• Tras el 2 y el 3 la herramienta avanza de seis en seis y solo comprueba 6k−1 y 6k+1. Todos los demás restos ya son divisibles por 2 o 3, lo que descarta gratis dos tercios de los candidatos.
• Que factorizar sea difícil para números muy grandes es una propiedad, no una limitación de esta herramienta. RSA se apoya en que multiplicar dos primos grandes es fácil y recuperarlos no lo es: esa asimetría es todo el argumento de seguridad.

Preguntas frecuentes

¿Es 1 un número primo?

No, y excluirlo es una decisión deliberada, no un descuido. Si el 1 contara como primo, las factorizaciones dejarían de ser únicas —6 podría ser 2×3, o 1×2×3, o 1×1×2×3— y el teorema que hace útil la factorización necesitaría una excepción incómoda en cada enunciado.

¿Por qué mi número se factoriza solo en sí mismo?

Porque es primo. Un primo no tiene más divisores que 1 y él mismo, así que su factorización es un único término con exponente uno. La herramienta lo dice explícitamente en vez de dejar que lo deduzcas de una lista de un elemento.