Aprende a descomponer cualquier numero en sus factores primos. Con el metodo del arbol y de divisiones sucesivas, y aplicaciones en MCD y MCM.
Descomponer un numero en factores primos significa escribirlo como producto de numeros primos. Todo numero mayor que 1 tiene una unica descomposicion en factores primos (Teorema Fundamental de la Aritmetica). 12 = 2² × 3. 60 = 2² × 3 × 5. 100 = 2² × 5².
Con la factorizacion prima, calcular MCD y MCM es mecanico. Para MCD(360, 180): 360=2³×3²×5, 180=2²×3²×5. MCD=factores comunes con el menor exponente=2²×3²×5=180. Para MCM: factores con el mayor exponente=2³×3²×5=360. Nota: 180 divide exactamente a 360, lo que confirma MCD=180 y MCM=360.
La factorizacion prima es la base de la criptografia moderna. El algoritmo RSA, que protege las comunicaciones de internet, se basa en que multiplicar dos primos grandes es facil pero factorizar su producto es computacionalmente inviable. El numero 15=3×5 se factoriza en microsegundos. Un numero de 2048 bits (producto de dos primos de 1024 bits) tardaría mas que la edad del universo en factorizarse con los mejores algoritmos actuales. La dificultad de la factorizacion prima protege tus transacciones bancarias, mensajes y datos personales.
La factorizacion prima tiene una aplicacion elegante en los calendarios. El ciclo del calendario Maya (la Rueda del Calendario) tenia dos partes: el Tzolkin de 260 dias (13×20) y el Haab de 365 dias (5×73). El MCM de 260 y 365 es MCM(13×20, 5×73). Como 13, 20=4×5, 5 y 73 son primos o potencias de primos: MCM = 13×4×5×73 = 18,980 dias = 52 años haab = 73 tzolkin. Este ciclo de 52 años se llamaba el Siglo Maya. Los mayas usaron factorizacion prima (implicitamente) para diseñar su sistema calendárico hace 2,000 años.
Encontrar todos los divisores de un numero usando su factorizacion prima es sistematico. Para N = p1^a1 × p2^a2 × ... × pk^ak, el numero total de divisores es (a1+1)×(a2+1)×...×(ak+1). Para 360 = 2^3 × 3^2 × 5^1: divisores = (3+1)(2+1)(1+1) = 4×3×2 = 24 divisores. La suma de divisores es (1+2+4+8)(1+3+9)(1+5) = 15×13×6 = 1170. Estos calculos aparecen en teoria de numeros y tienen aplicaciones en diseño de algoritmos de busqueda y compression de datos.