Número y suma de divisores#
Introducción#
En este capítulo vamos a presentar dos funciones relacionadas con los divisores de un número entero \(n\). Primero veremos la función sigma, denotada con la letra griega \(\sigma(n)\). Esta función calcula la suma de todos los divisores positivos de un número entero \(n\). Como consecuencia de la función \(\sigma\), veremos la función tau, denotada con la letra griega \(\tau(n)\), esta función cuenta el número total de divisores positivos de un número entero \(n\).
Suma de divisores#
Definición 16
La función suma de divisores, denotada por la letra griega \(\sigma\), es definida como \(\sigma (n)\) que es igual a la suma de todos los divisores positivos de \(n\).
Ejemplo 42
Calculemos los primeros \(8\) valores de la función \(\sigma(n):\)
Observación 6
De lo anterior podemos notar dos cosas.
Si \(n = 1\), entonces \(\sigma(n) = \sigma(1) = 1\).
Si \(n = p\), donde \(p\) es cualquier número primo, tenemos que \(\sigma(n) = \sigma(p) = 1 + p\).
Ahora, veamos qué pasa cuando la factorización en primos de \(n\) es de la forma \(n = p^\alpha\).
Proposición 10
Sea \(p\) un primo y \(\alpha\) un entero positivo. Si \(n = p^\alpha\), entonces la suma de todos los divisores positivos de \(n\) es:
Demostración. Procederemos por inducción sobre el número de divisores.
Sea \(P(k)\) la proposición que afirma que para el entero positivo \(k\) se cumple que la suma de los divisores del número \(n=p^k\) es:
Base inductiva. Verifiquemos que \(P(0)\) es verdadera.
Si \(k=0\) entonces tenemos que \(n = p^0=1\).
Por un lado, tenemos que
Y por otro lado, tenemos que
Así, ambas expresiones coinciden.
Hipótesis inductiva. Supongamos que \(P(k)\) es verdadera para algún entero positivo \(k\), es decir que, si \(n=p^k\) entonces la suma de sus divisores es,
Paso inductivo. Veamos que \(P(k)\) implica \(P(k+1)\).
Si \(n = p^{k+1}\) tendríamos que,
Así, por inducción \(P(n)\) es verdadera para todo entero \(n \ge 0. \square\)
La fórmula anterior se puede extender para cuando \(n\) tiene más de un primo en su descomposición canónica. Veamos la generalización para la función suma de divisores.
Proposición 11 (Fórmula para la suma de divisores)
Si tenemos un número \(n\) con factorización en primos \(n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\), entonces la suma de sus divisores positivos es:
Demostración. Sea \(P(k)\) la proposición que afirma que para el entero positivo \(k\) se cumple que la suma de los divisores positivos de \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\) es:
Base inductiva. Verifiquemos que \(P(1)\) es verdadera.
Por la Proposición 10 ya tenemos que si \(n = p_1^{\alpha_1}\) para cualquier entero \(\alpha_1 \ge 0\), la suma de los divisores positivos de \(n = p_1^{\alpha_1}\) es:
Para ver mas claro la idea de la inducción, verifiquemos que \(P(2)\) es verdadera.
Esto es, que si \(n = p_1^{\alpha_1}p_2^{\alpha_2}\) para cualesquiera \(\alpha_i \ge 0\) en donde \(i=1,2\) tenemos que la suma de los divisores de \(n\) es:
Notemos que los divisores de \(n = p_1^{\alpha_1}p_2^{\alpha_2}\) por el Lema 5 son de la forma \(p_1^{e_1}p_2^{e_2}\) en donde \(0\le e_i \le \alpha_i\) para \(i=1,2\). Entonces tendríamos lo siguiente,
Por lo tanto se cumple lo buscado.
Hipótesis inductiva. Supongamos que \(P(k)\) es verdadera para algún entero positivo \(k\), es decir que, la suma de los divisores positivos de \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\) es:
Paso inductivo. Veamos que si \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\), tendríamos que los divisores de dicho número son de la forma \(p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}p_{k+1}^{e_{k+1}}\) en donde \(0 \le e_i \le \alpha_i\) para \(i = 1,2,3,\ldots,k,k+1\), y un divisor de esta forma justo se puede reescribir como \(dp_{k+1}^{e_{k+1}}\) con \(d\) un divisor de \(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\), así tenemos que:
Notemos que lo que hicimos fue solamente correr los exponentes del término \(p_{k+1}\) de \(0\) a \(\alpha_{k+1}\) y así en cada uno de los términos \(p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}\) los exponentes van corriendo desde \(0 \le e_i \le \alpha_i\) para \(i = 1,2,3,\ldots,k\) y por la hipótesis de inducción podemos concluir que son igual a
Así, concluimos que por inducción la fórmula es válida para todo \(n \ge 1. \square\)
Ejemplo 43
Dado el número \(6120\), calcula \(\sigma(6120)\).
Solución.
Ya sabemos que \(6120 = 2^3\cdot 3^2\cdot 5\cdot 17\), entonces:
Veamos una propiedad que cumple la función \(\sigma(n)\).
Proposición 12
Si \(a\) y \(b\) son números enteros tales que \((a,b) = 1\), entonces \(\sigma(ab) = \sigma(a) \cdot \sigma(b)\).
Demostración. Sea \(n = ab\).
Supongamos que la descomposición en primos de \(a\) y \(b\) es,
en donde \(a_k\) y \(b_l\) son los factores primos de cada número.
Como \((a,b) = 1\), tenemos que \(a\) y \(b\) no comparten ningún divisor en común, es decir que \(a_i \neq b_j\) para \(1 \le i \le k\) y \(1 \le j \le l\).
Luego por la Proposición 11 tenemos que:
Luego tenemos que \(n= a_1^{\alpha_1}a_2^{\alpha_2}\cdot \ldots \cdot a_k^{\alpha_k} b_1^{\beta_1}b_2^{\beta_2}\cdot \ldots \cdot b_l^{\beta_l}\) y por la Proposición 11 tenemos que:
Código para calcular la suma de los divisores de un entero \(n\)#
Para los siguientes códigos vamos a utilizar y modificar la función que escribimos en el capítulo del teorema fundamental de la aritmética.
La siguiente función nos regresa dos listas, en la primera se encuentran los primos y en la segunda se encuentran los exponentes de dichos primos involucrados en la descomposición canónica de un número dado.
def fact_primos_exponentes(n):
a = n
lst_descomp = []
for i in range(2, a+1):
while a % i == 0:
lst_descomp.append(i)
a //= i
if a == 1:
break
lst_primos = set(lst_descomp)
lst_exp = []
for i in lst_primos:
exp = lst_descomp.count(i)
lst_exp.append(exp)
return [list(lst_primos), lst_exp]
fact_primos_exponentes(6120)
[[17, 2, 3, 5], [1, 3, 2, 1]]
fact_primos_exponentes(168)
[[2, 3, 7], [3, 1, 1]]
fact_primos_exponentes(2520)
[[2, 3, 5, 7], [3, 2, 1, 1]]
fact_primos_exponentes(83646)
[[2, 3, 1549], [1, 3, 1]]
La siguiente función calcula la suma de los divisores de un entero \(n\) dado.
def suma_divisores(n):
b = n
lst_prim_exp = fact_primos_exponentes(b)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
suma = 1
for i in range(len(lst_prim_exp[0])):
a = ((lst_prim_exp[0][i])**(lst_1[i])-1)//(lst_prim_exp[0][i] -1)
suma *= a
return print("La suma de los divisores del número ",n," es:", suma)
suma_divisores(6120)
La suma de los divisores del número 6120 es: 21060
suma_divisores(168)
La suma de los divisores del número 168 es: 480
suma_divisores(2520)
La suma de los divisores del número 2520 es: 9360
suma_divisores(83646)
La suma de los divisores del número 83646 es: 186000
Número de divisores#
Definición 17
La función número de divisores denotada por la letra griega \(\tau\), es definida como \(\tau (n)\) que es igual al número de divisores positivos del entero \(n\).
Ejemplo 44
Calculemos los primeros \(8\) valores de la función \(\tau(n)\):
Observación 7
De lo anterior podemos notar dos cosas.
Si \(n=1\), entonces \(\tau (1) = 1\) y es el único número positivo que tiene solamente un divisor.
Si \(n = p\), donde \(p\) es cualquier número primo, tenemos que \(\tau (n) = 2\).
Veamos el caso cuando \(n\) tiene un sólo primo en su factorización, es decir, \(n = p^\alpha\). Notemos que de la función \(\sigma(n)\) tenemos que,
Corolario 5
Sea \(p\) un primo y \(\alpha\) un entero positivo. Si \(n = p^\alpha\) entonces \(n\) tiene \(\alpha +1\) divisores, es decir que, \(\tau (n) = \tau(p^\alpha) = \alpha+1\).
La fórmula anterior se puede generalizar para cualquier número \(n\) teniendo en cuenta que por el Teorema 12 podemos descomponer dicho número en sus factores primos, es decir, \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\).
Proposición 13 (Fórmula para el número de divisores)
Si tenemos un número \(n\) con factorización en primos \(n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\), entonces la cantidad de divisores que tiene el entero \(n\) es:
Es decir que \(\tau (n) = \tau(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}) = (\alpha_1 +1)(\alpha_2 +1)\cdots(\alpha_k +1)\).
Demostración. La idea de la demostración es usar combinatoria, en especial usar el principio de la multiplicación y usar inducción sobre el número de primos que tenemos en la factorización.
Sea \(P(k)\) la proposición que afirma que para el entero positivo \(k\) se cumple que el número \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\) tiene \((\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\) divisores. Es decir que,
Base inductiva. Verifiquemos que \(P(1)\) es verdadera. Por el Corolario 5 ya tenemos que si \(n = p_1^{\alpha_1}\) para cualquier entero \(\alpha_1\), sucede que \(p^\alpha_1\) tiene \(\alpha_1 + 1\) divisores, es decir que,
Para fines didácticos verifiquemos que \(P(2)\) es verdadera.
Si \(n = p_1^{\alpha_1}p_2^{\alpha_2}\), por el Lema 5 sabemos que \(p_1^{\alpha_1}p_2^{\alpha_2}\) contiene todos los divisores de \(p_1^{\alpha_1}\) que son \(\alpha_1 + 1\) y los divisores de \(p_2^{\alpha_2}\) que son \(\alpha_2 + 1\). Luego los divisores del número \(n\) son de la forma \(p_1^{e_1}p_2^{e_2}\), en donde \(0 \le e_1 \le \alpha_1\) y \(0 \le e_2 \le \alpha_2\). Utilizando el principio de la multiplicación, tenemos que \(p_1^{\alpha_1}p_2^{\alpha_2}\) tiene \((\alpha_1 +1)(\alpha_2 +1)\) divisores, es decir que,
Hipótesis inductiva. Supongamos que \(P(k)\) es verdadera. Esto es que para \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\) el número \(n\) tiene \((\alpha_1 +1)(\alpha_2 +1)\cdots(\alpha_k +1)\) divisores, es decir que,
Paso inductivo. Tomemos el número \(n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\).
Sabemos que \(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\) contiene a todos los divisores de \(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\) que por la hipótesis de inducción son \((\alpha_1 +1)(\alpha_2 +1)\cdots(\alpha_k +1)\). Luego por el Corolario 5 tenemos que \(p_{k+1}^{\alpha_{k+1}}\) tiene \(\alpha_{k+1} +1\) divisores, además cada uno de estos divisores dividen a \(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\). Utilizando el principio de la multiplicación tenemos que \(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\) tiene \((\alpha_1 +1)(\alpha_2 +1)\cdots(\alpha_k +1)(\alpha_{k+1} +1)\) divisores, es decir que,
Ejemplo 45
Dado el número \(6120\), calcula \(\tau (6120)\).
Solución.
Primero, por el Teorema 12 tenemos que \(6120=2^3\cdot 3^2\cdot 5\cdot 17\), entonces tenemos que:
Código para calcular el número de divisores de un entero \(n\)#
La siguiente función calcula el número de divisores que tiene un entero dado.
def numero_divisores(n):
a = n
lst_prim_exp = fact_primos_exponentes(a)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
divisores = 1
for k in lst_1:
divisores *= k
return print("El número ",n , "tiene: ",divisores, " divisores.")
numero_divisores(127)
El número 127 tiene: 2 divisores.
numero_divisores(198)
El número 198 tiene: 12 divisores.
numero_divisores(2520)
El número 2520 tiene: 48 divisores.
numero_divisores(8364)
El número 8364 tiene: 24 divisores.
Explicación del código#
En este capítulo introducimos una estructura de datos, los conjuntos. Un conjunto en Python es una colección desordenada de elementos únicos. Los conjuntos en Python son similares a los conjuntos matemáticos.
Los conjuntos no pueden contener elementos duplicados. Si intentamos agregar un elemento que ya está presente en el conjunto, este no se duplicaría y el conjunto permanecería sin cambios. Los elementos en un conjunto no tienen un orden específico, esto significa que no podemos acceder a los elementos de un conjunto utilizando índices, ya que no están indexados. Sin embargo, podemos iterar sobre los elementos de un conjunto usando un bucle for. La sintaxis para crear un conjunto es poner los elementos entre llaves como se muestra en el siguiente ejemplo.
conjunto = {1,2,3,4}
Además de crear un conjunto, podemos transformar un elemento iterable en un conjunto con la función set(). En esta ocasión lo que hicimos fue transformar una lista en un conjunto. Al utilizar la función set() sobre una lista lo que sucede es lo siguiente:
Los elementos duplicados se eliminan, dejando únicamente una instancia de cada elemento único.
Como son colecciones desordenadas, la ordenación de los elementos no está garantizada y puede variar de una ejecución a otra.
Para convertir una lista en un conjunto simplemente tenemos que ingresarla en la función set() como argumento.
lista = [1,1,2,2,3,3,4,4,5,5,6,6]
conjunto = set(lista)
El valor de la variable «conjunto» sería el siguiente \(\{ 1,2,3,4,5,6 \}\).
De igual manera existe una función llamada list()la cual convierte un elemento iterable en una lista. En este caso la usamos ya que los conjuntos al no ser indexados dificultan usar los valores dentro de él. Utilizar esta función sobre un conjunto no modifica los valores ni los cambia de orden.
Como hemos visto, a las listas les podemos aplicar varios métodos. En este caso usamos el método count(), este método lo que hace es contar cuántas veces aparece un elemento en la lista. Es decir que si queremos saber cuántas veces aparece el elemento \(2\) en el siguiente ejemplo tendríamos que:
lista = [1,2,3,4,2,6,2,7,2]
veces = lista.count(2)
El valor de la variable «veces» sería igual a \(4\), ya que el número \(2\) aparece \(4\) veces en la lista. Este método no sólo funciona para números, depende de los elementos que contengan nuestras listas.
Hemos visto varias maneras de seleccionar elementos de una lista, pero cuando una lista tiene como elementos listas y queremos seleccionar un elemento dentro de esas listas podemos hacer lo siguiente.
lista_general = [[1,2,3,4,5], [6,7,8,9],[10,11,12]]
a = lista_general[1][3]
En el ejemplo anterior el valor de la variable \(a\) sería igual a \(9\), ya que seleccionamos la segunda lista y de ésta el cuarto valor.
Ahora, veamos cómo funcionan los códigos.
El primer código que usamos es una versión modificada del código creado en el capítulo del teorema fundamental de la aritmética.
def fact_primos_exponentes(n):
a = n
lst_descomp = []
for i in range(2, a+1):
while a % i == 0:
lst_descomp.append(i)
a //= i
if a == 1:
break
lst_primos = set(lst_descomp)
lst_exp = []
for i in lst_primos:
exp = lst_descomp.count(i)
lst_exp.append(exp)
return [list(lst_primos), lst_exp]
La primera parte de esta función ya la explicamos en el capítulo del teorema fundamental de la aritmética. La modificación es que al final del break no termina la función, si no que, ocupamos la lista «lst_descomp» que se genera con la descomposición canónica para la siguiente parte.
def fact_primos_exponentes(n):
a = n
lst_descomp = []
for i in range(2, a+1):
while a % i == 0:
lst_descomp.append(i)
a //= i
if a == 1:
break
Después de obtener la lista de primos creamos dos variables.
La primera «lst_primos» contiene la lista de primos obtenida en el paso anterior. Al aplicarle la funciónset(), esta lista se queda sin elementos repetidos, es decir que no hay primos repetidos en ella.
La segunda variable «lst_exp» es una lista vacía en donde guardaremos los exponentes de cada primo encontrado.
lst_primos = set(lst_descomp)
lst_exp = []
Luego iniciamos un ciclo
for. En esta parte lo que hace el código es tomar un primo \(p\) dentro del conjunto «lst_primos» y con el métodocount()aplicado a la variable «lst_decomp» cuenta cuántas veces aparece dicho primo en la descomposición. Ese valor encontrado es el exponente del primo \(p\) y es guardado en la lista «lst_exp». El ciclo se repite hasta que encuentre los exponentes de cada primo involucrado en la descomposición.
for i in lst_primos:
exp = lst_descomp.count(i)
lst_exp.append(exp)
Finalmente, lo que nos regresa este código como salida es una lista con dos listas como elementos. Una con los primos y otra con cada exponente de dicho primo. Hay que observar que al final el conjunto de primos es convertido en lista para poder utilizarlo en los siguientes códigos.
return [list(lst_primos), lst_exp]
Pasemos al segundo código, el cual calcula la suma de todos los divisores de un entero \(n\)
def suma_divisores(n):
b = n
lst_prim_exp = fact_primos_exponentes(b)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
suma = 1
for i in range(len(lst_prim_exp[0])):
a = ((lst_prim_exp[0][i])**(lst_1[i])-1)//(lst_prim_exp[0][i] -1)
suma *= a
return print("La suma de los divisores del número ",n," es:", suma)
Definimos una función llamada «suma_divisores» la cual recibe como argumento un entero positivo \(n\).
def suma_divisores(n):
Creamos cuatro variables.
La primera es la variable «b» a la que le asignamos el valor del entero \(n\), ya que este se va modificando dentro del código. En la segunda variable «lst_prim_exp» ejecutamos la función anterior para obtener la lista con las listas de primos involucrados en la descomposición canónica y cada uno de sus exponentes.
La tercera variable «lst_1» es una comprensión de listas y crea una nueva lista a partir de otra lista, lo que hace es tomar la lista de exponentes y sumarle \(1\) a todos los elementos de la lista, siguiendo la fórmula de la Proposición 11. La última variable «suma» le asignamos un valor inicial de \(1\).
b = n
lst_prim_exp = fact_primos_exponentes(b)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
suma = 1
Luego iniciamos un ciclo
foren donde el rango es la longitud de la lista de primos que tiene el entero \(n\). Luego en la variable «a» vamos a aplicar la fórmula de la Proposición 11. Una vez obtenido el primer factor, el valor se multiplica a la variable «suma.» El cicloforcontinua hasta que calcule cada factor de la fórmula y se multiplique en la variable «suma». Finalmente el código nos arroja el valor de la variable «suma», la cual es la suma de los divisores del entero \(n\).
for i in range(len(lst_prim_exp[0])):
a = ((lst_prim_exp[0][i])**(lst_1[i])-1)//(lst_prim_exp[0][i] -1)
suma *= a
return print("La suma de los divisores del número ",n," es:", suma)
Veamos el último código utilizado en este capítulo, el cual calcula el número de divisores que tiene un entero \(n\)..
def numero_divisores(n):
a = n
lst_prim_exp = fact_primos_exponentes(a)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
divisores = 1
for k in lst_1:
divisores *= k
return print("El número ",n , "tiene: ",divisores, " divisores.")
Definimos una función llamada «numero_divisores» la cual recibe como argumento un entero positivo \(n\).
def numero_divisores(n):
Creamos cuatro variables.
La primera es la variable «a» a la que le asignamos el valor del entero \(n\), ya que este se va modificando dentro del código. En la segunda variable «lst_prim_exp» ejecutamos la función «fac_primos_exponentes» para obtener la lista con las listas de primos involucrados en la descomposición y cada uno de sus exponentes.
La tercera variable «lst_1» es una comprensión de listas y crea una nueva lista a partir de otra lista. Lo que hace es tomar la lista de exponentes y sumarle \(1\) a todos los elementos de la lista, siguiendo la fórmula de la Proposición 13. La última variable «divisores» le asignamos un valor inicial de \(1\).
a = n
lst_prim_exp = fact_primos_exponentes(a)
lst_1 = [i + 1 for i in lst_prim_exp[1]]
divisores = 1
Luego iniciamos un ciclo
foren el cual tomamos cada valor de la lista «lst_1» y se va multiplicando a la variable divisores. Cuando termina el ciclo, en la variable «divisores» queda guardado el valor de la multiplicación de todos los valores de la lista. Finalmente ese es el valor de salida de la función, en donde nos indica que el entero \(n\) tiene tantos divisores.
for k in lst_1:
divisores *= k
return print("El número ",n , "tiene: ",divisores, " divisores.")
Ejercicios de práctica#
Demuestra que \(n\) es un número primo si y sólo si \(\tau(n) = 2\).
Demuestra que si \(a\) y \(b\) son números enteros tales que \((a,b) = 1\), entonces \(\tau(ab) = \tau(a) \cdot \tau(b)\).
Calcula \(\tau(n)\) y \(\sigma(n)\) para cada uno de los siguientes números:
\(28\).
\(43\).
\(496\).
\(2187\).
Encuentra todos los enteros positivos \(d\) que tienen exactamente \(16\) divisores enteros positivos \(d_1,d_2,...,d_{16}\) tales que \(1=d_1 < d_2 < \ldots < d_{16}=d\), \(d_6=18\) y \(d_9 - d_8 = 17\).
Demuestra lo siguiente. Si \(\tau(n)\) es impar entonces \(n\) es un cuadrado.
Demuestra lo siguiente. Si \(n\) es un cuadrado entonces \(\sigma(n)\) es impar.