ataca el totient
Marko Riedel
Hola grupo,
sea
f(s) = sum_{n >= 1} fi(n)/n^s,
es decir, la funcion generatriz de Dirichlet de fi(n).
Demuestrese por induccion matematica que
f(s) = zeta(s-1)/zeta(s)
donde zeta(s) es la funcion zeta de Riemann.
Animo! Es bastante bonito. ;-)
Un saludo.
--
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mri...@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html |
+------------------------------------------------------------+
Marko Riedel
demostracion.
Un saludo.
Marko
Marko Riedel
> Hola grupo,
>
> sea
>
> f(s) = sum_{n >= 1} fi(n)/n^s,
>
> es decir, la funcion generatriz de Dirichlet de fi(n).
>
> Demuestrese por induccion matematica que
>
> f(s) = zeta(s-1)/zeta(s)
>
> donde zeta(s) es la funcion zeta de Riemann.
>
Hola grupo,
ya casi lo tenemos si consegimos demostrar que
f(s) zeta(s) = zeta(s-1).
Pero resulta que
[n^s] f(s) = fi(n)
[n^s] zeta(s) = 1
y
[n^s] zeta(s-1) = n.
Entonces lo que se pide es una demostracion por induccion matematica
que
sum_{d|n} fi(d) = n.
(Se trata de aplicar la convolucion de Dirichlet a f(s) y zeta(s);
vease tambien http://en.wikipedia.org/wiki/Dirichlet_convolution.)
Seguire esperando la segunda parte desde Alemania. ;-)
Marko Riedel
> Marko Riedel <markor...@yahoo.de> writes:
>
> > Hola grupo,
> >
> > sea
> >
> > f(s) = sum_{n >= 1} fi(n)/n^s,
> >
> > es decir, la funcion generatriz de Dirichlet de fi(n).
> >
> > Demuestrese por induccion matematica que
> >
> > f(s) = zeta(s-1)/zeta(s)
> >
> > donde zeta(s) es la funcion zeta de Riemann.
> >
>
> Hola grupo,
>
> ya casi lo tenemos si consegimos demostrar que
>
> f(s) zeta(s) = zeta(s-1).
>
> Pero resulta que
>
> [n^s] f(s) = fi(n)
>
> [n^s] zeta(s) = 1
>
> y
>
> [n^s] zeta(s-1) = n.
>
> Entonces lo que se pide es una demostracion por induccion matematica
> que
>
> sum_{d|n} fi(d) = n.
Hola de nuevo,
veamos lo de la induccion. Probaremos que
sum_{d|n} fi(d) = n
por induccion sobre el numero k de factores primos que tiene n.
Sea k = 1, entonces n = p^v donde v >= 1 y p es un primo. (El caso de
n=1, es decir, que n no tenga ningun factor primo, es trivial.)
Entonces
sum_{d|n} fi(n) = sum_{w=0}^v fi(p^w) =
fi(1) + fi(p) + fi(p^2) + fi(p^3) + ... + fi(p^v) =
1 + (p-1) + (p^2-p) + (p^3-p^2) + ... + (p^v-p^{v-1}) =
p^v = n
y la proposicion se verifica. (Se trata de una suma telescopica.)
Tenga n entonces k+1 factores primos, y sea cierta la proposicion para
numeros con k factores primos. Entonces n = m p^v donde m tiene k
factores primos y v >= 1. Distinguiremos dos clases de divisores de n:
los que son multiplos de p y los que no lo son:
sum_{d|n} fi(n) = sum_{d|m} fi(d) +
sum_{d|m} sum_{w=1}^v fi(d p^w).
La primera suma es m por hipotesis y la segunda se puede simplificar:
sum_{d|m} sum_{w=1}^v fi(d p^w) =
sum_{d|m} sum_{w=1}^v fi(d) fi(p^w) =
sum_{d|m} fi(d) sum_{w=1}^v fi(p^w).
Pues bien, sum_{w=1}^v fi(p^w) es otra suma telescopica:
sum_{w=1}^v fi(p^w) = fi(p) + fi(p^2) + fi(p^3) + ... + fi(p^v) =
p-1 + (p^2-p) + (p^3-p^2) + ... + (p^v-p^{v-1}) = p^v - 1.
Todo esto da lo siguiente para n = m p^v con k+1 factores primos:
sum_{d|n} fi(n) = m + m (p^v-1) = m p^v = n
y ya esta.
Marko Riedel
> Marko Riedel <markor...@yahoo.de> writes:
>
> > Marko Riedel <markor...@yahoo.de> writes:
> >
> > > Hola grupo,
> > >
> > > sea
> > >
> > > f(s) = sum_{n >= 1} fi(n)/n^s,
> > >
> > > es decir, la funcion generatriz de Dirichlet de fi(n).
> > >
> > > Demuestrese por induccion matematica que
> > >
> > > f(s) = zeta(s-1)/zeta(s)
> > >
> > > donde zeta(s) es la funcion zeta de Riemann.
> > >
> >
> > Hola grupo,
> >
> > ya casi lo tenemos si consegimos demostrar que
> >
> > f(s) zeta(s) = zeta(s-1).
> >
> > Pero resulta que
> >
> > [n^s] f(s) = fi(n)
> >
> > [n^s] zeta(s) = 1
> >
> > y
> >
> > [n^s] zeta(s-1) = n.
> >
> > Entonces lo que se pide es una demostracion por induccion matematica
> > que
> >
> > sum_{d|n} fi(d) = n.
>
Hola grupo,
no es necesaria usar induccion matematica. Podemos usar el siguiente
lema:
"si f(n) es multiplicativa, sum_{d|n} f(d) tambien lo es."
(Una funcion aritmetica f se dice multiplicativa si
f(1) = 1 y f(m n) = f(m) f(n)
cuando (m, n) = 1. El totient es una funcion multiplicativa porque si
n = p1^v1 p2^v2 p3^v3 ... pk^vk
y
m = q1^w1 q2^w2 q3^w3 ... ql^wl
entonces
fi(n m) = n m (1-1/p1) ... (1-1/pk) (1-1/q1) ... (1-1/ql) =
n (1-1/p1) ... (1-1/pk) m (1-1/q1) ... (1-1/ql) = fi(n) fi(m).)
Es facil probar el lema. Sea g(n) = sum_{d|n} f(d). Entonces
g(n m) = sum_{d|n m} f(d) = sum_{d|n} sum_{e|m} f(d e) =
sum_{d|n} sum_{e|m} f(d) f(e) = sum_{d|n} f(d) sum_{e|m} f(e) =
g(n) g(m)
y g(n) es multiplicativa.
Para probar sum_{d|n} fi(d) = n basta con verificarlo para potencias
p^v de primos p:
sum_{d|n} fi(d) = fi(1) + fi(p) + fi(p^2) + ... + fi(p^v) =
1 + (p-1) + (p^2-p) + (p^3-p^2) + ... + (p^v-p^{v-1}) = p^v = n
(suma telescopica) y ya esta.
Marko Riedel
> Marko Riedel <markor...@yahoo.de> writes:
>
> > Marko Riedel <markor...@yahoo.de> writes:
> >
> > > Marko Riedel <markor...@yahoo.de> writes:
> > >
> > > > Hola grupo,
> > > >
> > > > sea
> > > >
> > > > f(s) = sum_{n >= 1} fi(n)/n^s,
> > > >
> > > > es decir, la funcion generatriz de Dirichlet de fi(n).
> > > >
> > > > Demuestrese por induccion matematica que
> > > >
> > > > f(s) = zeta(s-1)/zeta(s)
> > > >
> > > > donde zeta(s) es la funcion zeta de Riemann.
> > > >
> > >
> > > Hola grupo,
> > >
> > > ya casi lo tenemos si consegimos demostrar que
> > >
> > > f(s) zeta(s) = zeta(s-1).
> > >
> > > Pero resulta que
> > >
> > > [n^s] f(s) = fi(n)
> > >
> > > [n^s] zeta(s) = 1
> > >
> > > y
> > >
> > > [n^s] zeta(s-1) = n.
> > >
> > > Entonces lo que se pide es una demostracion por induccion matematica
> > > que
> > >
> > > sum_{d|n} fi(d) = n.
> >
>
> Hola grupo,
>
> no es necesaria usar induccion matematica.
Hola grupo,
es mas facil aun: sea n = p1^v1 p2^v2 p3^v3 ... pk^vk y mirese el
producto
(1 + p1 + p1^2 + p1^3 + ... + p1^v1)
(1 + p2 + p2^2 + p2^3 + ... + p2^v2)
(1 + p3 + p3^2 + p3^3 + ... + p3^v3)
...
(1 + pk + pk^2 + pk^3 + ... + pk^vk)
que es igual sum_{d|n} d. Incluye, por ejemplo, el termino
d = p1^3 p2 p5^6 | n
y todos los demas d. Pero para fi(n) la contribucion de p^v no es p^v
sino p^v-p^{v-1}, asi que trabajamos con el producto
(1 + (p1-1) + (p1^2-p1) + (p1^3-p^2) + ... + (p1^v1-p1^{v1-1})
(1 + (p2-1) + (p2^2-p2) + (p2^3-p^2) + ... + (p2^v2-p2^{v2-1})
(1 + (p3-1) + (p3^2-p3) + (p3^3-p^2) + ... + (p3^v3-p3^{v3-1})
...
(1 + (pk-1) + (pk^2-pk) + (pk^3-p^2) + ... + (pk^vk-pk^{vk-1}).
Es un producto de sumas telescopicas y vale
p1^v1
p2^v2
p3^v3
...
pk^vk,
es decir, n.