secretos del totient
Marko Riedel
Hola grupo,
sea Fi_n(z) el polinomio ciclotomico de orden n, es decir
Fi_n(z) = prod_{(k,n)=1} (z-rho_k)
donde rho_k = exp(2 pi i k/n) y el producto se extiende sobre las
raices primitivas de orden n.
Demuestrese que
[z^{fi(n)-1}] Fi_n(z) = -mu(n).
Luego sea tau(n) el numero de divisores de n y sigma(n) la suma de los
divisores de n.
Pruebese que
sum_{d|n} fi(d) tau(n/d) = sigma(n).
Un saludo.
--
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mri...@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html |
+------------------------------------------------------------+
Marko Riedel
> Hola grupo,
>
> sea Fi_n(z) el polinomio ciclotomico de orden n, es decir
>
> Fi_n(z) = prod_{(k,n)=1} (z-rho_k)
>
> donde rho_k = exp(2 pi i k/n) y el producto se extiende sobre las
> raices primitivas de orden n.
>
> Demuestrese que
>
> [z^{fi(n)-1}] Fi_n(z) = -mu(n).
>
Hola grupo,
el primer paso es observar que
[z^{fi(n)-1}] Fi_n(z) = -sum_{(k,n)=1} rho_k.
Entonces se trata de probar que
sum_{(k,n)=1} rho_k = mu(n).
Lo probamos por induccion completa. Es cierto para n=1 (rho_1 = 1 =
mu(1)) y n=2 (rho_1 = -1 = mu(2)). Luego sea cierto para
m<n. Comenzamos por
sum_{k=1}^n rho_k = exp(2 pi i/n) sum_{k=0}^{n-1} exp(2 pi i k/n)
= exp(2 pi i/n) (exp(2 pi i n/n)-1)/(exp(2 pi i/n)-1)
= exp(2 pi i/n) (1-1)/(exp(2 pi i/n)-1) = 0.
Esto significa que
sum_{d|n} sum_{(k,n)=d} rho_k = 0
o sea
sum_{(k, n)=1} rho_k + sum_{d|n, d>1} sum_{(k,n)=d} rho_k = 0.
Pero
sum_{(k,n)=d} rho_k = sum_{(l,n/d)=1} rho_l = mu(n/d)
por hipotesis (d>1 implica que n/d<n). Tenemos que
sum_{(k, n)=1} rho_k + sum_{d|n, d>1} mu(n/d) = 0
o sea
sum_{(k, n)=1} rho_k + sum_{d|n} mu(n/d) = mu(n).
Finalmente notese que sum_{d|n} mu(n/d) = sum_{d|n} mu(d) = 0 y hemos
probado que
sum_{(k, n)=1} rho_k = mu(n),
QED.
> Luego sea tau(n) el numero de divisores de n y sigma(n) la suma de los
> divisores de n.
>
> Pruebese que
>
> sum_{d|n} fi(d) tau(n/d) = sigma(n).
>
Esta identidad se obtiene trivialmente de las relaciones
fi = n * mu
mu * 1 = [n=1]
tau = 1 * 1
y
sigma = 1 * n.
La izquierda es fi * tau = n * mu * 1 * 1 = n * [n=1] * 1 = n * 1 y la
derecha es 1 * n, QED.
Una demostracion alternativa, digamos, clasica, comienza por probar
que la relacion es cierta para potencias de primos n = p^v. Sea
v>1. En este caso obtenemos
sum_{d|n} fi(d) tau(n/d) = sum_{w=0}^v fi(p^w) tau(p^{v-w})
= v+1 + sum_{w=1}^v (p^w-p^{w-1}) (v-w+1).
Hay cancelacion telescopica y la suma es
v+1 + p^v - v + sum_{w=1}^{v-1} p^w ((v-w+1)-(v-w))
= 1 + p^v + sum_{w=1}^{v-1} p^w = 1 + p^v + p (p^{v-1}-1)/(p-1)
= (p-1 + p^{v+1}-p^v + p^v-p)/(p-1) = (p^{v+1}-1)/(p-1) = sigma(n).
(Para v=0 tenemos fi(1) tau(1) = 1 * 1 = sigma(1) y para v=1, fi(1)
tau(p) + fi(p) tau(1) = 2 + (p-1) = p+1 = (p^2-1)/(p-1) = sigma(p).)
Luego sigma es multiplicativa, asi que
sigma(n m) = sum_{d|n} fi(d) tau(n/d) sum_{e|m} fi(e) tau(m/e)
= sum_{d|n} sum_{e|m} fi(d) tau(n/d) fi(e) tau(m/e).
Usando que (d, e)=1 y (n/d, m/e)=1 (porque (n,m)=1), y que fi y tau
son tambien multiplicativas, tenemos
sigma(n m) = sum_{d|n} sum_{e|m} fi(d e) tau(n/d m/e)
= sum_{d|n m} fi(d) tau(n m/d)
y la relacion es cierta para todo n.