La cantidad de divisores de un número

La cantidad de divisores de un número

UNREAD_POSTpor ésta » Lun 20 Dic, 2010 6:08 pm

Sea \tau(n) la cantidad de divisores de un entero positivo n.

Vamos a dar una formula general para calcular \tau(n) en base a la factorización en primos de n.

Si n=p_0^{e_0}p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}.

Sea d un divisor de n, entonces todo divisor primo de d también divide a n.
Podemos escribir d de la forma d=p_0^{i_0}p_1^{i_1}p_2^{i_2}\ldots p_k^{i_k}, con 0\leq i_j \leq e_j, para todo entero j tal que 0\leq j\leq k.

Y además sea d'=p_0^{i_0}p_1^{i_1}p_2^{i_2}\ldots p_k^{i_k}, con 0\leq i_j \leq e_j, para todo entero j tal que 0\leq j\leq k.
Entonces \frac{n}{d'}=\frac{p_0^{e_0}p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}}{p_0^{i_0}p_1^{i_1}p_2^{i_2}\ldots p_k^{i_k}}=p_0^{e_0-i_0}p_1^{e_1-i_1}p_2^{e_2-i_2}\ldots p_k^{e_k-i_k},
que es entero, porque e_j-i_j\geq 0.

Entonces todo número de la forma de d' es divisor de n y todo divisor de n es de la forma de d', por lo tanto \tau(n) es la cantidad de números de la forma de d'.
Para cada i_j hay e_j+1 posibilidades de elegirlo, entonces hay (e_0+1)(e_1+1)(e_2+1)\ldots(e_k+1) números de la forma de d' \Rightarrow \tau(n)=(e_0+1)(e_1+1)(e_2+1)\ldots(e_k+1).

Además claramente si m y n son enteros positivos tal que gcd(m,n)=1, entonces no tienen divisores primos es común entonces en mn, los primos están elevados a la misma potencia que en m o en n, entonces \tau(mn)=\tau(m)\tau(n).

Recapitulando tenemos que:
1) \tau(n)=(e_0+1)(e_1+1)(e_2+1)\ldots(e_k+1) si n=p_0^{e_0}p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}.
2) \tau(mn)=\tau(m)\tau(n) si gcd(m,n)=1.
Imagen
Avatar de Usuario
ésta
 
Mensajes: 219
Registrado: Sab 16 Oct, 2010 4:55 pm
Nivel: Ñandú

Re: La cantidad de divisores de un número

UNREAD_POSTpor Fredy10 » Vie 25 Feb, 2011 1:25 pm

Bueno, esto me hace acordar a una formula muy interesante que vale para toda función multiplicativa \theta \left ( n \right ).

En primer lugar una función es multiplicativa (en teoría de números) si \theta \left ( n \right )\cdot \theta \left ( m \right )= \theta \left ( n\cdot m \right ) para n coprimo con m. Estas funciones pueden ser bastante interesantes, por ejemplo es facil de ver que \theta \left ( 1 \right )= 1 o 0 si \theta \left ( n \right )= 0 para todo n.

Lo que queremos hallar es una formula para la suma de todos los \theta \left ( d \right ) donde d es un divisor de n.
Sea n=p_1^{\alpha _1}p_2^{\alpha _2}...p_j^{\alpha _j} la factorización en primos de n, notemos que \theta \left ( p_a^{c}\cdot p_b^{d} \right )=\theta \left ( p_a^{c} \right )\cdot \theta \left ( p_b^{d} \right ) por lo tanto vale que \sum_{d|n}^{ }\theta \left ( d \right )=\prod_{i=1}^{j}\sum_{k=0}^{\alpha _i}\theta \left ( p_i^{\alpha _k \right} )
Esto se ve muy feo así, pero basta escribirlo así para tornarlo un tanto mas comprensible:
\sum_{d|n}^{ }\theta \left ( d \right )=\prod_{i=1}^{j}\left ( \theta \left ( 1 \right ) + \theta \left (  p_i\right )+\theta \left (  p_i^2\right )+...+\theta \left ( p_i^{\alpha _i} \right )\right ).
Aquí es fácil ver que al expandir la expresión (teniendo en cuenta el carácter multiplicativo de la función) que la igualdad es correcta, ya que todo divisor de n tiene la forma: n=p_1^{\beta _1}p_2^{\beta _2}...p_j^{\beta _j} donde \alpha _n \geq \beta _n.

En el ejemplo de ésta, \theta \left ( n \right )= 1 para todo n y con la formula anterior obtenemos \prod_{i=1}^{j}\left ( 1+\alpha _i \right ).

Se pueden hallar otras formulas interesantes de esta, por ejemplo si tomamos \theta \left ( n \right )= n (que claramente es multiplicativa), obtendremos una formula para la suma de los divisores de n. Usando la formula de la suma de progresión geometrica tendremos:
\sum_{d|n}^{ }d= \prod_{i=1}^{j}\frac{{p_i^{\alpha _i+1}+1}}{p_i+1}
O teniendo en cuenta que \phi (n) es una funcion multiplicativa y teniendo en cuenta que \phi (p^\alpha )=p^\alpha-p^{\alpha-1} es fácil demostrar la siguiente igualdad:
\sum_{d|n}^{ }\phi \left ( n \right )=n
Avatar de Usuario
Fredy10
 
Mensajes: 13
Registrado: Mar 19 Oct, 2010 2:34 pm


Volver a Teoría de Numeros

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado