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: 246
Registrado: Sab 16 Oct, 2010 4:55 pm
Medals: 2
Colaborador OFO - Jurado
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