Resolución del problema

Lista completa de divisores de un número

Retomando las preguntas que se formularon al final de la página anterior, si tenemos la descomposición en factores primos de un número natural \(n\) es relativamente sencillo generar la lista de todos los divisores de \(n\). Lo que se hace es tomar todas las combinaciones de potencias de sus factores primos, desde cero hasta la potencia que tienen en la descomposición.

Por ejemplo, para \(360\), cuya descomposición en primos es \(2^ \color{red}3 \times3^ \color{green}2\times5^\color{blue}1\)

El número total de divisores, es decir, el tamaño de la lista, podemos calcularlo si multiplicamos las potencias de cada unos de los factores primos que aparecen en la descomposición, aumentadas en \(1\).

Por ejemplo, para \(360=2^ \color{red}3 \times3^ \color{green}2\times5^\color{blue}1\) tendremos \((\color{red}3+1)\times (\color{green}2+1)\times (\color{blue}1+1)=4\times3\times2=24\).

Esto se debe a que el número de formas en que podemos usar cada factor primo para encontrar un divisor va de cero hasta la potencia a la que está elevado en la descomposición.

En la escena de la página siguiente, aunque no es el objetivo primario, podrás constatar que es posible obtener todos los divisores de un número natural arbitrario variando los exponentes de la descomposición en factores primos correspondiente.

A continuación se muestra la lista completa de los \(24\) divisores, ordenados de menor a mayor. La raíz cuadrada de \(360\) es poco más de \(18.97\), por lo que primero obtendremos los \(12\) divisores de \(360\) menores que \(18.97\),

\(2^0\times3^0\times5^0=1\),
\(2^1\times3^0\times5^0=2\),
\(2^0\times3^1\times5^0=3\),
\(2^2\times3^0\times5^0=2\times2=4\),
\(2^0\times3^0\times5^1=5\),
\(2^1\times3^1\times5^0=2\times3=6\),
\(2^3\times3^0\times5^0=2\times2\times2=8\),
\(2^0\times3^2\times5^0=3\times3=9\),
\(2^1\times3^0\times5^1=2\times5=10\),
\(2^2\times3^1\times5^0=4\times3=12\),
\(2^0\times3^1\times5^1=3\times5=15\) y
\(2^1\times3^2\times5^0=2\times9=18\).

Los \(12\) divisores complementarios a los anteriores, que son mayores que la raíz cuadrada de \(360\), son los siguientes:

\(360/18=20\),
\(360/15=24\),
\(360/12=30\),
\(360/10=36\),
\(360/9=40\),
\(360/8=45\),
\(360/6=60\),
\(360/5=75\),
\(360/4=90\),
\(360/3=120\),
\(360/2=240\) y
\(360/1=360\).

Preguntas
  • ¿Crees que la segunda parte de la lista puede también obtenerse usando potencias de los factores primos?

  • De la lista anterior, ¿cuáles serán los divisores que dan solución a nuestro problema?